数据结构_平衡二叉搜索树(AVL树)

心已赠人 2022-05-22 09:45 307阅读 0赞

## 平衡二叉搜索树 ##

在[二叉搜索树][Link 1]中，已经知道search、insert和remove等主要接口的运行时间均正比于树的高度。但是在最坏的情况下，二叉搜索树可能退化成列表，此时查找的效率会降至O(n)。因此，通常通过控制树高，来控制最坏情况下的时间复杂度。  
对于节点数目固定的BST，越是平衡，最坏情况下的查找速度越快，如下图所示：  
![这里写图片描述][70]

为了理解平衡二叉树，我们首先要理解几个主要概念，理想平衡与适度平衡以及如何进行等价变换让树更为平衡。

*  理想平衡与适度平衡  
    节点数目固定时，兄弟子树高度越接近（平衡），全树的高度也将倾向于更低。包含n个节点的二叉树，高度不可能小于log2(n)（向上取整），当树的高度刚好为log2(n)时，称作理想二叉树。例如完全二叉树和满二叉树。  
    ![这里写图片描述][70 1]  
    但是大多数情况下，树不能满足完全二叉树的条件，因此要放宽平衡的标准。在渐进意义下，放松标准后的平衡性称为适度平衡（渐进的不超过O(logn)）。 我们称可以保持适度平衡的BST称为平衡二叉树（BBST），例如AVL树、红黑树等。
 *  等价变换  
    若两颗二叉搜索树的中序遍历序列是相同，则称他们是相互等价的，反之亦然。例如：  
    ![这里写图片描述][70 2]  
    总结出来，等价BST的特性即是：  
    上下可变：联系关系不尽相同，承袭关系可能颠倒。左右不乱：中序遍历完全一致。
 *  旋转调整  
    实际上任何一组等价BST的相互转换，都可以认为是一系列的基本操作串接而成的。最基本的修复手段就是通过围绕节点的旋转，实现等价前提下的的局部拓扑调整。  
    1、zig：顺时针旋转  
    ![这里写图片描述][70 3]  
    2、zag：逆时针旋转  
    ![这里写图片描述][70 4]  
    平衡二叉搜索树的适度平衡性，都是通过对树中每一局部增加某种限制条件来保证的。例如：AVL树中，兄弟节点高度相差不过1。除了适度平衡性，还有以下局部性：  
    1、经过单次动态修改操作之后，至多只有O(log(n))处局部不在满足限制条件。  
    2、在O(log(n))时间内，使这O(log(n))处局部（以至全树）重新满足限制条件。  
    意味着，刚刚失去平衡的二叉搜索树，可以通过（一系列zig或zag，只在局部操作可以在常数时间内完成）变换，转换成一颗等价的平衡二叉搜索树。
    
    **AVL——BBST**

首先给出所用的一些宏定义

#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平衡条件
     #define stature(p)((p)?(p)->height:-1)
    
     /******************************************************************************************
      * 在左、右孩子中取更高者
      * 在AVL平衡调整前，借此确定重构方案
      ******************************************************************************************/
     #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）优先*/ \
        ) \
        ) \
     )

*  定义及性质  
    AVL树，即平衡因子受限的二叉搜索树\_各节点的平衡因子的绝对值均不超过1。  
    平衡因子：balFac(v)=height(lc(v))-height(rc(v));  
    接口定义如下（其中BST的定义参考[二叉搜索树][Link 1]）：

#include "BST/BST.h" //基于BST实现AVL树
     template <typename T> class AVL : public BST<T> { //由BST派生AVL树模板类
     public:
        BinNodePosi(T) insert ( const T& e ); //插入（重写）
        bool remove ( const T& e ); //删除（重写）
     // BST::search()等其余接口可直接沿用
     };

*  AVL树的平衡性  
    收先要证明高度为h的AVL树至少包含fib(h+3)-1个节点。

--------------------

