二叉搜索树

发表于 分类于

任何词条之间可相互比较大小是有序向量得以定义，以及二分查找赖以成立的基本前提。通过对二分查找策略的抽象和推广，定义和实现二叉搜索树结构。二叉搜索树有诸多变种，各具特色，各有所长，也有各自适用范围。为有效控制树高，二叉树的性能主要取决于树高，故应在节点数目一定的情况下尽可能地减小树高，相应地，尽可能使兄弟子树地高度彼此接近，即全树尽可能地平衡。平衡二叉搜索树通过对树中每一局部增加某种性质来保证二叉树的适度平衡性。

查找，即按照事先约定的规则，从数据集合中找出符合特定条件的对象，属于基本的静态操作。

基本的数据结构(列表和向量)并不能高效地兼顾静态查找和动态修改操作。

基本结构 查找 插入/删除
无序向量 $O( n )$ $ O( n )$
有序向量 $O(logn)$ $ O(n)$
无序列表 $O( n )$ $O(1)$
有序列表 $O(n)$ $O(n)$

二叉搜索树

顺序性

在所谓的二叉搜索树中，处处都满足顺序性：

任一节点r的左(右)子树中，所有节点(若存在)，均不大于(不小于)r

为了回避边界情况，暂且假定所有节点互不相等，于是上述顺序性可简化表述为：

任一节点r的左(右)子树中，所有节点(若存在)，均小于(大于)r

当然，在实际应用中，对相等元素的禁止既不自然也不必要，可以对现有结构进行扩展，使二叉搜索树的接口支持相等词条的同时并存。

单调性

在微观上满足顺序性，在宏观上满足单调性，单调性：

BST的中序遍历序列，必然单调非降

考查二叉树中的任一节点$r$，按照中序遍历的约定，$r$左(右)子树中的节点(若存在)均应先于(后于)r接受访问。

按照二叉搜索树的定义，$r$左(右)子树中的节点(若存在)均不大于(不小于)$r$，故中序遍历序列必然在r处单调非降，反之亦然。

鉴于以上所取$r$的任意性，在二叉搜索树中处处成立。

二叉搜索树的定义无法更改为任意节点的左(右)孩子均不大于(不小于)r，即将原来定义中的左(右)后代替换为左(右)孩子。满足这一定义的树未必中序遍历序列单调非降。

查找算法

二叉搜索树的查找算法采取了减而治之的思路和策略，执行过程可描述为：

从树根出发，逐步地缩小查找范围，直到发现目标(成功)或缩小至空树(失败)

对照中序遍历来看，整个过程可视为仿效有序向量的二分查找。

递归版

1
2
3
4
5
6
7
8
template <typename T> BinNodePosi(T) & BST<T>::search ( const T& e ) //在BST中查找关键码e
{ return searchIn ( _root, e, _hot = NULL ); } //返回目标节点位置的引用，以便后续插入、删除操作
template <typename T> //在以v为根的（AVL、SPLAY、rbTree等）BST子树中查找关键码e
static BinNodePosi(T) & searchIn ( BinNodePosi(T) & v, const T& e, BinNodePosi(T) & hot ) {
   if ( !v || ( e == v->data ) ) return v; //递归基：在节点v（或假想的通配节点）处命中
   hot = v; //一般情况：先记下当前节点，然后再
   return searchIn ( ( ( e < v->data ) ? v->lc : v->rc ), e, hot ); //深入一层，递归查找
} //返回时，返回值指向命中节点（或假想的通配哨兵），hot指向其父亲（退化时为初始值NULL）

迭代版

