【高阶数据结构】二叉树进阶探秘：AVL树的平衡机制与实现详解（一）

前文

关于上篇二叉搜索树性能那块，探讨了二叉搜索树虽然可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度，按照这种规则形成的二叉搜索树为AVL树，保持着严格的平衡。

一、AVL树概念

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

• 它的左右子树都是AVL树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
• 平衡因子并不是必须，只是他的一种实现方式

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在logn,搜索时间复杂度O(logn)

平衡因子计算:

• 平衡因子 = 右子树高度 - 左子树高度

二、AVL树实现

2.1 AVL树节点的定义 (成员默认访问公有)

template<class K, class V>
    struct AVLTreeNode
    {
        AVLTreeNode<K, V>* _left;
        AVLTreeNode<K, V>* _right;
        AVLTreeNode<K, V>* _parent;
        pair<K, V> _kv;
        int _bf;
        //主要类型
        AVLTreeNode(const pair<K, V> & kv)
            :_left(nullptr)
                ,_right(nullptr)
                ,_parent(nullptr)
                ,_kv(kv)
                ,_bf(0)
            {}
    };

AVL树每个结构存储一个pair对象，其中需要parent指针目的是为了方便访问当前节点的上一个节点。

考虑到AVLTreeNode书写麻烦，使用typedef进行类型重定义typedef AVLTreeNode Node;

2.2 AVL树查找逻辑

Node* Find(const K& key)
  {
    //按照搜索树
    Node* cur = _root;
    while (cur)
    {
      if (key > cur->_kv.first)
      {
        cur = cur->_right;
      }
      else if (key < cur->_kv.first)
      {
        cur = cur->_left;
      }
      else
      {
        //返回当前节点的指针
        return cur;
      }
    }
        //防止意外发生。
    return nullptr;
  }

本质上来说AVL树属于二叉搜索树，关于cur->_kv.first是cur通过指针去访问Node类中类型为pair对象的_kv。通过set与map简单学习。可以得知pair内部实现逻辑，_这里的kv.first中first是K类型的对象。同时AVL也是二叉树搜索树，查找逻辑当然是使用二叉搜索树的逻辑。

2.3 AVL树插入逻辑

既然AVL也是二叉搜索树，那么插入逻辑也是一样的，不同在于需要进行平衡因子的调正。(平衡因子 = 右子树高度 - 左子树高度)

当插入节点结束后，对插入节点的父亲节点进行平衡因子的修改。当对于父亲节点达到特定值会对应不同的情况，不断利用parent向上调整父亲节点的平衡因子。

通过例图去分析，当父亲平衡因子到达特定值对应不同情况:

第一张:当parent平衡因子从1或-1变到0

第二张:这里出现两种情况，parent平衡因子从0变到1或-1，parent平衡因子从1或-1变到2或-2。只有从0变到1或-1，没有从2或-2变成1或-1，因为当parent平衡因子绝对值超过1时，已经出现问题，需要进行调正

具体说明:

1. 按照搜索树规则插入
2. 某个父亲节点的平衡因子    

• 插入父亲的左孩子，父亲平衡因子–
• 插入父亲的右孩子，父亲平衡因子++