证明：  
假设高度为h的AVL树，至少应该包含s(h)个节点。情况如下图所示：  
![这里写图片描述][70 5]  
则，s(h)满足以下递推式：  
s(h)=s(h-1)+1+s(h-2)  
=>s(h)+1=s(h-1)+1+s(h-2)+1  
=>T(h)=T(h-1)+T(h-2)=fib(h+3)  
=>s(h)=fib(h+3)-1  
综上，高度为h的AVL树，至少包含fib(h+3)-1个节点。于是反过来包含n个节点的AVL树高度应为O(log(n))。

--------------------

*  AVL树的失衡与重平衡  
    AVL树经过插入、删除等动态修改操作，节点的高度可能发生变化，使得其不在满足AVL树的平衡条件。例如：  
    ![这里写图片描述][70 6]
 *  AVL插入操作  
    1、插入单旋  
    v是p的右孩子，且p是g的右孩子，朝向一致。  
    ![这里写图片描述][70 7]  
    上图灰色部分表示插入节点（二选一），插入操作之后，同时可有多个失衡节点，但是最低者g不低于x的祖父。g经过单旋调整之后复衡，子树高度复原，更高的祖先也必然平衡，如下图所示（此处为zag旋转，还有对称情况）：  
    ![zigzig][]  
    2、插入双旋  
    v是p的左孩子，p是g的右孩子，朝向不一致。  
    ![zigzag][]  
    与插入情况类似，同时可有多个失衡节点，但是最低者g不低于x的祖父。g经过双旋调整之后复衡，子树高度复原，更高的祖先也必然平衡，  
    经过一次zig旋转和zag旋转之后结果如下（同样还有对称情况）：  
    ![这里写图片描述][70 8]  
    接口实现：

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

效率：首先按照二叉搜索树的常规算法，在O(log(n))时间内插入新的节点x。由于原树是平衡的，最多检查O(log(n))就可以确定失衡节点的位置，为了恢复平衡，最多两次旋转（常数时间）就可以恢复。因此，AVL树的插入操作可以在O(log(n))时间内完成。

*  AVL树删除操作。  
    与插入操作不同，在摘除节点之后，以及在之后的调整过程中，失衡的节点集始终至多含有一个节点。而且若该结点存在，则其高度必然与失衡前相同。如下图所示：  
    ![这里写图片描述][70 9]  
    失衡的节点g与之前的高度相同。  
    重平衡操作：  
    与插入操作同理，从\_hot节点（删除节点的父节点）出发沿parent指针上行，经过O(log(n))时间就可以确定失衡节点g的位置。作为失衡节点g，在不包含被删除节点x的一侧，必然有一个非空孩子p，且p的高度至少为1。于是根据以下规则从p的两个孩子中选出节点v：若连个孩子不等高，v选择其中的更高者；否则选取v与p的同向者（v与p同为左孩子，或者同为右孩子）。  
    1、单旋  
    经过单旋调整之后，子树高度未必复原，更高祖先仍可能失衡（例如下图，T2下面的节点不存在时的情况）。  
    为了让上图所示的二叉搜索树恢复平衡，我们只需要经过一次zig旋转（对称的情况类似），如下图（此时p的两个孩子同高，p选择同向者）结果：  
    ![这里写图片描述][70 10]

2、双旋  
![这里写图片描述][70 11]  
3、失衡传播  
与插入操作不同，在删除节点之后，尽管可以通过单旋或者双旋调整使局部子树复衡，但是局部子树的高就全局而言，亦然可能再次失衡，例如下图：  
![这里写图片描述][70 12]  
将这种由于底层失衡节点的重平衡而致使更高祖先失衡的情况，称为失衡传播。失衡传播的方向必然自底而上，在此过程的任一时刻，至多只有一个失衡节点；高层的某一个节点由失衡转为平衡，只能发生下层节点复衡之后。因此，最多需要O(log(n))次调整即可恢复。  
算法实现：

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

**3+4重构算法及其实现**  
对于上面所说的重平衡操作，如果采用旋转一步一步的完成将会显得很复杂，其实就如同拼魔方一样，我们可以将魔方打散然后合起来就可以而不是旋转。

