5. AVL树

2018-06-13 本文已影响0人執著我們的執著

AVL树背景

在计算机科学中，AVL树是最先发明的自平衡二叉搜索树（BBST）。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 "An algorithm for the organization of information" 中发表了它。

BST -> BBST

BBST 核心技巧

1. 满足`适度平衡`标准

2. 重平衡操作的技巧与算法

以 AVL树为例，如何实现上述两条核心

AVL 树定义：

1. 首先满足 BST 性质

2. 或者为空树，或者满足以下性质

任意节点的左右子树高度差的绝对值不大于1

其左右子树又都满足 AVL树

为此，引入 `平衡因子` balFactor() ：左子树的高度减去右子树的高度

balFactor(V) = height( LC(V) ) - height( RC(V) ). 即V的左子树高度-右子树高度

则 AVL 满足： -1<= balFactor(V) <=1 (取值只有-1 ， 0 ，1)

注：AVL满足适度平衡标准，有 height(AVL) = O( log n)

AVL相关接口

BinTree 中定义的 节点高度
#define NodeHeight(p) ((p) ? p->height : -1)     //节点高度，约定空树的节点高度约定为 －1

AVL 接口
1. 理想平衡,左右子树高度相等
#define Balanced(x) \
    (NodeHeight(x->lchild) == NodeHeight(x->rchild))

