第七章：二叉搜索树

第七章：二叉搜索树

概述

循关键码访问

顺序性：BST中任一节点均不小于其左后代，不大于其右后代。

满足上述顺序性的二叉树就是BST，然而虽然BST的任一节点均不小于其左孩子，不大于其右孩子，然而满足这个条件的却未必是二叉树。比如一棵二叉树，根结点是2，左孩子是1,1的右孩子是3，尽管满足父结点与孩子结点之间的顺序性，却不满足祖先与后代间的顺序性，故不是BST。

BST的充要条件：中序遍历序列（垂直投影）单调非降。

BST的接口直接派生自二叉树类，重写了查找、插入、删除等接口。

BST查找

BST的查找过程类似于有序向量的二分查找。从根结点出发，待查找节点大于当前节点则向右子树深入，小于当前节点则向左孩子深入，等于则返回当前节点，查找成功。如果查找到最后一直深入到空树，则查找失败。

实现：

代码中的hot总是记下了每次深入访问之前的父结点，故不论查找成功还是失败，hot最终都指向最后返回结点的父节点。

BST插入

在BST的查找操作中，search接口返回了查找成功或者失败的位置，而hot则指向命中节点的父亲，所以可以直接调用search函数找到待插入元素的位置，并将其作为hot的孩子接入BST。

正因为如此，BST新插入的节点总是叶子节点。

BST删除

删除操作的主算法与插入操作类似，通过search接口找到待删除的元素，执行删除操作。

下面需要考虑的问题就是如何实现removeAt接口？

不妨以上图的BST为例。待删除的节点e有三种可能情况：

其一，e只有右子树。比如要删除11，由于11没有左孩子，只需将11的右子树替换掉11即可，替换掉之后，由于除了11的右子树外其它节点未进行调整，故11左边的元素依旧小于右边的元素，11右子树右边的元素依旧大于11的右子树，BST的顺序性依旧满足。

其二，e只有左子树，比如要删除15，只需将15的左孩子替换掉15即可。

也就是说，当e的度为1时，只需将其唯一的子树替换掉e即可完成删除操作。

更一般的说，即使e的度为0，即e是叶子节点，依旧可以执行上述操作，代以e的将是空节点。

其三：e左右孩子并存。比如删除根结点16，要想维持BST的顺序性，需要找到一个节点顶替被删除的节点，该节点要满足既大于16的左子树节点，又要不大于e的右子树节点，这样的节点也就是e在BST中序遍历下的后继节点。中序遍历下e的后继节点的查找需要先深入到e的右孩子，然后沿左侧链深入找到最左侧的节点即是中序遍历下的后继结点。（这里由于前提是e的左右孩子均存在，所以无需考虑e没有右孩子的情况）。16的后继节点就是17，交换两个节点，之后删除17就转化为上面两种情况了。

这里的w一开始是需要删除的节点x，通过succ函数找到其在中序遍历下的后继后，w指向该后继，并交换w和x的数据域，这个O（1）的交换操作使得需要删除的节点变成了 w，而交换操作并未改变指针，x仍是指向原来要删除元素的位置，w还是指向x在中序下的后继。之后要做的操作无非是删除w。不妨用u记录下w的父节点位置。

w是x的中序下的后继，按照之前所分析的，应先找到x的右孩子，再沿着左侧链向左找到最左的节点。第一种情况是x的右孩子没有左孩子，所以此时x的右孩子就是x的后继，即需要删除的是w元素，w只可能含有右子树，于是用w的右子树替掉w的位置即可；第二种情况是x的右孩子有左孩子，沿着左侧链往下，此时w一定没有左孩子，同样是用w的右子树替换掉w。不同的是，第一种情况，w的父结点u等于x，w处在u的右孩子位置，所以用w的右子树替换掉w，即替换掉u的右子树；第二种情况，w是左侧链下来找到的，必定是u的左孩子，所以需要用w的右子树替换掉u的左孩子。

BST删除操作总的代码如下：

template <typename T> bool BST<T>::remove ( const T& e ) { //从BST树中删除关键码e
   BinNodePosi(T) & x = search ( e ); if ( !x ) return false; //确认目标存在（留意_hot的设置）
   removeAt ( x, _hot ); _size--; //实施删除
   updateHeightAbove ( _hot ); //更新_hot及其历代祖先的高度
   return true;
} //删除成功与否，由返回值指示

