文章目录

• 7.3.1 二叉排序树
• • 1. 二叉排序树的定义
  • 2. 二叉排序树的查找
  • • 二叉排序树算法
    • 二叉排序树算法分析
  • 3. 二叉排序树的插入
  • 4. 二叉排序树的生成
  • 5. 二叉排序树的删除
• 7.3.2 平衡二叉树
• • 1. 平衡二叉树的定义
  • 2. 平衡二叉树的平衡调整方法
  • • LL型调整
    • RR型调整
    • LR型调整
    • RL型调整
  • 3. 构造平衡二叉排序树

7.3.1 二叉排序树

二叉排序树（Binary Sort Tree）又称为二叉搜索树、二叉查找树。

1. 二叉排序树的定义

二叉排序树或是空树，或是满足如下性质的二叉树：

1. 若其左子树非空，则左子树上所有结点的值均小于根节点的值；
2. 若其右子树非空，则右子树上所有结点的值均大于等于根节点的值；
3. 其左右子树本身又各是一棵二叉排序树。

举个例子

图1：

1. 左子树上所有结点的值都小于根结点的 45。
2. 右子树上所有结点的值都大于等于根结点的 45。
3. 左右子树显然又是一棵二叉排序树。

图2：

• 再看这个每个结点的元素都是字符串的二叉排序树
• 右子树非空，按照首字母排序，右子树上的所有结点的元素都大于等于根节点。

中序遍历二叉排序树，结果有什么规律？

• 中序遍历：3 12 24 37 45 53 61 78 90 100
• 规律：结果是有序递增的。

二叉排序树的性质：

• 中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的有序递增序列。

2. 二叉排序树的查找

• 因为二叉排序树可以看成是一个有序表，所以在二叉排序树上进行查找和折半查找类似，也是一个逐步缩小查找范围的过程。

二叉排序树所有的左子树的值都小于根结点的值，右子树的值都大于根结点的值。

举个例子

• 若查找的关键字等于根节点，查找成功。
• 否则：
  • 若小于根结点，查其左子树；
  • 若大于根节点，查其右子树。
• 在左右子树上的操作类似。

找 105

1. 先从根结点开始比较，发现要找的值 105 小于 根节点的值，说明要找的值如果存在，则一定在左子树。
2. 再和左子树的根结点比较，105 大于 99，则说明要到右子树去找了。
3. 依次类推，105 小于 110，去左子树，哦豁终于找到你了。

找 103

• 按照上面的步骤一直往下找，最后找到105的左子树，发现105的左子树为空，查找失败，返回空指针。

二叉排序树算法

算法步骤

1. 若二叉排序树为空，则查找失败，返回空指针。
2. 若二叉排序树非空，将给定值 key 与根节点的关键字 T->data.key 进行比较：
   • 若 key 等于 T->data.key，则查找成功，返回根结点地址；
   • 若 key 小于 T->data.key，则递归查找左子树；
   • 若 key 大于 T->data.key，则递归查找右子树。

二叉排序树的存储结构

算法描述

//在根结点指针 T 所指二叉排序树中递归查找某关键字等于 key 的数据元素
//若查找成功，则返回指向该数据元素结点的指针，否则返回空指针BSTree SearchBST(BSTree T,KeyType key)
{if((!T)||key == T->data.key)//树为空或根节点的值等于要查找的值{return T;//查找结束}else if(key < T.data.key){return SearchBST(T->lchild,key);//在左子树中继续查找}else{return SearchBST(T->rchild,key);//在右子树中继续查找}
}

二叉排序树算法分析

• 查找某个值要比较的次数，和要查找的这个结点在二叉排序树当中的位置有关。
  • 找第一层的结点第一次比较就找到了，找位于第二层的结点的话两次比较就行了。找位于第四层的 35 就需要比较 4 次。
  • 每一个结点需要比较的次数，和这个结点在二叉排序树当中的层数有关。
• 二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。
  • 比较的关键字次数 = 此结点所在层次数。
  • 最多的比较次数 = 二叉排序树的深度。

二叉排序树的平均查找长度：

• 每个结点的比较次数加起来 / 所有结点的个数

• 含有 n 个结点的二叉排序树的平均查找长度和树的形态有关。
  • 树的高度越高，平均查找长度越长，反之越短。
• 最好的情况的树就是判定树。

如何提高形态不均衡的二叉排序树的查找效率？