1
2
3
4
5
6
7
8
9
10
11
template <typename T> BinNodePosi(T) & BST<T>::search ( const T& e ) //在BST中查找关键码e
{ return searchIn ( _root, e, _hot = NULL ); } //返回目标节点位置的引用，以便后续插入、删除操作
#define EQUAL(e, v)  (!(v) || (e) == (v)->data) //节点v（或假想的通配哨兵）的关键码等于e
template <typename T> //在以v为根的（AVL、SPLAY、rbTree等）BST子树中查找关键码e
static BinNodePosi(T) & searchIn ( BinNodePosi(T) & v, const T& e, BinNodePosi(T) & hot ) {
   if ( EQUAL ( e, v ) ) return v; hot = v; //退化情况：在子树根节点v处命中
   while ( 1 ) { //一般地，反复不断地
      BinNodePosi(T) & c = ( e < hot->data ) ? hot->lc : hot->rc; //确定深入方向
      if ( EQUAL ( e, c ) ) return c; hot = c; //命中返回，或者深入一层
   } //hot始终指向最后一个失败节点
} //返回时，返回值指向命中节点（或假想的通配哨兵），hot指向其父亲（退化时为初始值NULL）

运行时间正比于返回节点v的深度，不超过树高$O(h)$。最好情况下目标关键码刚好出现在树根节点处(或附近)，此时只需$O(1)$时间。最坏情况下，规模为$n$的二叉搜索树深度可能达到$\Omega(n)$,比如该树退化为一条单链时，此时的查找等效于顺序查找。

节点的插入和删除操作都需要首先调用查找算法，并根据查找结果确定后续的处理方式，这里以引用的方式传递(子)树根节点。在成功时指向一个关键码为e且真实存在的节点，失败时，指向最后一次试图转向的空节点null。对于后一情况，可假想地将此节点转换为一个数值为e的哨兵节点，如此，无论命中与否，查找的返回值均等效地指向命中节点,而hot总是指向命中节点的父亲。

无论树的具体形态如何，查找必然有n种成功情况和n+1种失败情况

通过对树高数学归纳可以证明。

假设原有二叉树度数为0、1、2的节点，各有$n_0$,$n_1$,$n_2$个。

在原有二叉搜索树的基础上，引入$n_1+2n_0$个外部节点，可使原有节点度数统一为2，如此，即可将任一二叉搜索树T转化为一棵真二叉树T’。s设T’度数为0、1、2的节点，分别为$n’_0,n’_1,n’_2$。查找失败的情况必定对应于外部节点。

由树的性质，有$e’=n’-1=n’_1+2n’_2$

$n’=n’_0+n_1+n’_2=1+2n_1+n_2$

此时所有节点均为二度节点，则$n’_1=0$

$n’_0=n’_2+1$

注意到此时的零度节点数量即等于引入的外部节点，即$n’_0=n_1+2n_0$

二度节点即为原来的节点总数$n’_2=n_0+n_1+n_2=n$

即$n’_0=n+1$,查找失败的情况总数即是外部节点的数目。

查找成功的情况总数即是二叉搜索树的节点总数$n$,得证。

插入算法

为了在二叉搜索树中插入一个顶点，首先需要利用查找算法search() 确定插入的位置和方式，然后才能将新节点作为叶子插入。

1
2
3
4
5
6
7
template <typename T> BinNodePosi(T) BST<T>::insert ( const T& e ) { //将关键码e插入BST树中
   BinNodePosi(T) & x = search ( e ); if ( x ) return x; //确认目标不存在（留意对_hot的设置）
   x = new BinNode<T> ( e, _hot ); //创建新节点x：以e为关键码，以_hot为父
   _size++; //更新全树规模
   updateHeightAbove ( x ); //更新x及其历代祖先的高度
   return x; //新插入的节点，必为叶子
} //无论e是否存在于原树中，返回时总有x->data == e

这里需要注意，在创建新节点$x$的时候，只是指定了父亲为$hot$，并没有指定$hot$的左孩子还是右孩子为$x$。在前一步的search过程中，返回了命中节点的引用，通过对$x$的赋值来连接父子节点，同时也将$x$接入树中。

插入操作必定在叶节点处，同样取决于节点的深度，在最坏情况下不超过全树的高度，即最深的叶子的深度。