template <typename T>
static BinNodePosi(T) removeAt ( BinNodePosi(T) & x, BinNodePosi(T) & hot ) {
   BinNodePosi(T) w = x; //实际被摘除的节点，初值同x
   BinNodePosi(T) succ = NULL; //实际被删除节点的接替者
   if ( !HasLChild ( *x ) ) //若*x的左子树为空，则可
      succ = x = x->rc; //直接将*x替换为其右子树
   else if ( !HasRChild ( *x ) ) //若右子树为空，则可
      succ = x = x->lc; //对称地处理——注意：此时succ != NULL
   else { //若左右子树均存在，则选择x的直接后继作为实际被摘除节点，为此需要
      w = w->succ(); //（在右子树中）找到*x的直接后继*w
      swap ( x->data, w->data ); //交换*x和*w的数据元素
      BinNodePosi(T) u = w->parent;
      ( ( u == x ) ? u->rc : u->lc ) = succ = w->rc; //隔离节点*w
   }
   hot = w->parent; //记录实际被删除节点的父亲
   if ( succ ) succ->parent = hot; //并将被删除节点的接替者与hot相联
   release ( w->data ); release ( w ); return succ; //释放被摘除节点，返回接替者
}

删除操作的hot最终会指向实际被删除节点的父节点。

平衡与等价

n个互异节点随机组成的BST，一共有Catalan（n）棵。

推导与栈混洗的推导类似，设一棵二叉树由1,2,3，…，n这些节点组成，则k号结点作为根节点时，左子树有k – 1个节点，右子树有n – k个节点。可以得到上图所示的公式。

由于随机组成的BST中越低的BST容易多次被统计，所以认为BST的平均高度是根号n更为可信。

等价BST是指中序遍历序列相同的BST。

这里为了进行等价变换所作的旋转调整分为zig和zag。

zig（v）表示将v节点顺时针旋转，用其左孩子作为旋转后v的父节点；

zag（v）表示将v节点逆时针旋转，用其右孩子作为旋转后v的父节点。

总而言之，不论对v做何种旋转，v的深度必然增加1,。

AVL树-重平衡

AVL树平衡因子 = 左子树高度 – 右子树高度。

所有节点平衡因子的绝对值不超过1的BST称为AVL树。

需要注意这里对平衡因子的定义，比如上图的1节点，左右子树均为空树，高度都是-1，所以1的平衡因子为0，而2的左子树高度为0，右子树高度为-1，平衡因子为1.

要证明AVL树的高度在渐进意义上是logn级别。先考察固定高度h，节点树最少的AVL树。

设高度为h的AVL树最少节点数为S（h），可以确定的是，其左右子树也均是AVL树。

既然树高为h，则左右子树至少有一棵高度是h – 1，不妨设左子树高度为h – 1.要实现AVL树节点数最少，需要在维持平衡的条件下使左右子树的节点数尽可能的少，因此，左子树应该是一棵高度为h – 1的节点数最少的AVL数，其节点数为S（h - 1）；维持平衡要求右子树的高度为h – 1或者h – 2，节点数尽可能少自然让右子树高度为h – 2，其节点数为S（h - 2）。

故可以得到递推式S（h） = S(h – 1) + S(h – 2) + 1,等式两边加一得S(h) + 1 = [S(h – 1) + 1] + [S(h – 2) + 1]。令T（n） = S（n） + 1，得到T（n） = T（n - 1） + T（n - 2）。即S（h） + 1是斐波那契数列中的某一项。高度为0的AVL树至少有1个节点，对应fib（3） - 1 = 1，高度为1的AVL树至少有2个节点，对应fib（4） - 1 = 2.（注意：这里fib（0） = 0，fib（1） = fib（2） = 1），可以推出S（h） + 1 = fib（h + 3），即S（h） = fib（h + 3） - 1.

高度为h的AVL树至少有fib（h + 3） - 1个节点，则节点树为n的AVL树高至多为logn。

（这里n = fib（h + 3） - 1约等于1.618^(h + 3) - 1）.

对于插入操作而言，新插入的节点必然是叶节点，引起失衡必然是在深度较大的一个分支下插入了引起祖父节点左右失衡，祖父节点的高度因此加一，于是可能会引起祖先节点一系列的失衡，比如插入M节点。

删除操作引起失衡是因为删除了深度较小的分支的节点，引起了父节点及其以上某个节点的失衡，但是失衡节点的高度未受影响，所以不会影响其他祖先，因此删除操作至多有一个祖先会失衡。

