节点深度：对任意节点x，x节点的深度表示为根节点到x节点的路径长度。所以根节点深度为0，第二层节点深度为1，以此类推
节点高度：对任意节点x，叶子节点到x节点的路径长度就是节点x的高度
树的深度：一棵树中节点的最大深度就是树的深度，也称为高度
父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
子节点：一个节点含有的子树的根节点称为该节点的子节点
节点的层次：从根节点开始，根节点为第一层，根的子节点为第二层，以此类推
兄弟节点：拥有共同父节点的节点互称为兄弟节点
度：节点的子树数目就是节点的度
叶子节点：度为零的节点就是叶子节点
祖先：对任意节点x，从根节点到节点x的所有节点都是x的祖先（节点x也是自己的祖先）
后代：对任意节点x，从节点x到叶子节点的所有节点都是x的后代（节点x也是自己的后代）
森林：m颗互不相交的树构成的集合就是森林

1. 无序树
   树的任意节点的子节点没有顺序关系。
2. 有序树
   树的任意节点的子节点有顺序关系。
3. 二叉树
   树的任意节点至多包含两棵子树。
4. 满二叉树
   叶子节点都在同一层并且除叶子节点外的所有节点都有两个子节点。
5. 完全二叉树
   对于一颗二叉树，假设其深度为d（d>1）。除第d层外的所有节点构成满二叉树，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
6. 平衡二叉树
   它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树。
7. 二叉查找树
   又称为二叉搜索树
   若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
   若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
   任意节点的左、右子树也分别为二叉查找树；
   没有键值相等的节点。
8. 线索二叉树
   遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点(第一个和最后一个结点除外)都有一个直接前驱和直接后继。
9. 霍夫曼树
   带权路径最短的二叉树称为哈夫曼树或最优二叉树。
10. 红黑树
    红黑树是一颗特殊的二叉查找树，除了二叉查找树的要求外，它还具有以下特性：
    • 每个节点或者是黑色，或者是红色。
    • 根节点是黑色。
    • 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
    • 如果一个节点是红色的，则它的子节点必须是黑色的。
    • 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
      图示如下：
      
11. B树
    一颗m阶B树的特性：
    • 根结点至少有两个子女（如果B树只有一个根节点，这个根节点的key的数量可以为[1~m-1])
    • 每个非根节点所包含的关键字个数 j 满足：⌈m/2⌉ - 1 <= j <= m - 1，节点的值按非降序方式存放，即从左到右依次增加
    • 除根结点以及叶子节点以外的所有结点的度数正好是关键字总数加1，故内部节点的子树个数 k 满足：⌈m/2⌉ <= k <= m
    • 所有的叶子结点都位于同一层
12. B+树
    m阶B+树是m阶B树的变体，它的定义大致跟B-tree一致，不过有以下几点不同：
    • 有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点，其中⌈m/2⌉ <= n <= m
    • 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接
    • 所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字
    • 通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点
13. B * 树
    B * 树是B+树的变体，除了B+树的要求之外，还有以下特性：
    • ⌈m * 2/3⌉ <= n <=m 这里的n是除根节点之外的内部节点的键
    • 增加内部节点中兄弟节点的指针，由左边指向右边

3.1、二叉树的定义

二叉树，顾名思义是一种每个节点中至多有两棵子树的一种树结构，并且有左右的分别，其次序也不能颠倒。
二叉树的两棵子树分别称为左子树以及右子树，而对于两棵子树而言，同样是一个二叉树，同样存在两棵子树。
综上所述，如果交换二叉树的左右节点，就会变成另外一棵二叉树，即使只有一个子树，同样也要区分左右子树。
以下是二叉树的几个形态：

3.2、特殊的二叉树

1. 斜二叉树
   所有子节点在左边的叫左斜二叉树，所有节点在右边的叫做右斜二叉树。
2. 满二叉树
   一颗高度为h的二叉树，且含有2h-1个节点的二叉树称为满二叉树，也就是说在每个节点上都存在数量最多的子节点。
   
3. 完全二叉树
   一颗高度为h的二叉树，有n个节点，当且仅当每一个节点都与高度为h的满二叉树中编号为1~n的节点一一对应的时候，称为完全二叉树。
   
   • 若i ≤ n / 2 i≤n/2i≤n/2, 则结点i ii为分支结点，否则为叶子结点。
   • 叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。
   • 若有度为1 11的结点，则只可能有一个，且该结点只有左孩子而无右孩子(重要特征)。
   • 按层序编号后，一旦出现某结点(编号为i ii)为叶子结点或只有左孩子，则编号大于i ii的结点均为叶子结点。
   • 若n nn为奇数，则每个分支结点都有左孩子和右孩子;若n nn为偶数，则编号最大的分支结点(编号为n / 2 n/2n/2)只有左孩子，没有右孩子，其余分支结点左、右孩子都有。