做 平衡化（平衡二叉树）处理，尽量让二叉树的形状均衡！

• 如果选择中间数作为根节点，可以保持树左右子树的相对平衡；
• 关键是根节点选哪个，如果选个小的，自然就有更多的元素跑到右子树，相对来说层次加深。

3. 二叉排序树的插入

举个栗子

1. 如果我们要插入的元素小于根结点，则往左子树上插。
2. 同样的，到了左子树之后，如果要插入的值比当前的根节点 12 大，则往右子树插。
3. 到了 12 的右子树 37 之后，发现 37 小于 40，往右子树插，又发现 37 的右子树为空，此时就在 37 的右孩子处安家了。

算法步骤

1. 若二叉排序树为空，则待插入结点 *S 作为根节点插入到空树中。
2. 若二叉排序树非空，则将 key 与根结点的关键字 T->data.key 进行比较：
   • 若 key 小于 T->data.key，则将 *S 插入左子树；
   • 若 key 大于 T->data.key，则将 *S插入右子树。

• 插入的元素一定在叶子结点上。

算法描述

//当二叉排序树 T 中不存在关键则等于 e.key 的数据元素时，则插入该元素void InsertBST(BSTree &T,ElmeType e)
{if(!T)//找到插入位置，递归结束{S = new BSTNode;//生成新结点 *SS->data = e;//将新结点 *S 的数据域置为 eS->lchild = S->rchild = NULL;//新结点*S作为叶子结点T= S；//将新结点 *S 连接到已找到的插入位置}else if(e.key < T-> data.key){InsertBST(T->lchild,e);//将*S插入左子树}else{InsertBST(T->rchild,e);//将*S插入右子树}
}

4. 二叉排序树的生成

二叉排序树的创建是从空的二叉排序树开始的，每输入一个结点，经过查找操作，将新结点插入到当前二叉排序树的合适位置。

举个例子

• 设查找的关键字序列为：{45,24,53,45,12,24,90}
• 可生成二叉排序树如下：
  
• 其中，45 出现了两次，第一次出现在了根结点，所以就没必要再在后面继续插入一个重复的值。

算法步骤

1. 将二叉排序树 T 初始化为空树。
2. 读入一个关键字为 key 的结点。
3. 如果读入的关键字 key 不是输入结束标志，则循环执行以下操作：
   • 将此结点插入二叉排序树 T 中；
   • 读入一个关键子为 key 的结点。

算法描述

//依次读入一个关键字为 key 的结点，将此结点插入二叉排序树 T 中void CreatBST(BSTree &T)
{T = NULL;//将二叉树T初始化为空树cin >> e;//while(e.key != ENDFLAG)//ENDFLAG为自定义常量，作为输入结束标识{InsertBST(T,e);//将此结点插入二叉排序树 T 中cin >> e;}
}

算法分析

• 假设有 n 个结点，则需要进行 n 次插入操作；
• 而插入一个结点的时间复杂度为 O(log₂n)；
• 所以创建二叉排序树算法的时间复杂度为 O(nlog₂n)。

构造二叉排序树的特点

1. 一个无序序列可以通过构造二叉排序树而变成一个有序序列。
   • 构造树的过程就是对无序序列进行排序的过程。
   • 构造好一棵二叉排序树之后，对它进行中序遍历，就能到到一个有序递增的序列。
2. 插入的结点均为叶子结点，故无需移动其他结点。相当于在有序序列上插入记录而无需移动其他记录。
3. 如果关键字的输入顺序不同，建立的二叉排序树的形态是不一样的（查找效率也会不同）。
   • 初始的时候以中位数为开头进行生成，可以获得深度较小的二叉排序树。
   • 相对来说，取中位数作为根节点，这个树的层次会浅，即查找效率高一点。

5. 二叉排序树的删除

• 从二叉排序树汇总删除一个结点，不能把以该节点为根的子树都删去；只能删除该结点，并且还应该保留删除后所得到的二叉树任然满足二叉排序树中性质不变。
• 由于中序遍历二叉排序树可以得到一个有序递增的序列。那么，在二叉排序树中删除一个结点相当于删去有序序列中的一个结点。
  • 将因删除结点而断开的二叉链表重新链接起来；
  • 防止重新链接后树的高度增加。

算法步骤

下面分 3 中情况进行讨论