--------------------

假设g为最低的失衡节点，考察祖孙三代g~p~v，按照中序遍历次序，将其重命名为a、b、c。并且他们拥有互不相交的四颗（可能为空的）子树，按中序遍历次序命名为：T0、T1、T2、T3。合起来的中序遍历为\{T0,a,T1,b,T2,c,T3\}。我们最终得到的结果（正如魔方的六面相同一样）都如下图所示：  
![这里写图片描述][70 13]

--------------------

实现如下：

/*******************
    *按照“3+4”结构联结三个节点及其四颗子树，返回重组之后的局部子树根节点的位置
    *子树根节点与上层节点之间的双向联结，均有上层调用者完成
    **********************/
    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)
    {
        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;//子树新的根节点
    }

利用上述connect34()算法，可以按照不同的情况，完成重平衡算法：

/******************************************************************************************
      * BST节点旋转变换统一算法（3节点 + 4子树），返回调整之后局部子树根节点的位置
      * 注意：尽管子树根会正确指向上层节点（如果存在），但反向的联接须由上层函数完成
      ******************************************************************************************/
     template <typename T> BinNodePosi(T) BST<T>::rotateAt ( BinNodePosi(T) v ) { //v为非空孙辈节点
        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 );
           }
     }

分析：为了调用connect34()，主要是要确定对应的三个节点四个子树，主要根据中序遍历序列确定。例如上面对应的情况（这里只列举zig-zig和zig-zag，其余情况类似）：

![这里写图片描述][70 14]  
![这里写图片描述][70 15]

**总结**  
优点：无论查找、插入或删除，最坏的情况下的复杂度均为O(log(n))，O(n)的存储空间。  
缺点：  
1、借助高度或平衡因子，为此需要改造元素结构，或额外的封装（可以通过伸展树splay解决）  
2、单词动态调整后，全树的拓扑结构的变化量可能高达log(n)。插入与删除操作的变化量不对等，inert操作只许常数即可满足，remove操作则可能高达log(n)。（红黑树可以使得插入与删除操作的变化量都在常数内，即只需常数的时间就可恢复平衡）。

[Link 1]: https://blog.csdn.net/xc13212777631/article/details/80752323
[70]: /images/20220522/53636b42a7204a34b4040997e472ef69.png
[70 1]: /images/20220522/216bf1bdcdb047f2b69d995e4c4242bf.png
[70 2]: /images/20220522/b38cbd2839f54e798eaaa2f23fcfedd4.png
[70 3]: /images/20220522/4f86e03bbb854a35996be7832b56a35c.png
[70 4]: /images/20220522/59cd7bf419b6452bbbb52943764c182b.png
[70 5]: /images/20220522/86a70384244a401fb4b4faa88170b899.png
[70 6]: /images/20220522/316bf490b89c4bf1925751c57e9cd950.png
[70 7]: /images/20220522/10a2d6d7f20c44a0929cd9eb98ec9c0d.png
[zigzig]: /images/20220522/9b203881eccf4387893c49ae27eae4aa.png
[zigzag]: /images/20220522/45ea1f8fcd0f4d23aeb96ea843cad3dd.png
[70 8]: /images/20220522/5799d903417d42288a03ef0f45900b4e.png
[70 9]: /images/20220522/758dd446a3cf47fa8d381a04a071746f.png
[70 10]: /images/20220522/5b069ce10e9c44d38eb3c06eba5c7d42.png
[70 11]: /images/20220522/d3543a237fca498f8ff66e82f33f2243.png
[70 12]: /images/20220522/10216a6f5c60487786f01e9cbeaa9f86.png
[70 13]: /images/20220522/accc233474fd4715bfb4452e6d7a1c76.png
[70 14]: /images/20220522/1c83e3280218465994a7b647e8c3014f.png
[70 15]: /images/20220522/57153488b39044f7861f9b2172405dfb.png