在二叉树树中插入节点v之后，除v的历代祖先外，其余节点的高度无需更新

节点的高度仅取决于其后代，更确切地，是该节点与其最深后代之间的距离。因此在插入节点$v$之后，节点$a$的高度可能发生变化，当且仅当$v$是$a$的后代，或反过来等价地，a是v的祖先。

祖先高度不会降低，但是至多加一

插入节点$v$之后，所有节点的后代集不至缩小。高度取决于后代深度的最大值，故不至于下降。
另外一方面，假定节点$a$的高度由$h$增加至$h’$。若将$v$的父节点记作$p$,则$a$到$p$的距离不大于$a$在此之前的高度，于是必有：

$h’ \leq |ap|+1 \leq h+1$

一旦某个祖先高度不变，则更高的祖先高度也必然高度不变

对于任意节点$p$，若将其左、右孩子分别记作$l$和$r$(可能为空)，则必有：

$height(p)=1+max(height(l),height(r))$

在插入节点$v$之后，在$l$和$r$之间，至多其一可能会(作为$v$的祖先)有所变化。一旦该节点的高度不变，$p$以及更高层祖先(如果存在的话)的高度亦保持不变。

删除算法

单分支情况

若节点x的某一子树为空，则可将其替换为另一棵子树(可能亦为空)，如此操作后，二叉搜索树的拓扑结构依然完整，顺序性同样满足。

双分支情况

l除了更新全树规模和释放被摘除节点外，此时也要更新一系列祖先高度，首个需要更新的祖先恰好为hot。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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; //释放被摘除节点，返回接替者
}

算法操作所需的时间主要消耗于对search()，succ()，updateHeightAbove()的调用。在树的任意高度，它们至多消耗$O(1)$时间，故总体的渐进时间复杂度亦不超过全树的高度。

从二叉搜索树中删除节点，若实际被删除的节点为x,则此后除x的历代祖先外，其余节点的高度无需更新

节点的高度仅取决于其后代，更确切地，是该节点与其最深后代之间的距离。因此在插入节点v之后，节点a的高度可能发生变化，当且仅当v是a的后代，或反过来等价地，a是v的祖先。

祖先高度不会降低，但是至多减一

假设在删除节点x之后，祖先节点a的高度由h变化至h’。假想将x重新插回树中，于是自然地，a的高度应该从h恢复至h，由插入的结论，必有：

$h\leq h’+1$

亦即$h’ \geq h-1$

一旦某个祖先高度不变，更高的祖先也必然高度不变

反正，假设在删除节点x之后，祖先节点高度会间隔地下降和不变。

假想将x重新插入树中，所有节点的高度均应复原，而祖先节点的高度则必然间隔地上升和不变，这一结论与之前插入的结论不一致。

在逐层上行更新祖先高度时，一旦某一祖先的高度不变，便可随即终止。

期望树高

BST主要接口search()，insert()，remove()的运行时间在最坏情况下均线性正比于其高度$O(h)$。

若无法有效控制树高，在最坏情况下，二叉搜索树可能彻底地退化为列表，查找效率降至$O(n)$,线性正比于树(列表)规模。

以下按照两种常用的随机统计方法对BST的平均性能进行分析

随机生成

考察$n$个互异词条${e_1,e_2,..,e_n}$,对任一排列$P=(e_{i1},e_{i2},…,e_{in})$

从空树开始，反复调用insert()接口将各词条依次插入，得到T

与随机序列$P$对应的$T$，称由$P$随机生成。

假定任一排列$P$作为输入的概率均等$1/n!$

则由$n$个互异词条随机生成的二叉搜索树，平均高度为$\Theta(logn)$

随机组成

n个互异节点在遵守顺序性的情况下，可随机确定拓扑联接关系

如此得到的BST，称由这组节点随机组成。

由同一节点组成的二叉搜索树不尽相同，但是中序遍历序列必然相同，不妨记作