1. 被删除的结点是叶子结点：直接删除该结点。
   • 将其双亲结点中相应指针域的值改为 空。
   • 如：20 是30 的左孩子，将 30 的左孩子指针置空，88 同理。

2. 被删除的结点只有左子树或者只有右子树，用其左子树或者右子树替换它（结点替换）。
   • 其双亲结点的相应指针域的值改为指向被删除结点的左子树或右子树（孙子变儿子）。
   • 如：删除 40，该结点没有右孩子，直接让 40 的双亲结点 30 的右指针域指向 35 即可，让 35 成为 30 的右子树。
   • 删除 80 同理，该结点没有左孩子，直接让 80 的双亲结点 50 的右指针域指向 90 ，让 90 成为 50 的右子树。

3. 被删除的结点即有左子树，又有右子树。
   • 既要删除结点，又要保证新的二叉排序树的中序遍历序列是有序递增的。

• 方法1：以其中序前趋值替换之（值替换），然后再删除该结点的前趋结点。前趋是左子树中最大的结点。
  • 前趋代替：左子树最右结点
  • 如果40既有左子树，又有右子树，说明不是50的直接前趋，要找50的直接前趋结点。
  • 用 40 代替了 50 之后就要将原来的 40 删了，将 40 删除的方法无外乎就是目前为止提到的 3 种删除结点的方法。

• 方法2：也可以用中序遍历的后继来替换它，然后在删除该结点的后继结点。后继是右子树中最小的结点。
  • 后继代替：右子树最左结点。
• 总结：左边用最大，右边用最小

7.3.2 平衡二叉树

如何提高形态不均衡的二叉排序树的查找效率？

• 解决办法：做 平衡化（平衡二叉树）处理，尽量让二叉树的形状均衡！

  • 如果选择中间数作为根节点，可以保持树左右子树的相对平衡；
  • 关键是根节点选哪个，如果选个小的，自然就有更多的元素跑到右子树，相对来说层次加深。

1. 平衡二叉树的定义

平衡二叉树（Balanced Binary Tree）

• 又称为 AVL 树（Adelson - Velskii and Landis）。
• 一棵平衡二叉树要么是空树，要么是具有下列性质的二叉排序树：
  1. 左子树和右子树的高度之差的绝对值小于等于1；
  2. 左子树和右子树也是平衡二叉排序树。
• 为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子（BF）。
  • 平衡因子 = 结点左子树的高度 - 结点右子树的高度。
  • 根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能是：-1、0，或 1。

举个例子

• 对于一棵有 n 个结点的 AVL 树，其高度保持在 O(log₂n) 的数量级，ASL（平均查找长度） 也保持在 O(log₂n) 量级。

2. 平衡二叉树的平衡调整方法

• 当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，即出现平衡因子绝对值大于1的结点，如：2、-2。

• 如果在一棵 AVL 树中插入一个新结点后造成失衡，则必须重新调整树的结构，使之恢复平衡。

最小失衡子树

• 有时候添加一个结点之后，造成的失衡结点不止一个时，选择最小的失衡子树。
• 找离着插入结点最近且平衡因子绝对值超过 1 的祖先结点，以该节点为根的子树称为最小失衡子树。
• 找最小失衡子树其实是因为只要调整了这个子树，一般可以使上面的那些失衡结点也平衡，因为导致失衡的根本原因是插入结点

平衡调整的四种类型：

把需要调整的四种失衡形态表示成这样，分别研究一下怎样将失衡情况扭转回来。

1. LL型：插入在结点左子树的左子树上而造成该结点失衡，这种失衡类型称为 LL型（左左型）。
   • 将失衡结点 A 的左孩子 B 作为根节点，其余结点按照二叉排序树规则接在上面。
2. LR型：插入在结点左子树的右子树上而造成该结点失衡，这种失衡类型称为 LR型（左右型）。
   • 将失衡结点 A 的左孩子的右孩子 C 作为根节点，其余结点按照二叉排序树规则接在上面。
3. RL型：插入在结点右子树的左子树上而造成该结点失衡，这种失衡类型称为 RL型（右左型）。
   • 将失衡结点 A 的右孩子的左孩子 C 作为根结点，其余结点按照二叉排序树规则接在上面。
4. RR型：插入在结点右子树的右子树上而造成该结点失衡，这种失衡类型称为 RR型（右右型）。
   • 将失衡结点 A 的右孩子 B 作为根结点，其余结点按照二叉排序树规则接在上面。

