数据结构-第七章（树型查找）

注：在写这个的时候，是在期末考试。而且复习已经到了第三本（计组）了。可能知识点没有之前有逻辑。但是会尽量完整。

前提引言：

顺序查找、折半查找、分块查找都是对线性表进行查找操作，它是静态查找表。即我们一般不对它进行插入和删除操作，因为如果是无序的，插入删除很方便但是查找的效率过低；如果是有序的，折半查找的效率不错但是插入删除太麻烦，所以我们下面要讨论的诸多树型查找就是动态查找表，它们方便进行插入删除操作的同时查找效率也不错。值得一提的是，它们是我们为了方便查找而定义的一种逻辑结构，属于是面向查找操作的数据结构，那么我们对它们复杂的定义也不足为奇了，这里点名红黑树。

1.二叉排序树（BST）

思维导图（前提）

1.1二叉排序树的定义

二叉排序树又称为BST，二叉搜索树，二叉排序树。

1.2BST的查找 

递归的思想：二叉排序树的查找是从根结点开始，沿某个分支逐层向下比较的过程。若二叉排序树非空，先将给定值与根结点的关键字比较若相等，则查找成功；若不等，如果小于根结点的关键字，则在根结点的子树上查找，否则在根结点的右子树上查找。

如下图：

代码如下： 

 知识点：递归的代码同样简单，但效率更低。

1.3BST的插入

理解：二叉排序树作为一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找的过程中，当树中不存在关键字值等于给定值的结点时再进行插入的。

插入结点的过程如下：

1. 若原二叉排序树为空树，则直接插入结点；
2. 若关键字k小于根结点的值，则插入到左子树，若关键字k大于根结点的值，则插入到右子树。插入的结点一定是一个新添加的叶结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子。

代码：

 知识点：可以看到插入的效率和查找相同，不需要移动其他记录的位置，它表明，二叉排序树既拥有类似于折半查找的特性，又采用了链表作为存储结构，因此是动态查找表的一种适宜表示。

1.4BST的构造

过程：从一颗空树出发，依次输入元素，将它们插入二叉排序中的合适位置。

过程如下图：

代码：

1.5BST的删除

需要使删除结点后的树仍满足二叉排序树的特性，删除操作的过程分3种情况讨论：

特别第三种：若被删除结点z有左子树和右子树，则让z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换为了第一种或第二种情况 

注意点：如果我们按上述操作删除48后再插入48，显然二叉排序树已经不同 

1.6BST的查找效率分析

二叉排序树的查找效率，主要取决于树的高度。

1. 若二叉排序树的左、右子树的高度之差的绝对值不超过1，则这样的二叉排序树称为平衡二叉树，它的平均查找长度为O(logn)。
2. 若二叉排序树是一个只有左(右)孩子的单支树，(类似于有序的线性表)，则其平均查找长度为O(n)。

明确使用(mid=(low+high)/2)时二分查找的判定树唯一，而二叉排序树的查找不唯一，相同的关键字其插入的顺序不同可能生成不同的二叉排序树。

• 当有序表是静态查找表时，宜选择顺序表作为其存储结构，故采用二分查找实现查找操作；
• 当有序表是动态查找表时，宜选择二叉排序树作为其逻辑结构，此时插入删除，查找的时间复杂度都是O(logn)。

例题：

 2.平衡二叉树

前提：思维导图

平衡二叉树（AVL）相对于二叉排序树，知识点较多 

2.1AVL的定义

平衡二叉树又称平衡二叉搜索树，是为了避免构建二叉搜索树时树的高度增长过快，降低其性能，规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过1。又称ALV树，得名于它的发明者G.M.Adelson-Velsky和E.M.Landis。

易错知识点：是高度差不超过1，而不是结点差不超过1。

平衡二叉树是一棵空树，或者是具有以下性质的二叉树：

1. 若左子树非空，则左子树上所有结点的值均小于根结点的值。
2. 若右子树非空，则右子树上所有结点的值均大于根结点的值。
3. 左、右子树也分别是一棵平衡二叉树。
4. 左子树和右子树的高度差的绝对值不超过1

 知识点：结点的平衡因子=左子树高-右子树高