$x_0$,$x_1$,$x_2$,…,$x_{k-1}$,$x_k$,$x_{k+1}$,$x_{k+2}$,…,$x_{n-1}$

根据所选树根节点的不同，所有搜索树分为$n$类，对于其中以$x_{k}$为根者而言，左、右子树必然分别由{$x_0$,$x_1$,$x_2$,…,$x_{k-1}$}和{$x_{k+1}$,$x_{k+2}$,…,$x_{n-1}$}组成。

如此，可得边界条件和递推式如下：

$T(0)=T(1)=1$

由$n$个互异节点组随机组成的BST，若共计$T(n)$棵，则有
$$
T(n)=\sum_{k=1}^{n-1} T(k-1)T(n-k)=catalan(n)=\frac{(2n)!}{n!(n+1)!}
$$
假定所有BST等概率出现，则其平均高度为$\Theta(\sqrt n)$

在随机生成的统计方法中，越低的BST被统计多次，故过于乐观。理想随机在实际中并不常见，关键码往往按单调甚至线性的次序出现，极高的BST频繁出现不足为奇。

在目标节点同时拥有左右子树的时候，总是固定选取直接后继与之交换，从二叉树的整个生命周期来看，左子树将越来越倾向于高于右子树，从而加剧整体的不平衡性

一种简捷的策略为除直接后继外还考虑直接前驱，并在二者之间随机选取。

平衡二叉搜索树

二叉搜索树的性能主要取决于树高，故在节点数目固定时应尽可能地降低高度。

节点数目固定时，兄弟子树的高度越接近(平衡)，全树也倾向于更低。

若高度为$h$的二叉树共含$n$个节点，则必有：

$n\leq 2^{h+1}-1$
这里的等号成立，当且仅当是满树。于是有：

$h \geq log_2(n+1)-1 $

$h \geq \lceil log_2{n+1} \rceil-1=\lfloor log_2n \rfloor$

恰好为$\lfloor log_2n \rfloor$时，称作理想平衡。大致相当于完全树甚至满树：叶节点只能出现在最底部的两层。完全二叉树的限制过于苛刻相对二叉树所有可能的形态，此类二叉树所占比例极低，而随着二叉树规模的增大，这一规模还将继续锐减。所以对标准适度放松，依照某种相对宽松的标准，重新定义二叉搜索树的平衡性。

高度在渐进意义上不超过$O(logn)$，故可称作适度平衡。适度平衡的BST，称作平衡二叉搜索树。

等价变换

若两棵二叉树的中序遍历序列相同，则称它们彼此等价。

上下可变

联接关系不同，承袭关系可能颠倒

左右不乱

中序遍历序列完全一致，全局单调非降

各种平衡二叉搜索树(BBST)可视为BST的某一子集，相应地满足限制条件。除了适度平衡性，还具有如下局部性：

  • 单次动态修改操作后，至多$O(logn)$处局部不再满足限制条件
  • 可在$O(logn)$时间内，使这些局部(以至全树)重新满足

刚刚失去平衡的二叉搜索树，必然可以迅速转换为一棵等价的平衡二叉搜索树。等价二叉搜索树之间的上述转换过程，也称作等价变换。

旋转调整

修复局部失衡的最基本手段，就是通过围绕特定节点的旋转，实现等价前提下的拓扑调整。

设$c$和$Z$是$v$左孩子、右子树，$X$和$Y$是$c$的左、右子树。以$v$为轴的zig旋转，如图所示，重新调整这两个节点和三棵子树之间的关系，将$X$和$v$作为$c$的左子树、右孩子，$Y$和$Z$分别作为$v$的左、右子树。

对称地，设$X$和$c$是$v$左子树、右孩子，$Y$和$Z$是$c$的左、右子树。以$v$为轴的zig旋转，如图所示，重新调整这两个节点和三棵子树之间的关系，将$X$和$Y$作为$v$的左子树、右子树，$v$和$Z$分别作为$c$的左孩子、右子树。