调整原则

1. 降低高度。
   2.保持二叉排序树性质：比根小的放左子树，比根大的放右子树 。

LL型调整

新结点的插入位置在失衡结点的左子树的左子树上。

• 取这三个结点的中间值 B 作为根结点升上去。
• 然后根据二叉排序树的性质：将比根小的结点放左子树，比根大的结点放右子树。

举个例子

1. 将这三个结点的中间值 4 作为根结点升上去。
2. 然后根据二叉排序树的性质，比根小的 2 放左子树，比根大的 5 放右子树。

RR型调整

新插入的结点在失衡结点的右子树的右子树上。

• 根据二叉排序树的性质找出这三个结点的中间值 B 作为根节点。
• 根据二叉排序树的性质，A 为左孩子，β 作为右孩子。
• 其余结点一律根据性质自己找地方猫着。

举个例子

以失衡结点为起点，找出右子树的根结点，以及右子树的右子树的根结点

1. 找到中间值 6，然后将中间值升上去作为根结点。
2. 其余结点按照二叉排序树的性质排序。

LR型调整

新插入的结点在失衡结点的左子树的右子树上。

• 找出这三个结点的中间值 C 作为根节点升上去。
• 根据二叉排序树的性质：让 B 为左孩子，A 为右孩子。
• 其余节点按照二叉排序树的性质自己找位置待着。

举个例子

1. 将中间值 7 作为根节点，呲溜一下提上去。
2. 根据二叉排序树性质：3 为左孩子，16 为右孩子。

RL型调整

新插入的结点在失衡结点的右子树的左子树上。

• 根据二叉排序树性质或中序遍历找出 A C B 的排序，将中间值 C 置为根接单，A 为左孩子，B 为右孩子。

举个例子

1. 新插入的结点在失衡结点的右子树的左子树上，由此判断是RL型。
2. 分别找出失衡结点 7、根节点的右孩子 11、根节点的右孩子的左孩子 9，由此得出失衡的树。
3. 按照中序遍历的方式排得出序列为：7 9 11.
4. 将中间值 9 作为根节点，7 作为左孩子，11 作为右孩子。
5. 其余结点按照二叉树性质找地方挂着。

3. 构造平衡二叉排序树

输入关键字序列（16，3，7，11，9，26，18，14，15），给出构造一棵 AVL （平衡二叉排序树）的步骤。（要根据二叉排序树的性质插入结点）

1. 先输入第一个值 16，然后计算它的平衡因子。平衡因子为 0 可以继续插入输入后续结点。
2. 输入第二个结点 3，到根节点的左孩子，计算这两个结点的平衡因子，没有失衡，无需调整继续构造。

3. 输入第三个结点 7，比 16 小，比 3 大，放到 3 的右子树上，此时结点 16 失衡，调整二叉排序树：
   • 造成失衡的结点 7 在失衡结点 16 的左子树的右子树上，判断为 LR型。
   • 选出这三个结点的中间值 7 为根结点，将 3 置为左孩子，16 置为右孩子，调整完毕，继续输入元素。

4. 输入第四个结点 11，继续计算平衡因子。

5. 输入第五个结点 9，计算平衡因子，此时结点 16 失衡。
   • 取最小失衡子树，判定为 LL型。
   • 取最小失衡子树 16，11 ，9 三个结点的中间值 11 为根节点，9为 11 的左孩子，16 为右孩子。

6. 插入第六个结点 26，此时结点 7 失衡。
   • 造成失衡的结点 26 在失衡结点的右子树的右子树上，判定为 RR型。
   • 取7，11，16 的中间值11为根，7 为左孩子，16 为右孩子。其余结点根据二叉排序树的性质排列在树中。

7. 输入第七个结点 18 到 26 的左孩子处，检查平衡因子，此时结点 16 失衡了。
   • 结点 18 插入在失衡结点 16 的右子树的左子树上，判定为 RL型
   • 将失衡子树 16，26，18 的中间值 18 换成根结点，16 、26 分别为左、右孩子。

8. 插入第八个结点 14 至结点 16 的左孩子处。

9. 插入第九个结点 15 至结点 14 的右子树上，此时结点 16、18、11 均失衡。
   • 取最小失衡子树 16，14，15 来判定失衡类型为 LR型。
   • 取最小失衡子树的中间值 15 为根结点，15、16 分别为左、右子树。

AVL 树构造完成