2.2AVL的插入

平衡二叉树保证平衡的基本思想如下：每当在二叉排序树中插入(或删除)一个结点时，

1. 首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。
2. 若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

调整的对象为最小不平衡子树，即其根结点是离插入结点最近，且平衡因子的绝对值超过1的祖先结点的子树。

我们对其进行平衡旋转处理，经过旋转处理后子树深度与插入之前相同，因而不影响插入路径上所有祖先结点的平衡度。

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

• LL平衡旋转：由于在A结点的左孩子结点的左子树插入了新结点，A的平衡因子从1增加到2，此时我们需要进行一次右旋操作，即A的左孩子结点B向右上旋转代替结点A成为根结点，A结点向右下旋转成为根结点B的右孩子结点，而B的原右子树成为结点A的左子树。

 

•  RR平衡旋转：由于在A结点的右孩子结点的右子树插入了新结点，A的平衡因子的绝对值从1增加到2，此时我们需要进行一次左旋操作，即A的右孩子结点B向左上旋转代替结点A成为根结点，A结点向左下旋转成为根结点B的左孩子结点，而B的原左子树成为结点A的右子树。

 

•  LR平衡旋转：由于在A结点的左孩子结点的右子树插入了新结点，A的平衡因子从1增加到2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后把该C结点向右上旋转提升到A结点的位置。

 

•   RL平衡旋转：由于在A结点的右孩子结点的左子树插入了新结点，A的平衡因子的绝对值从1增加到2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后把该C结点向左上旋转提升到A结点的位置。

 

总结四种情况：

2.3平衡二叉树(AVL)的删除

与插入进行对比：

• 与平衡二叉树的插入操作类似，以删除结点w为例来说明平衡二叉树删除操作的步骤：
• 用二叉排序树的删除方法对结点w进行删除操作。
• 从结点w开始，向上回溯，找到第一个不平衡的结点z(还是要对最小不平衡树操作);y为结点z的高度最高的孩子结点；x是结点y的高度最高的孩子结点。
• 然后对以z为根的最小不平衡树进行平衡调整，其中x、y和z可能得位置有4种情况:
• y是z的左孩子，x是y的左孩子(这种情况即为LL,右旋转)
• y是z的右孩子，x是y的右孩子(这种情况即为RR,左旋转)
• y是z的左孩子，x是y的右孩子(这种情况即为LR,先左旋再右旋)
• y是z的右孩子，x是y的左孩子(这种情况即为LR,先左旋再右旋)

然后最小不平衡子树z就被调整为平衡了，但注意此时z的高度可能会减少，因此我们可能需要向上回溯对z的祖先结点进行平衡调整，甚至回溯到根结点(导致树高减1)。这一点与插入不同，插入结点后最小不平衡子树经过旋转处理后子树深度与插入之前相同。

举例删除操作为何类似插入操作：

 下图给出删除操作可能会减少树高的情况: 

总之，插入操作是因为初始左子树低，右子树高，我们往右子树插入导致不平衡，那我们一定可以通过旋转改变树形把这个插入的结点搞到左子树，旋转后整体高度不变。左子树高，右子树低同理。

删除操作是因为初始左子树低，右子树高，我们减少左子树的高度使之打破平衡界限，那我们通过旋转改变树形从右边借了一个结点使左子树的高度恢复，但如果右子树恰好需要这个结点来作为最后一层，我们借过之后右子树的高度减一，旋转后整体高度减一。

2.4平衡二叉树(AVL)的查找效率分析

故求给定结点数的平衡二叉树的查找所需的最多比较次数可以先构造一个该结点树的最高平衡二叉树。  

3.红黑树

注：我初学的时候，也觉得红黑树比较复杂，根据学长介绍，这一节学习的性价比不是很高，这一节的安排是先基本了解，如果有时间的话，再深度推进。（红黑树一般考定义和插入操作，删除操作比较繁琐，真题没有考过）

3.1简略版

性质定义：

 插入操作：

 3.2浓缩版