zig和zag均属于局部操作，旋转以后中序遍历序列依然不变，故均为等价变换。旋转操作仅涉及常数顶点及其之间的联接关系，故均可在常数时间内完成。

调整之后，$v/c$深度加/减1，子(全)树高度的变化幅度，上下不超过1。实际上，经过不超过$O(n)$次旋转，等价的BST均可相互转化。

规模为n的任何二叉搜索树，经过不超过n-1次旋转调整，都可等价变换为仅含左分支的二叉搜索树，即最左侧通路

任一节点需要通过一次旋转归入最左侧通路，当且仅当它最初不在最左侧通路上。

故原最左侧通路的长度为$s$，则上述算法所做的旋转调整，恰好共计$n-s-1$次。

特别地，$s=0$(根节点的左子树为空),当且仅当需做$n-1$次旋转。

考查二叉搜索树的最左侧通路，从该通路的末端节点$L_d$开始，逐步迭代地延长该路径，直至不能延长。每次迭代，无非两种情况：

  • 若$L_k$的右子树为空，则可令$L_k$上移一层，转至其父节点
  • 若$L_k$的右孩子$R_k$存在，则可以以当前$L_k$为轴，做一次zag旋转调整，如此，$R_k$将作为$L_k$的父亲纳入最左侧通路中。

整个迭代过程的不变性为：

  • 当前$L_k$来自最左侧通路
  • $L_k$的左子树(由不大于$L_k$的所有节点组成)已不含任何右向分支

另外，整个迭代过程也满足如下单调性：

最左侧通路的长度，严格单调增加

故该算法必然终止，且所得的二叉搜索树已不含任何右向分支。

以上思路具体实现如下：

1
2
3
4
5
6
7
8
9
//通过zag旋转调整，将BST子树x拉伸成最左侧通路
template <typename T> void stretchByZag ( BinNodePosi(T) & x ) {
   BinNodePosi(T) p = x; while ( p->rc ) p = p->rc; //最大节点，必是子树最终的根
   while ( x->lc ) x = x->lc; //转至初始最左侧通路的末端
   for ( ; x != p; x = x->parent ) { //若x右子树已空，则上升一层
       while ( x->rc ) //否则，反复地
       x->zag(); //以x为轴做zag旋转
      } //直到抵达子树的根
   }

可见，每做一次zag旋转，总有一个节点归入最左侧通路中，后者的长度也同时加一。最坏情况下，除原根节点外，其余节点均各自对应于一次旋转，累计不过n-1次。

由以上结论推广可知：

规模为n的任何两棵等价二叉搜索树，至多经过2n-2次旋转，即可彼此转换。

AVL树

通过合理设定适度平衡的标准，并借助以上等价变换，AVL树可实现近似理想的平衡。在渐进意义上，AVL树可始终将其高度控制在$O(logn)$以内，从而保证每次查找、插入或删除操作均可在$O(logn)$时间内完成。

任一节点的平衡因子定义为其左、右子树的高度差，即

$balFac(v)=height(lc(v))=height(rc(v))$

空树高度取-1，单节点子树(叶节点)高度取0。

AVL树，即平衡因子受限的二叉搜索树，其中各节点平衡因子的绝对值均不超过1。

1
2
3
#define Balanced(x) ( stature( (x).lc ) == stature( (x).rc ) ) //理想平衡条件
#define BalFac(x) ( stature( (x).lc ) - stature( (x).rc ) ) //平衡因子
#define AvlBalanced(x) ( ( -2 < BalFac(x) ) && ( BalFac(x) < 2 ) ) //AVL平衡条件

高度为$h$的AVL树至少包含$S(h)=fib(n+3)-1$个节点。

固定高度$h$，考查节点最少的AVL树

将这一最小规模记作$S(h)$