4. 平衡二叉树
   一棵二叉树的左右节点的深度差别不大于1，就是平衡二叉树。
5. 二叉排序树
   一棵二叉树的左节点上的所有的节点的值都比根节点小，并且所有右节点上的所有的节点的值都比根节点大，且每一个子节点又分别是一颗二叉排序树，这就是二叉排序树。

3.3、二叉树的存储结构

二叉树有两种存储结构，分别是顺序存储结构以及链式存储结构。

1. 顺序存储结构

二叉树的顺序存储结构是指用一组地址连续的存储单元自上到下，自左到右存储完全二叉树的节点元素，即将二叉树上编号为 i 的项存储在一维数组下标为 i-1 的位置上。

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映结点之间的逻辑关系，这样既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

但对于一般的二叉树，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点，让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中。然而，在最坏情况下，一个高度为 h 且只有 h 个结点的单支树却需要占据近 2h−1 个存储单元。二叉树的顺序存储结构如图所示，其中0表示并不存在的空结点。

2. 链式存储结构

由于顺序存储结构的实用性不强，所以有了链式存储结构。
二叉树有一个根节点，一个根节点又有两个子节点，所以我们设计一个链式存储结构的结构为一个数据域以及两个指针域。如下：

其中data是数据域，lchild 和rchild都是指针域，分别存放指向左孩子和右孩子的指针。

容易验证，在含有 n 个结点的二叉链表中，含有 n + 1 个空链域。

3.4、遍历二叉树

首先创建一个二叉树节点类，以便后面的遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

二叉树的遍历，是指从根节点出发，逐步查找访问每一个子节点，子节点的子节点的一个过程，其中每一个节点必须也只能被访问一次。

遍历二叉树有多种方式，以下是一些基本的遍历方式：
(1).先序遍历
(2).中序遍历
(3).后序遍历

1. 先序遍历

先序遍历的顺序为：根节点-左子树-右子树

其算法实现为：
leetcode-144

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        preorder(root,list);
        return list;
    }
    public void preorder(TreeNode root, List<Integer> list){
        if (root==null){
            return;
        }
        list.add(root.val);
        preorder(root.left,list);
        preorder(root.right,list);
    }
}

2. 中序遍历

中序遍历的顺序为：左子树-根节点-右子树

其算法实现为：
leetcode-94

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    List<Integer> list=new ArrayList<Integer>();
    public List<Integer> inorderTraversal(TreeNode root) {
        inorder(root,list);
        return list;
    }
    public void inorder(TreeNode root, List<Integer> res){
        if (root==null){
            return;
        }
        inorder(root.left,res);
        res.add(root.val);
        inorder(root.right,res);
    }
}

3. 后序遍历

后序遍历的顺序为：左子树-右子树-根节点

其算法实现为：
leetcode-145

1
2
3
4
5
6
7
8
9
10
11
12
13

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        dfs(root,list);
        return list;
    }
    public void dfs(TreeNode root,List<Integer> list){
        if (root==null){
            return;
        }
        dfs(root.left,list);
        dfs(root.right,list);
        list.add(root.val);
    }

3.5、层序遍历二叉树

除了上一节中的三种常见的遍历二叉树的方式，还有一种层序遍历的方式，该遍历方式就是从根节点开始，依层遍历，先遍历完第二层，再遍历第二层，以此类推直到结束。

要进行层次遍历，需要借助一个队列。先将二叉树根结点入队，然后出队，访问出队结点，若它有左子树，则将左子树根结点入队;若它有右子树，则将右子树根结点入队。然后出队，访问出队结…如此反复，直至队列为空。

其算法实现为：
leetcode-102

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        
        return ret;
    }
}

4.1、线索二叉树理论入门

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点(第一个和最后一个结点除外)都有一个直接前驱和直接后继。
传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。

为了区分二叉树的左孩子指针和右孩子指针是否为空，或者是否指向前驱节点或后继节点，我们将节点的结构改成5个域，在原二叉树的基础上添加左标志域Ltag和右标志域Rtag，他们是两个int型的数据域。

• 如果节点有左孩子，那么Lchild依然指向他的左孩子，否则指向遍历序列中他的前驱节点。
• 如果节点有右孩子，那么Rchild依然指向他的左孩子，否则指向遍历序列中他的后继节点。

Ltag和Rtag的定义如下:

• Ltag : 等于0时，Lchild域指示节点的左孩子;等于1时，Lchild指示节点的遍历前驱。
• Rtag : 等于0时，Rchild域指示节点的左孩子;等于1时，Rchild指示节点的遍历后继。

4.2、二叉树的线索化

二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树，线索化的过程就是在遍历的过程中修改空指针的过程。

1. 当遍历到左孩子指针域为空的时候，我们应该填入该节点的遍历前驱节点的指针，这时候我们可以提前声明一个全局变量pre来记录刚刚访问过的节点，在遍历过程中如果遇到左孩子为空的节点，就将pre赋给他的左孩子域，并且将Ltag设置为1。pre的初值应该为NULL，因为便利的首节点的前驱节点一定为空。
2. 当遍历过程中右孩子的指针域为空的时候，要填的节点应该为当前节点遍历序列的后继节点，但是我们现在无法确定，因此当前节点的右孩子指针域只能遍历到下一个节点的时候在填，并且当前节点就是pre节点的后继节点，所以我们只需要在遍历的过程中加上判断，回填pre的语句，若pre的右孩子节点为空，那么将当前的节点赋值给pre的右节点，同时pre节点的Rtag应该置为1

以下是中序线索二叉树的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void Inthread(BiTree root) 
{
//pre为全局变量，在函数外已经声明过
	if(root != null)
	{
		Inthread(root.Lchild);//递归线索化root的左孩子
		if(root.Lchild == null) //置前置线索 
		{
			root.Lchild = pre;
			root.Ltag = 1;
		}
		else{
			root.Ltag = 0;
		}
		if(pre != null && pre.Rchlid == null)//置后置线索
		{
			pre.Rchlid = root;
			pre.Rtag = 1;
		} 
		pre = root;
		Inthread(root.Rchlid);//递归线索化root的右孩子
	}
}

4.3、遍历线索二叉树

在讲树的存储结构时，我们提到了树的孩子兄弟法可以将一棵树用二叉链表进行存储，所以借助二叉链表，树和二叉树可以相互进行转换。从物理结构来看，它们的二叉链表也是相同的，只是解释不太一样而已。 因此，只要我们设定一定的规则，用二叉树来表示树，甚至表示森林都是可以的，森林与二叉树也可以互相进行转换。

5.1、树转换为二叉树

树转换为二义树的规则:每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称“左孩子右兄弟”。由于根结点没有兄弟，所以对应的二叉树没有右子树。

以下是树转换为二叉树的画法：

1. 在兄弟节点中加一连线
2. 对每个节点，只保留它与第一个子节点的连线，而其他子节点的连线全都删掉
3. 以根节点为中心，旋转45°
   

5.2、森林转换为二叉树

森林是由若干棵树组成的，所以完全可以理解为,森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作。

以下是森林转换为二叉树的画法：

1. 将森林中的每棵树都转换为单独的二叉树
2. 每一颗单独的树的根节点都看作兄弟节点，在每棵树的下面加一条连线
3. 以第一棵树为中心旋转45°
   

而二叉树转化为树或者森林即为将上述的过程倒推一遍即可。

二叉排序树又称为二叉查找树。其可能是一颗空树，也有可能是具有以下性质的二叉树：

1. 若左子树非空，那么左子树上的所有节点值均小于根节点的值
2. 若右子树非空，那么右子树上的所有节点值均大于根节点的值
3. 左右节点分别都是一颗二叉搜索树

根据二叉排序树的定义，左子树结点值<根结点值<右子树结点值，所以对二叉排序树进行中序遍历，可以得到一个递增的有序序列。例如，下图所示二叉排序树的中序遍历序列为123468。

首先创建一个二叉排序树：

1
2
3
4
5
6
7
8
9
10

public class BinaryTreeNode {
	public int data; //数据域
	public BinaryTreeNode left, right; //指向左右子节点的指针

	public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right) {
		this.data = data;
		this.left = left;
		this.right = right;	
	}
}

6.1、 初始化二叉排序树

首先是在初始化的类中定义二叉查找树的根节点：

1

public BinaryTreeNode root;

然后即可初始化二叉排序树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public void insertBinaryTree(int[] datas) {

    if(datas.length < 1) {
        System.out.println("the datas Array length small zero!");
        return;
    }
    this.root = new BinaryTreeNode(datas[0], null, null);

    for (int i = 1; i < datas.length; i++) {
        this.insert(this.root, datas[i]);
    }
}

private void insert(BinaryTreeNode root, int data) {
    if(data > root.data) {
        if(root.right == null) 
            root.right = new BinaryTreeNode(data, null, null);
        else 
            this.insert(root.right, data);
    }
    else {
        if(root.left == null) 
            root.left = new BinaryTreeNode(data, null, null);
        else 
            this.insert(root.left, data);
    }
}