3.2.1红黑树的定义

 为了保证AVL树的平衡性，我们在插入删除时频繁地调整全树整体的拓扑结构，代价较大。(从目的入手，更好深入）因此，我们对二叉排序树不再进行高度平衡的限制(AVL树)，而进行适度平衡的限制(红黑树)。这样在保证查找效率的同时我们进行插入删除操作所付出的代价也更小，因此红黑树的实际应用更广泛，C++中的map和set(Java中的TreeMap和TreeSet)就是用红黑树实现的。

一棵红黑树是满足如下红黑性质的二叉排序树:

每个结点或是红色，或是黑色的。
根结点是黑色的。
叶结点(虚构的外部结点，NULL结点)都是黑色的。
如果一个结点是红色的，则它的两个子结点都是黑色的。
对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数量相同。 

• 对第3条的解释：与折半查找判定树和B树(它俩的失败结点)类似，为了便于红黑树的实现和理解，引入n+1个外部叶结点，以保证红黑树中每个内部结点的左右孩子均非空。
• 对第4、5条的解释，从根结点到叶结点(不含叶结点)的任何一条简单路径上都至少有一半是黑结点，这两条定义结合起来，所以"任意结点左右子树的高度，相差不超过2倍"。这正是适度平衡的体现。

从某结点出发(不含该结点)到达一个叶结点的任一简单路径上的黑结点总数称为该结点的黑高(记为bh)。根结点的黑高为红黑树的黑高。

结论一：从根结点到叶结点的最长路径不大于最短路径的2倍。
结论二：有n个内部结点的红黑树的高度h≤2log(n+1)。

3.2.2红黑树的插入 

 红黑树的插入过程是二叉排序树的插入过程类似，不同之处在于，红黑树中插入新结点后需要进行调整（包括重新着色和旋转操作），以满足红黑树的性质。

设结点z为新插入的结点，初始色为红色。插入过程如下：

用二叉排序树的插入法插入，若结点z的父结点是黑色，结束。
如果结点z的根结点，将z着为黑色(树的黑高增1)，结束。
如果结点z不是根结点，并且z的父结点z.p是红色的，此时z.p.p为黑色的，z.p的兄弟结点的颜色未知，下面分为三种解决：
①z的叔结点y是黑色的，且z是一个右孩子。
②z的叔结点y是黑色的，且z是一个左孩子。
③z的叔结点y是红色的(z是左或右无所谓)。
结束
对于①z的叔结点y是黑色的，且z是一个右孩子。：(下图为LR,先左旋，再右旋)，旋转同时还要重新着色。

 如果y(T4)是左子树还有一种对称情况(即RL，先右旋，再左旋)。

对于②z的叔结点y是黑色的，且z是一个左孩子。(下图为LL，右旋一次)，旋转同时还要重新着色。

 

如果y(T4)是左子树还有一种对称情况(即RR，左旋一次)

对于③z的叔结点y是红色的(z是左或右无所谓)：z的父结点z.p和叔结点y都是红色的，因为z.p.p是黑色的，将z.p和y都着为黑色，z.p.p着为红色，以在局部保持性质4、5，然后把Z.P.P作为新的结点z来重复循环。

只要满足③的条件，就会不断循环，每次循环指针z都会上移两层，直到根结点或者满足①和②的条件。 

如果y是左子树一样的操作，也对应二个图，不再赘述。

3.2.3红黑树的构造

下面为依次插入5，4，3，2，1时红黑树的构造过程：

3.2.4红黑树的删除 
红黑树的插入操作容易导致两个连续的红结点，破坏定义4。而红黑树的删除操作容易造成子树黑高的变化(删除黑结点会导致根结点到叶结点间的黑结点数量减少)，破坏定义5。

红黑树的删除也是先执行BST树的删除操作，我们知道BST树的删除操作分三种情况，一是无子树，二是只有左或右子树，三是有左右子树，其中第三种情况会转换为前两种情况，因此我们只需讨论前两种情况即可：

为方便对照，先将所有可能性分类，等下填到讨论的两种情况之中。设待删结点为z

1.结点z无子树

1.1结点z为红色；

1.2结点z为黑色；

2.结点z有左子树或右子树

2.1结点z为黑色，只有左子树且必为红色；

2.2结点z为黑色，只有右子树且必为红色；

注：不存在待删结点z为红色时有单一子树这种情况

3.结点z有左右子树

3.1 直接后继(前驱)结点y来替换黑色结点z并且y为红色无子树。

3.2 直接后继(前驱)结点y来替换黑色结点z并且y为黑色无子树

3.3 直接后继(前驱)结点y来替换红色结点z并且y为红色无子树。

3.4 直接后继(前驱)结点y来替换红色结点z并且y为黑色无子树。

3.5 直接后继(前驱)结点y来替换黑色结点z并且y为黑色只有左子树。

3.6 直接后继(前驱)结点y来替换黑色结点z并且y为黑色只有右子树。

3.7 直接后继(前驱)结点y来替换红色结点z并且y为黑色只有右子树。

3.8 直接后继(前驱)结点y来替换红色结点z并且y为黑色只有右子树。

待删结点只有右子树或左子树。z的子树只有一个孩子结点，该结点必然为红色，否则会破坏定义

5，我们进行下图这样的转换即可。2.1、2.2、3.5、3.6、3.7、3.8都属于此情况。对于3.7、3.8我们用y来替换z时注意黑色变成红色。

待删结点没有孩子  

• 如果待删结点没有孩子，且结点是红色的，直接删除，结束。对应1.1、3.1、3.3
• 如果待删结点没有孩子，且结点是黑色的。下面进行讨论分析。对应1.2、3.2、3.4

删除y(1.2时为y为z本身)后将导致先前包含y的任何路径上的黑结点数量减1，因此y的任何祖先都不再满足定义5。
简单的修正方法就是删除y时把现在占有y位置的x结点视为还有额外一重黑色，定义为双黑结点。(因为y是终端结点所以x是空叶结点)
也就是说，如果将任何包含结点x的路径上的黑结点数量加1，在此假设下，定义5得到满足，但破坏了定义1(不能存在双黑结点)，于是，删除操作的任务就转化为将双黑结点x恢复为普通结点。
分以下四种情况，区别在于x的右兄弟结点w及w的孩子结点的颜色不同：

情况1：x的兄弟结点w是红色结点。

w必须有黑色父结点和黑色孩子结点。交换w与父结点x.p的颜色，然后对x.p做一次左旋，不会破坏红黑树的任何规则。现在，x的新兄弟结点是旋转之前w的某个孩子结点，其颜色为黑色，下面要继续讨论新兄弟w的状态，这样就将情况1转换为了情况2、3、4。

情况2：x的兄弟结点w是黑色结点，且w的右孩子是红色

(下图对应RR，左旋一次)即红结点是其爷结点的右孩子的右孩子。交换w和父结点x.p的颜色，把w的右孩子着为黑色，并对x的父结点x.p做一次左旋，然后使x变为单重黑色，此时不再破坏红黑树的性质。注：灰色代表红黑均可，不影响该情况。

情况3：x的兄弟结点w是黑色结点，且w的左孩子是红色的，w的右孩子是黑色的。

(下图对应RL,先右旋再左旋)即红结点是其爷结点的右孩子结点的左孩子。交换w和其左孩子的颜色，然后对w进行一次右旋，而不破坏红黑树的任何性质。右旋过后x的新兄弟结点的右变为了红色，这样就变为了情况2，再进行左旋即可。

 情况4：x的兄弟结点w是黑色结点，且w的两个孩子结点都是黑色的。

因w和x都是黑色的，我们可让x和w都去掉一层黑色，即w变为红色，x变为正常结点，为了保持局部的黑高不变，我们让x.p变为双黑结点。然后将x.p作为新的x结点来循环。如果是通过情况1进入情况4的，因为原来的x.p是红色的，将新结点变为黑色，终止循环，结束。

我们上图假设了x为左孩子结点，当x为右孩子结点时处理方式左右对称，不再赘述。

情况1、2、和3在各执行常数次的颜色改变和至多3次旋转后便终止，情况4是可能重复执行的唯一情况，每执行一次指针x上升一层，至多O(logn)次。