$S(h)=1+S(h-1)+S(h-2)$
$S(h)+1=[S(h-1)+1]+[S(h-2)+1]$

当$h$等于0时，T中至少有1个节点，$S(0)+1=fib(3)$

递推关系为$fib(h+3)=fib(n+2)+fib(n+2)$

反过来，由$n$个节点构成的AVL树，高度至多为$O(logn)$。

按照BST规则动态操作之后，AVL的平衡性可能破坏

  • 插入：从祖父开始，每个祖先都有可能失衡，且可能同时失衡
  • 删除：从父亲开始，每个祖先都有可能失衡，但至多一个

通过旋转等价变换恢复平衡，累计操作不过$O(logn)$。

节点插入

插入节点$x$之后，可能有多个失衡节点。插入操作必定位于叶节点处，叶节点的父亲必不失衡，故失衡节点中最低者$g$不低于$x$祖父。

在$x$和$g(x)$的通路上，设$p$为$g(x)$的孩子，$v$为$p$的孩子。$g(x)$是由于$x$的引入而失衡，则$p$和$v$的高度均不会低于各自的兄弟。因此可通过以下宏定义由$g(x)$找到$p$和$v$。

1
2
3
4
5
6
7
#define tallerChild(x) ( \
   stature( (x)->lc ) > stature( (x)->rc ) ? (x)->lc : ( /*左高*/ \
   stature( (x)->lc ) < stature( (x)->rc ) ? (x)->rc : ( /*右高*/ \
   IsLChild( * (x) ) ? (x)->lc : (x)->rc /*等高：与父亲x同侧者（zIg-zIg或zAg-zAg）优先*/ \
   ) \
   ) \
)

这里通过比较子树的高度直接计算。失衡节点的恢复方案取决于节点$g(x)$、$p$、$v$之间具体的联接方向。

单旋

不妨设$p$是$g$的右孩子，$c$是$p$的右孩子。在这种情况下，必定是子树$v$中插入节点$x$，而使$g(x)$不再平衡。逆时针旋转zag(g(x))，$g(x)$必将恢复平衡。对称情况可由zig(g(x))恢复平衡。

双旋

不妨设节点$v$是$p$的左孩子，而$p$是$g(x)$的右孩子。在这种情况下，必定是在子树$v$中插入了新节点$x$，而致使$g(x)$不再平衡。先顺时针旋转zig(p)，再zag(g(x))，$g(x)$必将恢复平衡。

经过局部调整后，局部子树高度也必将复原，$g(x$)以上所有祖先的平衡因子亦将统一地复原。在AVL树中插入新节点后，仅需不超过两次旋转即可使整树恢复平衡。

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T> BinNodePosi(T) AVL<T>::insert ( const T& e ) { //将关键码e插入AVL树中
   BinNodePosi(T) & x = search ( e ); if ( x ) return x; //确认目标节点不存在
   BinNodePosi(T) xx = x = new BinNode<T> ( e, _hot ); _size++; //创建新节点x
// 此时，x的父亲_hot若增高，则其祖父有可能失衡
   for ( BinNodePosi(T) g = _hot; g; g = g->parent ) { //从x之父出发向上，逐层检查各代祖先g
      if ( !AvlBalanced ( *g ) ) { //一旦发现g失衡，则（采用“3 + 4”算法）使之复衡，并将子树
         FromParentTo ( *g ) = rotateAt ( tallerChild ( tallerChild ( g ) ) ); //重新接入原树
         break; //g复衡后，局部子树高度必然复原；其祖先亦必如此，故调整随即结束
      } else //否则（g依然平衡），只需简单地
         updateHeight ( g ); //更新其高度（注意：即便g未失衡，高度亦可能增加）
   } //至多只需一次调整；若果真做过调整，则全树高度必然复原
   return xx; //返回新节点位置
} //无论e是否存在于原树中，总有AVL::insert(e)->data == e