通过传递给insertBinaryTree()存储二叉查找树值的数组来完成初始化。通过insert()方法递归的来完成对结点的初始化操作。

6.2、 二叉排序树的中序遍历

1
2
3
4
5
6
7

public void inOrder(BinaryTreeNode root) {
    if(root != null) {
        this.inOrder(root.left);
        System.out.print(root.data + "-");
        this.inOrder(root.right);
    }
}

根据二叉排序树的特性我们知道如果根节点非空，则根节点的左子树上所有结点的值均小于根节点，右子树上的所有结点值均大于根节点。同理对任意子树都满足上面。所以对于二叉排序树的遍历是对二叉排序树的由小到大的升序输出。在这里前序和后序遍历与中序逻辑相似，不做展示。

6.3、二叉排序树的查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public boolean SearchBST(BinaryTreeNode root, int key) {
    if(root == null) {
        return false;
    }
    else if(key == root.data) {
        return true;
    }
    else if(key < root.data) {
        return this.SearchBST(root.left, key);
    }
    else {
        return this.SearchBST(root.right, key);
    }
}

查询操作也基于递归，查询过程和节点结点值进行比较，若成功返回true。

6.4、二叉排序树的插入

1
2
3
4
5
6
7
8
9
10

public boolean InsertBST(BinaryTreeNode root, int key) {
	if(!this.SearchBST(root, key)) {
		this.insert(root, key);
		return true;
	}
	else {
		System.out.println("the key existence in BinaryTree");
		return false;
	}
}

该操作的思路是查询带插入的key是否已经在二叉排序树中，如果不在，执行insert()方法递归的将key插入到指定的位置，如果存在，返回错误信息并结束。

6.5、二叉排序树的删除

相对于其他的操作，二叉排序树的删除操作就显得不是特别容易，因为我们需要保证在删除了某一个元素之后，剩下的元素还保持二叉排序树的结构，所以在删除时就需要考虑多种情况。

1. 当删除的为叶子节点的时候：

可以直接删除该叶子结点的值，并将其父节点指向该节点的域置为null

删除x

2. 当删除的节点只有左子树或者只有右子树

相对来说也好解决，那就是结点删除后，将它的左子树或右子树整个移动到删除结点的位置即可，可以理解为独子继承父业。
比如要删除结点x，直接将父结点p指向待删除的结点x的指针直接指向x结点的唯一儿子结点(l或则是r)，然后删除x结点即可。

删除x

3. 当删除的节点存在左右子树时

这也是最麻烦的一种情况，通常的解决方式是用删除结点x的前驱(或后继)结点填补它的位置。因为x有一个左子结点，因此它的前驱结点就是左子树中的最大结点，这样替换就能保证有序性，因为x.data和它的前驱之间不存在其他的键值。
操作如下：
3.1 寻找到待删除的结点的前驱结点，并用s指向其前驱结点
3.2 找到待删除结点的前驱结点的父结点，并用q来指向前驱结点的父节点。
3.3 将x的前驱结点的值赋给x，完成替换操作。
3.4 最后修改q的指向为s的子节点，并删除s。

通过递归寻找要删除的节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public boolean DeleteBST(BinaryTreeNode root, int key) {

    if(root == null) {
        System.out.println("the root node is null");
        return false;
    }
    else {
        if(key == root.data) {
            return this.delete(root);
        }
        else if(key < root.data) {
            return this.DeleteBST(root.left, key);
        }
        else {
            return this.DeleteBST(root.right, key);
        }
    }
}

删除找到的节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public boolean delete(BinaryTreeNode root) {
    BinaryTreeNode q, s;
    if(root.right == null) {
        root = root.left;	
    }
    else if(root.left == null) {
        root = root.right;
    }
    else {
        q = root;
        s = root.left;
        while(s.right != null) {
            q = s;
            s = s.right;
        }
        root.data = s.data;
        if(q != root) {
            q.right = s.left;
        }
        else {
            q.left = s.left;
        }
    }	
    return true;
}

平衡二叉树(Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree)是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。

它是一种高度平衡的二叉排序树。它要么是一棵空树， 要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF (Balance Factor) ， 那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

7.1、平衡二叉树的查找

在平衡二叉树上进行查找的过程与二叉排序树的相同。

7.2、平衡二叉树的插入

二叉排序树保证平衡的基本思想如下：每当在二叉排序树中插入(或删除)一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