AVL树-插入

我们知道，在AVL树中插入一个节点x，如果引发了失衡，必然是祖父及其更早的祖先节点才会失衡。（原因很简单，插入的x作为叶结点，其父节点如果原本是叶结点，那么不会失衡，如果x的父节点不是叶结点，则至多只有一个孩子，同样不会失衡）。

设g表示插入x后失衡节点的最深者，g不低于x的祖父节点，在g到x的通路中，设p为g的孩子，v为p的孩子，则只需对这祖孙三个节点做等价变换即可使AVL树重新恢复平衡。

第一种情况，p是g的右孩子，v是p的右孩子。此时比如在v的左子树上插入了一个节点使得g的平衡因子变成了-2。我们需要把g的右子树往上提点来恢复平衡，为此，只需对g做zag变换，将g的右孩子p作为g的父节点。如上图所示，zag旋转后p作为顶替g的节点其高度与插入x之前g的高度一致，故更高的祖先节点也将恢复平衡。

第二种情况，p是g的左孩子，v是p的左孩子，只需对g做zig旋转同样可恢复平衡。

这两种情况只需做一次旋转就能恢复平衡的称为单旋。

上图中p是g的右孩子，v是p的左孩子。不妨先对p做一次zig旋转，使得v成为g的右孩子，p成为v的右孩子，问题就转化为了单旋的情况了，这时，再对g做一次zag旋转，AVL树便可再次恢复平衡。这种通过两次单旋恢复平衡的操作叫做双旋，这里叫做zig-zag旋转。

另一种情况p是g的左孩子，v是p的右孩子，此时先对p做一次zag旋转，再对g做一次zig旋转即可恢复平衡，成为zag-zig旋转。

总而言之，zig-顺时针旋转，zag-逆时针旋转，不管哪种旋转都是将某个结点从根节点的位置上旋下来，以其孩子节点替之。

 

AVL树-删除

删除操作与插入操作有很大的不同，首先，如果一个节点左子树高度为1，右子树高度为0，我们把它的右孩子x删除了，致使该节点的平衡因子变为2，插入操作的失衡是从x的祖父节点开始的，而删除操作则可能从x的父节点就可能失衡。正因为如此，从g到x的父节点路径上可能就一个节点，故我们不能再从该路径上取p和v节点了。

教材中给出了p、v节点的选取策略。概括一下就是先找到失衡节点，其子树中包含删除节点x的一侧在删除x后导致另一侧的高度要高两层故不含x的那一侧g的孩子设定为p，而p可能含有两个孩子，两个孩子中更高者选为v，一样高则选取v与p同向者。

与插入类似，一旦找到了g，p，v，如果它们同向就可以做一次单旋操作。比如上图因为g的右子树高度降低了，我们对g做一次zig选择，使其变为p的右孩子。此时虽然g恢复了平衡，但是p节点的高度可能因此少了1，从而引发更高祖先节点的失衡，也就是失衡传播。

以上图为例，p的右子树更高，故选取p的右孩子作为v，先对p做一次zag旋转，再对g做一次zig旋转即可恢复平衡，此时v的高度少了1，因此v的祖先可能失衡。

单旋后局部子树高度可能不变可能降低1，双旋后局部子树高度一定降低1。

实现：

AVL树-（3+4）重构

观察之前的等价变换操作，不论是插入还是删除，单旋还是双旋，所涉及的顶点不过是g、p、v三个以及他们附属的四棵子树，而重构后恢复平衡的树都具有一个特征。即g、p、v中大小位于中间的是根结点，另外两个根据大小关系分别位于左右孩子节点，其它的四棵子树也均按照中序遍历的次序严格的排列着，由此，可以将所有的选择调整操作封装为一个函数。这种统一的操作只涉及三个节点，四棵子树，故被称为3 + 4重构。

重构函数的实现

下一步操作即需要找到三个节点及其子树，不妨传入v节点，通过对父节点的引用即可找到p和g节点。

需要根据四种旋转调整的结构依次给connect34函数传参，比如zig-zig调整时，v < p < g，子树顺序也自左向右依次传入。上图的第二种情况应是zag-zig旋转，可能是课件的笔误。

AVL树综合评价：

优点：各类操作对数的时间，线性的空间。

缺点：其一：为了维护平衡因子，需额外封装；其二：实际复杂度要高于理论的，比如删除操作引起失衡传播可能要进行logn次调整；其三：单次调整可能影响logn个节点的结构。