在AVL树中引入一个节点后，失衡的节点可能多达$\Omega(logn)$个。

节点删除

同时至多一个失衡节点，首个可能就是$x$的父亲$hot$

在不包含$x$的一侧，必有一个非空孩子$p$，且$p$的孩子至少为1。于是，可按以下规则从$p$的两个孩子中选出节点$v$

  • 若两个孩子不等高，则$v$取作其中更高者
  • 否则，优先取与$v$与$p$同向者

单旋

在$T_{3}$中删除了节点而使$g(x)$不再平衡，但$p$的平衡因子非负时，通过以g(x)为轴顺时针旋转一次可恢复局部的平衡。

双旋

若$g(x)$失衡时$p$的平衡因子为-1，则经过以$p$为轴的一次逆时针旋转和以$g(x)$为轴顺时针旋转时可恢复局部平衡。

失衡传播

在删除节点后，通过单旋或双旋调整使局部子树恢复平衡，但是恢复平衡后，子树的高度未必可以复原，可能再次失衡。

设$g(x)$复衡后，局部子树的高度的确降低。此时，若$g(x)$原本属于某一更高祖先的更短分支，则因为该分支的进一步缩短，从而致使该祖先失衡，称作失衡传播。失衡传播的方向必然为自底而上，而不至于影响到后代节点。在此过程的任一时刻，至多只有一个失衡的节点；高层的某一节点由平衡转为失衡只可能发生在下层失衡节点恢复平衡之后。因此，可沿parent指针遍历所有祖先，每找到一个失衡的祖先节点，即可套用以上算法使之恢复平衡。

在AVL树中摘除一个节点后，刚刚通过调整使$g(x)$恢复了平衡，此时，若发现$g(x)$原先的父节点依然平衡，在更高层仍可能有失衡的祖先，仅仅通过平衡性不足以确定可否终止自底而上的重平衡过程，转而核对重平衡后节点的高度可判断是否可以立即终止上溯过程。

1
2
3
4
5
6
7
8
9
10
template <typename T> bool AVL<T>::remove ( const T& e ) { //从AVL树中删除关键码e
   BinNodePosi(T) & x = search ( e ); if ( !x ) return false; //确认目标存在（留意_hot的设置）
   removeAt ( x, _hot ); _size--; //先按BST规则删除之（此后，原节点之父_hot及其祖先均可能失衡）
   for ( BinNodePosi(T) g = _hot; g; g = g->parent ) { //从_hot出发向上，逐层检查各代祖先g
      if ( !AvlBalanced ( *g ) ) //一旦发现g失衡，则（采用“3 + 4”算法）使之复衡，并将该子树联至
         g = FromParentTo ( *g ) = rotateAt ( tallerChild ( tallerChild ( g ) ) ); //原父亲
      updateHeight ( g ); //并更新其高度（注意：即便g未失衡，高度亦可能降低）
   } //可能需做Omega(logn)次调整——无论是否做过调整，全树高度均可能降低
   return true; //删除成功
} //若目标节点存在且被删除，返回true；否则返回false

在AVL树中摘除一个节点后，失衡的节点至多一个

节点的平衡与否取决于其左、右子树之差。因此反过来，只要子树的高度不变，则节点不可能失衡。

在删除节点以后自底而上逐层核对平衡因子的过程中，一旦遇到一个失衡节点$v$，则被删除的节点必然来自$v$原来更低的一棵子树，而$v$的高度必然由其另一更高的子树确定，故$v$的高度必然保持不变。由此可知，其祖先节点必然不可能失衡。

在高度为h的AVL树中，任一叶节点的深度均不小于$\lfloor h/2 \rfloor$

对树高做数学归纳。作为归纳基时，$h=1$的情况显然。假设以上命题对高度小于$h$的AVL树均成立。

根据AVL树的性质，此时左、右子树的高度至多为$h-1$，至少为$h-2$。