平衡二叉树的插入过程的前半部分与二叉排序树相同，但在新结点插入后，若造成查找路径上的某个结点不再平衡，则需要做出相应的调整。

1. LL平衡旋转(右单旋转)

由于在结点A的左孩子(L)的左子树(L)上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。
如下图所示，结点旁的数值代表结点的平衡因子，而用方块表示相应结点的子树，下方数值代表该子树的高度。

2. RR平衡旋转(左单旋转)

由于在结点A的右孩子®的右子树®上插入了 新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。

3. LR平衡旋转(先左后右双旋转)

由于在A的左孩子(L)的右子树®上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置（即进行一次RR平衡旋转(左单旋转)），然后再把该C结点向右上旋转提升到A结点的位置（即进行一次LL平衡旋转(右单旋转)）。

4. RL平衡旋转(先右后左双旋转)

由于在A的右孩子®的左子树(L)上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置（即进行一次LL平衡旋转(右单旋转)），然后再把该C结点向左上旋转提升到A结点的位置（即进行一次RR平衡旋转(左单旋转)）。

注意: LR和RL旋转时，新结点究竟是插入C的左子树还是插入C的右子树不影响旋转过程，而上图中是以插入C的左子树中为例。

7.2、平衡二叉树的插入——举例

假设关键字序列为15 , 3 , 7 , 10 , 9 , 8通过该序列生成平衡二叉树的过程如下图所示。

8.1、哈夫曼树的定义

在许多应用中，树中结点常常被赋予一个表示某种意义的数值，称为该结点的权。从树的根到任意结点的路径长度(经过的边数)与该结点上权值的乘积，称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为
$$
WPL=\sum_{i=1}^nw_il_i
$$
式中，wi是第i个叶结点所带的权值， li是该叶结点到根结点的路径长度。
在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树，也称最优二叉树。例如，下图中的3棵二叉树都有4个叶子结点a, b,c,d,分别带权7,5,2,4，它们的带权路径长度分别为

a. WPL = 7x2 + 5x2 + 2x2 + 4x2 = 36。
b. WPL = 4x2 + 7x3 + 5x3 + 2x1 = 46。
c. WPL = 7x1 + 5x2 + 2x3 + 4x3 = 35。
其中，图c树的WPL最小。可以验证，它恰好为哈夫曼树。

8.2、构造哈夫曼树

1. 先把有权值的叶子结点按照从大到小（从小到大也可以）的顺序排列成一个有序序列。
2. 取最后两个最小权值的结点作为一个新节点的两个子结点，注意相对较小的是左孩子。
3. 用第2步构造的新结点替掉它的两个子节点，插入有序序列中，保持从大到小排列。
4. 重复步骤2到步骤3，直到根节点出现。

8.3、哈夫曼编码

哈夫曼编码的研究，本质上是一种最优化问题的研究，其目的主要是为了解决远距离通信的数据传输问题。而哈夫曼编码被公认为是一种有效的数据压缩编码。

比如我们有一段文字内容为“ BADCADFEED”要网络传输给别人，显然用二进制的数字(0和1)来表示是很自然的想法。我们现在这段文字只有六个字母ABCDEF，那么我们可以用相应的二进制数据表示，如下表所示：

这样按照固定长度编码编码后就是“001000011010000011101100100011”，对方接收时可以按照3位一分来译码。如果一篇文章很长，这样的二进制串也将非常的可怕。而且事实上，不管是英文、中文或是其他语言，字母或汉字的出现频率是不相同的。

假设六个字母的频率为A 27,B 8,C 15,D 15,E 30,F 5,合起来正好是100%，那就意味着，我们完全可以重新按照赫夫曼树来规划它们。

图左图为构造赫夫曼树的过程的权值显示。右图为将权值左分支改为0，右分支改为1后的赫夫曼树。

这棵哈夫曼树的WPL为:
$$
WPL=2*(15+17+30)+315+4(5+8)=241
$$
此时，我们对这六个字母用其从树根到叶子所经过路径的0或1来编码，可以得到如下表所示这样的定义。

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。
我们将文字内容为“ BADCADFEED”再次编码，对比可以看到结果串变小了。

• 原编码二进制串: 000011000011101100100011 (共 30个字符)
• 新编码二进制串: 10100101010111100(共25个字符)

也就是说，我们的数据被压缩了，节约了大约17%的存储或传输成本。

需要注意的一点是：
0和1究竟是表示左子树还是右子树没有明确规定。左、右孩子结点的顺序是任意的，所以构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度WPL相同且为最优。此外，如有若干权值相同的结点，则构造出的哈夫曼树更可能不同，但WPL必然相同且是最优的。