while (parent)
{
    //规矩平衡因子的规则，是根据特性和下面代码得来的
    if (parent->_left == cur)
    {
        parent->_bf--;
    }
    else if (parent->_right == cur)
    {
        parent->_bf++;
    }
    //判断是否回到父亲节点改动
    if (parent->_bf == 0)
    {
        //没有啥问题，可以跳出程序
        break;
    }
    else if (parent->_bf == 1 || parent->_bf == -1)
    {
        cur = parent;
        parent = parent->_parent;
    }
    //出现问题,这种情况是由情况二变化过来的，那么就是说，cur和parent向上移动了
    else if (parent->_bf == 2 || parent->_bf == -2
             {//.............}
}

理解:

在节点插入后，需要进行平衡因子的更新。更新顺序是从下到上，结合着父亲节点平衡因子进行判断是否需要继续向上更新。

根据判断更新父亲的平衡因子状况进行处理(该平衡因子更新完后):

• 父亲平衡因子 == 0，父亲所在子树高度不变，不再继续往上更新，插入结束
• 父亲平衡因子 == 1 or -1, 父亲所在子树高度变了，继续往上更新上面节点的平衡因子
• 父亲平衡因子 == 2 or -2, 父亲所在的子树已经不平衡了，需要旋转处理

三、AVL的旋转(重点)

如果在一颗原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种:

这里可以将前面两种归为单旋进行处理，而后面两种需要通过双旋进行处理。

提前说明:一个AVL树有多个AVL树或者说一个复杂的AVL树是由许多个简单的AVL树进行组合而成的。那么如果插入一个节点导致AVL树失去平衡，这里AVL树指以插入节点的父亲节点为根节点的子AVL树。遵守一个有问题解决问题，如果只是这一课AVL树有问题，就解决这颗AVL树，正常的AVL树我们是不要去过多的进行处理。

根据说明，如果将一整棵AVL树全部拆分进行研究，不同节点插入的位置很多选择，情况有很多种，难以全部罗列出来，而且没有必要，如果将一颗有问题AVL树治好，就可以将任何一颗AVL树治好，所以这边采用使用抽象图进行分析。

3.1 选用抽象图探讨AVL旋转

其中使用a、b、c子AVL树及其高度设置为h

抽象图中的抽象的AVL树平衡因子这里不用看的，目前罗列的情况是可以包含这里的，这里小部分就是大部分调正平衡因子的过程，意味着这部分也可以是抽象AVL树中的情况按照当前处理已经进行了调整。

3.2 单旋问题

使用单旋场景:parent->_bf == 2 && cur->_bf == 1或者parent->_bf == -2 && cur->_bf == -1

3.2.1 新节点插入较高左子树的左侧–左左:右单旋

场景:parent->_ bf == -2 && cur->_bf == -1

具体解析旋转步骤:

目前AVL树是平衡的，当插入新节点30到左子树中，左子树高度加一层，导致以60为根的子AVL树失去平衡。为了使得平衡，意味着节点60的右子树也需要增加一层，那么将60节点成为30节点的左孩子，同时原本30节点的左孩子和60节点成为30节点的左孩子的高度相同，那么将原本30节点的左孩子成为60节点有孩子。这里保证了30节点原本左孩子一定是小于60节点的。更新节点的平衡因子即可，简单概况就是30 < b子树 < 60 < c子树

旋转过程中，有以下几点情况需要考虑:

1. 30节点的右孩子可能存在，也可能不存在
2. 60可能是根节点，也可能是子树    

• 如果是根节点，旋转完成后，要更新根节点
• 如果是子树，可能是某个节点的左子树，也可能是右子树

void RotateR(Node* parent)
{
    Node* SubL = parent->_left;
    Node* SubLR = SubL->_right;
    parent->_left = SubLR;
    if (SubLR)
        SubLR->_parent = parent;
    SubL->_right = parent;
    Node* ppNode = parent->_parent;
    parent->_parent = subL;
    if (parent == _root)
    {
        SubL = _root;
        SubL->_parent = nullptr;
    }
    else
    {
        if (ppNode->_left == parent)
        {
            ppNode->_left = SubL;
        }
        else if(ppNode->_right == parent)
        {
            ppNode->_right = SubL;
        }
        SubL->_parant = ppNode;
    }
    SubL->_bf = 0;
    parent->_bf = 0;
}

通过旋转使得不平衡AVL树得到调整，这里不需要考虑向上更新平衡因子。从抽象图中可以得出旋转后结论，直接使用结论修改平衡因子就行。

3.2.2 新节点插入较高右子树的右侧–右右:左单旋

场景:parent->_ bf == 2 && cur->_bf == 1

这里和右单旋是差不多的，具体流程可以去看上述和代码分析

void RotateL(Node* parent)
{
    Node* SubR = parent->_right;
    Node* SubRL = SubR->_left;
    parent->_right = SubRL;
    if (SubRL)
        SubR->_parent = parent;
    SubR->_left = parent;
    Node* ppNode = parent->_parent;
    parent->_parent = subR;
    if (parent == _root)
    {
        SubR = _root;
        SubR->_parent = nullptr;
    }
    else
    {
        if (ppNode->_left == parent)
        {
            ppNode->_left = SubR;
        }
        else if (ppNode->_right == parent)
        {
            ppNode->_right = SubR;
        }
        SubR->_parant = ppNode;
    }
    SubR->_bf = 0;
    parent->_bf = 0;
}

【高阶数据结构】二叉树进阶探秘：AVL树的平衡机制与实现详解（二）https://developer.aliyun.com/article/1617412