2. 平衡因子
#define BalFator(x) \
    (NodeHeight(x->lchild) - NodeHeight(x->rchild)

3. AVL 平衡条件 BalFactor(x)在 [-1,1] 之间
#define AVLBalanced(x) \
    ( (-2 < BalFactor(x) ) && (  BalFactor(x) < 2 )

4. AVL 查找 Search() ... 可直接沿用 BST 的接口 <详见BST>

5. 需要重写的只有引起 AVL 结构变化的动态操作
5.1  插入操作
BinNodePosi insert(const T &);

5.2 删除操作
bool remove(const T &);

下面主要介绍 AVL 树的插入和删除操作

失衡与重平衡

AVL 插入删除操作

[注] insert操作 相比 remove操作 的重平衡简单一点

1. AVL 插入节点操作

一个重要的结论： AVL树插入节点x，同时可有多个失衡节点，从节点x 向上追溯其祖先，找到第一个失衡点(也称为最低失衡点)，对最低失衡点进行"对应"的复衡操作(等价变换)，子树的高度必然恢复，更高祖先也必复衡，全树也就恢复平衡。

[注] 最低失衡点 概念总结
首先引入最小不平衡子树 ：插入节点导致失衡后，距离插入节点最近的，且平衡因子的绝对值大于 1 的节点为根的子树。
这个节点就称之为最低失衡点
对最小不平衡子树进行复衡操作，使子树恢复平衡，全树也会进而平衡。

上图 insert(M) 操作，N 节点为最低失衡点。（N，K，M）为最小不平衡子树

1.1. 在平衡的二叉排序树(AVL)中插入一个节点，当出现不平衡时，根据不平衡情况可分为四种不平衡类型，这四种类型又可通过两类操作"单旋，双旋"来实现复衡

假设已知 `最低失衡点` 为A，根据新插入节点与A的位置关系来命名不平衡类型

LL型：新插入节点在A的左孩子(L)的左子树(L)中;
LR型：新插入结点在A的左孩子(L)的右子树(R)中;
RL型：新插入结点在A的右孩子(R)的左子树(L)中;
RR型：新插入结点在A的右孩子(R)的右子树(R)中;

图解这四种类型，以及其复衡操作

LL型： 右旋最低失衡点A（Zig(A)）

LL型
RR型：左旋最低失衡点A（Zag(A)）

RR型
LR型：

LR型
RL型：

RL型

下面通过更详细的"单旋，双旋操作步骤"来展示实现4类失衡情况复衡的过程

单旋：

对于 LL型：只需对 最低失衡点A 进行Zig(A)操作
对于 RR型：只需对 最低失衡点A 进行Zag(A)操作

`本质上`是一次`等价变换`的实现过程

以RR型为例，Zag(A)的等价变换过程
Zig
本质上是等价交换的过程，将三个节点及其子树按中序次序重构即可
[注] 理解上，采用上面的"RR型"图示展示的"2个节点+3棵子树"来重新构建即可，但是下面双旋要以 3+4 结构来实现重构，所以单旋'委屈一下'适应双旋，以便后续重构算法的统一实现，而不是单旋写一个重构，双旋也实现一个重构。

双旋：

对于 LR型 ： zag-zig
对于 RL型 ： zig-zag

与单旋类似，本质上也是等价变换的过程

以 RL型为例，进行 zig-zag 操作的过程
Zig-Zag
上图中 失衡前的树(1) 到 复衡后的树(3) ，本质上就是等价交换的过程：即
A，B，C三个节点与其对应的子树，按中序次序重新构建，可恢复平衡

将上述的单旋，双旋的操作过程理解清楚，本质上是等价交换的过程，下面的代码实现也是基于这个思想，理解了这个过程，也就理解了下述复衡算法实现的过程。 重点！！！

插入操作代码实现:
/*************************************/

#define FromParentTo(x)  ( IsRoot(x) ? _root : ( IsLChild(x)? x.parent->lchild : x.parent->rchild) )

BinNodePosi insert(const T & e)
{
   BinNodePosi &x = search(e);      //查找插入点
   if (x)
   {
       return x;                    //若目标已经存在，不执行插入操作，直接返回
   }
   
   x = new BinNode(e, _hot);     //找到待插入点，以_hot为父亲，创建 x ，并插入
   _size ++;
   BinNodePosi xx = x;   

   //以下，从 x 的 父亲出发，逐层向上，依次检查各代祖先，找到最低失衡点
   for (BinNodePosi g = x->parent; g; g = g->parent)
   {
       if (!AvlBalanced(*g))   // 一旦发现g失衡，则找到最低失衡点，通过调整可恢复全树平衡
       {
           //具体的重平衡实现函数
           FromParentTo(*g) ＝ rotateAt( tallerChild(g) );       //旋转重平衡操作
           break;
       }
       else
       {
           //否则，只需要更新其高度(平衡度虽然不变，高度却有可能改变)
           updateHeight(g);          //是只要更新该节点高度，还是包括其祖先？？再整理一下
       }
   }  
   
   return x;    //返回新节点，只需要一次调整！！！；
}

2. AVL删除节点操作

当出现不平衡状态需要重平衡时，同样通过"单旋"和"双旋"两类操作实现

单旋： LL型和 RR型

同时至多一个失衡节点g，首个可能的就是删除节点 x 的父亲节点 _hot

g经过单旋调整后恢复平衡，子树高度未必复原，更高祖先仍可能失衡

因有失衡传播现象，可能需要做 O(log n)次调整

双旋： zig-zag 和 zag-zig
以 zag-zig 为例：

同时至多一个失衡节点g，首个可能就是删除节点x的父亲_hot

Zag(p)
Zig(g)

因有失衡传播现象，可能需要做 O(log n )次调整

删除操作代码实现:
/*************************************/
bool remove(const T &e)
{
   BinNodePosi & x = search(e);
   if ( !x )
   {
       return false;    //待删节点不存在
   }
   removeAt(x, _hot);   //按常规的BST规模删除之后，_hot及其祖先都有可能失衡
   _size --;

   //以下是删除后的重平衡操作：从_hot出发逐层向上，依次检查其祖先g
   for (BinNodePosi g = _hot; g; g = g->parent)
   {
       if ( !AVLBalanced(*g) )  //一旦找到失衡点，则通过调整恢复平衡
       {
           g = FromParentTo(*g) = rotateAt( tallerChild( tallerChild(g) ));      //旋转重平衡操作
       }
       upDateHeight(g);      //并更新其高度
   }  // 可能还需做多次调整！！！无论是否做过调整，全树高度均可能下降

   return true;
}

上面AVL插入和删除节点操作，重平衡讲的很热闹
那么重平衡算法 rotateAt() 函数(也就是旋转操作)到底是怎么实现的呢？
我们现在知道所谓的旋转操作rotateAt() 无外乎zig, zag, zig-zag, zag-zig四类
那么如何能够高效的实现上述四类旋转呢？
通过一些分析，不难发现，所谓旋转最后实现的复衡结构，实际上是满足中序次序的重新构建，将理解上的旋转操作转换成逻辑上的构建操作，复衡算法的实现也就很容易实现
下面着重讲解！

写在前面

/* 删除节点操作后的调整动作  */
/* 1. <3+4重构> */
BinNodePosi connect34(BinNodePosi, BinNodePosi, BinNodePosi,
                      BinNodePosi, BinNodePosi, BinNodePosi, BinNodePosi);

/*2. <旋转操作> */
BinNodePosi rotateAt(BinNodePosi);

"3＋4" 重构算法

前面提及的 zig ，zag 操作（单旋式，双旋式），主要是帮助对算法操作过程形成整体了解，在真正的实现时，我们不必机械地如此理解，通过上面的图示，也很容易看出复衡的过程，也就是 3个节点 + 4棵子树的重新组合构建的过程

AVL 重平衡过程：并非在乎平衡过程的技巧，更在于高效率实现重平衡，引入高效重平衡算法`"3＋4" 重构算法`

"3＋4" 重构算法

设 g 为最低失衡节点，考察祖孙三代 g ~ p ~ v
以中序遍历次序（大小），将其重命名为： a < b < c （g，p，v根据中序次序对号入座）
比如 LL 型： {v，p，g} 对应 {a，b，c}
比如 LR 型： {p，v，g} 对应 {a，b，c}
此为 '3' , 表 3 个节点
{g，p，v}总共拥有互不相交的四颗（可能为空）的子树，
按中序遍历次序，将其重命名为 T0 < T1 < T2 < T3
此为 '4' , 表 4 棵子树
重构 :
1. a 的左子树为 T0，T0的父亲为a
  a 的右子树为 T1，T1的父亲为a
2. c 的左子树为 T2，T2的父亲为c
  c 的右子树为 T3，T3的父亲为c
3. b 的左孩子为 a，a 的父亲为 b
  b 的右孩子为 c，c 的父亲为 b

重构

"3＋4" 重构算法代码实现：

BinNodePosi connect(BinNodePosi a, BinNodePosi b, BinNodePosi c,
                    BinNodePosi T0, BinNodePosi T1, BinNodePosi T3, BinNodePosi T4)
{
    //重构
    a->lChild = T0;    
    if (T0)
    {
        T0 -> parent = a;
    }
    a->rchild = T1;
    if (T1)
    {
        T1 -> parent = a;
    }
    updateHeight(a);

/**********************************************/

    c->lChild = T2;    
    if (T2)
    {
        T2 -> parent = c;
    }
    c->rChild = T3;
    if (T3)
    {
        T3 -> parent = c;
    }
    updateHeight(c);

/**********************************************/

    b->lChild = a;    
    a->parent = b;
    b->rChild = c;
    c->parent = b;
    updateHeight(b);

    return b;      //该子树新的根节点
}

统一调整：实现全树的复衡 `rotateAt()` 旋转操作

BinNodePosi rotateAt(BinNodePosi v)
{
    BinNodePosi p = v->parent;      //父亲
    BinNodePosi g = p->parent;      //祖父

    if ( IsLChild(*p) )        //  L
    {
        if (IsLChild(*v))       //  L-L型
        {
            p-parent = g->parent;      //向上联接
            
            // 将 v, p, g 节点及其子树按中序排一下，作为入参
            return connect34(v, p, g, v->lchild, v->rchild, p->rchild, g->rchild);
        }
        
        else  //  L-R型
        {
            v->parent = g->parent;     //向上联接

            return connect34(p, v, g, p->lchild, v->rchild, v->rchild, g->rchild);
        }
    }

    else
    {  // zag-zig  ,  zag-zag
        
    }
}

以 LL 型和 LR 型为例，

LL型"3+4重构"

LR型"3+4重构"

[ 注 ] ：
3+4重构的等价变换算法是为了统一解决单旋和双旋对应的等价变换的！！！诚然单旋LL型或RR型用2+3重构也可以实现等价变换，但是双旋的话却不能以2+3实现，必须多引入一个节点，只能采用3+4，为统一实现单旋&双旋，采用3+4，对于单旋无影响。

综合评价

优点：无论search(),insert().remove()，最坏情况下的复杂度均为O(log n),O(n)的存储空间
缺点：借助高度或平衡因子，为此需改造元素结构，或额外封装
实测复杂度与理论值尚有差距
插入/删除后的旋转，成本大
删除操作重平衡，最多需要Ω(log n) 次
如果需要频繁插入和删除操作，未免得不偿失
单次动态调整后，全树的拓扑结构的变化量可能高达 Ω(log n)

5. AVL树

AVL树背景

BBST 核心技巧

1. 满足`适度平衡`标准

2. 重平衡操作的技巧与算法

以 AVL树为例，如何实现上述两条核心

AVL 树定义：

1. 首先满足 BST 性质

2. 或者为空树，或者满足以下性质

为此，引入 `平衡因子` balFactor() ：左子树的高度减去右子树的高度

则 AVL 满足： -1<= balFactor(V) <=1 (取值只有-1 ， 0 ，1)

下面主要介绍 AVL 树的插入和删除操作

失衡与重平衡

1. AVL 插入节点操作

1.1. 在平衡的二叉排序树(AVL)中插入一个节点，当出现不平衡时，根据不平衡情况可分为四种不平衡类型，这四种类型又可通过两类操作"单旋，双旋"来实现复衡

假设已知 `最低失衡点` 为A，根据新插入节点与A的位置关系来命名不平衡类型

图解这四种类型，以及其复衡操作

单旋：

`本质上`是一次`等价变换`的实现过程

双旋：

与单旋类似，本质上也是等价变换的过程

2. AVL删除节点操作

当出现不平衡状态需要重平衡时，同样通过"单旋"和"双旋"两类操作实现

写在前面

"3＋4" 重构算法

AVL 重平衡过程：并非在乎平衡过程的技巧，更在于高效率实现重平衡，引入高效重平衡算法`"3＋4" 重构算法`

"3＋4" 重构算法

统一调整：实现全树的复衡 `rotateAt()` 旋转操作

综合评价

猜你喜欢

热点阅读

5. AVL树

AVL树背景

BBST 核心技巧

1. 满足适度平衡标准

2. 重平衡操作的技巧与算法

以 AVL树 为例，如何实现上述两条核心

AVL 树定义 ：

1. 首先满足 BST 性质

2. 或者为空树，或者满足以下性质

为此，引入 平衡因子 balFactor() ： 左子树的高度减去右子树的高度

则 AVL 满足 ： -1<= balFactor(V) <=1 (取值只有-1 ， 0 ，1)

下面主要介绍 AVL 树的插入和删除操作

失衡与重平衡

1. AVL 插入节点操作

1.1. 在平衡的二叉排序树(AVL)中插入一个节点，当出现不平衡时，根据不平衡情况可分为四种不平衡类型 ，这四种类型又可通过两类操作"单旋，双旋"来实现复衡

假设已知 最低失衡点 为A，根据新插入节点与A的位置关系来命名不平衡类型

图解这四种类型，以及其复衡操作

单旋 ：

本质上是一次等价变换的实现过程

双旋 ：

与单旋类似，本质上也是等价变换的过程

2. AVL删除节点操作

当出现不平衡状态需要重平衡时，同样通过"单旋"和"双旋"两类操作实现

写在前面

"3＋4" 重构算法

AVL 重平衡过程：并非在乎平衡过程的技巧，更在于高效率实现重平衡，引入高效重平衡算法"3＋4" 重构算法

"3＋4" 重构算法

统一调整 ： 实现全树的复衡 rotateAt() 旋转操作

综合评价

猜你喜欢

热点阅读

1. 满足`适度平衡`标准

以 AVL树为例，如何实现上述两条核心

AVL 树定义：

为此，引入 `平衡因子` balFactor() ：左子树的高度减去右子树的高度

则 AVL 满足： -1<= balFactor(V) <=1 (取值只有-1 ， 0 ，1)

1.1. 在平衡的二叉排序树(AVL)中插入一个节点，当出现不平衡时，根据不平衡情况可分为四种不平衡类型，这四种类型又可通过两类操作"单旋，双旋"来实现复衡

假设已知 `最低失衡点` 为A，根据新插入节点与A的位置关系来命名不平衡类型

单旋：

`本质上`是一次`等价变换`的实现过程

双旋：

AVL 重平衡过程：并非在乎平衡过程的技巧，更在于高效率实现重平衡，引入高效重平衡算法`"3＋4" 重构算法`

统一调整：实现全树的复衡 `rotateAt()` 旋转操作