由归纳假设，在高度为$h-1$的子树内部，叶节点的深度不小于$\lceil (h-1)/2 \rceil \geq \lceil h/2 \rceil -1$

而在高度为$h-2$的子树内部，叶节点的深度也不小于$ \lceil h/2 \rceil -1$

因此在全树中，任何叶节点深度都不至小于

$ 1+(\lceil h/2 \rceil -1)=\lceil h/2 \rceil$

对于任意大的正整数都存在一棵规模为$n$的AVL树，从中删除某一特定节点后的确需要做$\Omega(logn)$次旋转方能使全树恢复平衡。

knuth指出，remove()操作尽管在最坏情况下需做$\Omega(logn)$次旋转，但平均而言仅需0.21次

设在AVL树中摘除一个节点后，刚刚通过调整使g(x)恢复了平衡。此时若发现g(x)原来的父节点恢复了平衡，仍然需要检查更高层的祖先。

仅仅通过平衡性，并不足以确定可否及时终止自底而上的重平衡过程。转而核对重平衡后节点的高度，即可及时判断是否可以立即停止上溯过程。

AVL的插入操作，可以在首次重平衡后随即终止上溯，原因在于此时不仅局部子树的平衡性能够恢复，而且局部子树的高度亦必然同时恢复。

统一重平衡算法

从刚发生失衡的节点$x$出发逆行而上，直至遇到最低的失衡节点$g(x)$。于是在$g(x)$的更高一侧的子树内，其孩节点$p$和孙节点$v$必然存在，这一局部可以$g(x)$，$p$，$v$为界，分为四棵子树。按照中序遍历序列再重新排序$g(x)$和$p$,$v$，分别命名为$a$,$b$,$c$。观察之前的例子，可以发现四7棵子树的高度彼此相差不过一层，所以将这四棵树重新组装起来恰好即是一棵AVL树。

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
29
30
31
32
33
template <typename T> BinNodePosi(T) BST<T>::connect34 (
   BinNodePosi(T) a, BinNodePosi(T) b, BinNodePosi(T) c,
   BinNodePosi(T) T0, BinNodePosi(T) T1, BinNodePosi(T) T2, BinNodePosi(T) T3
) {
   //*DSA*/print(a); print(b); print(c); printf("\n");
   a->lc = T0; if ( T0 ) T0->parent = a;
   a->rc = T1; if ( T1 ) T1->parent = a; updateHeight ( a );
   c->lc = T2; if ( T2 ) T2->parent = c;
   c->rc = T3; if ( T3 ) T3->parent = c; updateHeight ( c );
   b->lc = a; a->parent = b;
   b->rc = c; c->parent = b; updateHeight ( b );
   return b; //该子树新的根节点
}
template <typename T> BinNodePosi(T) BST<T>::rotateAt ( BinNodePosi(T) v ) { //v为非空孙辈节点
   /*DSA*/if ( !v ) { printf ( "\a\nFail to rotate a null node\n" ); exit ( -1 ); }
   BinNodePosi(T) p = v->parent; BinNodePosi(T) g = p->parent; //视v、p和g相对位置分四种情况
   if ( IsLChild ( *p ) ) /* zig */
      if ( IsLChild ( *v ) ) { /* zig-zig */ 
         p->parent = g->parent; //向上联接
         return connect34 ( v, p, g, v->lc, v->rc, p->rc, g->rc );
      } else { /* zig-zag */  
         v->parent = g->parent; //向上联接
         return connect34 ( p, v, g, p->lc, v->lc, v->rc, g->rc );
      }
   else  /* zag */
      if ( IsRChild ( *v ) ) { /* zag-zag */ 
         p->parent = g->parent; //向上联接
         return connect34 ( g, p, v, g->lc, p->lc, v->lc, v->rc );
      } else { /* zag-zig */  
         v->parent = g->parent; //向上联接
         return connect34 ( g, v, p, g->lc, v->lc, v->rc, p->rc );
      }
}