C++--AVL树

AVL树

1. AVL树的介绍

在前面学习二叉搜索树时提到，二叉搜索树的查找效率为 O(N)，因为当数据有序或接近有序时，构建出来的二叉搜索树是单分支或接近单分支的结构，此时树的高度接近 n，所以最坏情况下二叉搜索树的查找效率为 O(N)。

为了应对上面这种情况，两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在1962年提出了一种解决办法，当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1 (需要对树中的结点进行调整来实现)，即可降低树的高度，从而减少平均搜索长度。

通过上面这种方法构建出来的树就是平衡二叉搜索树，也叫 AVL 树 (由提出它的两个科学家名字的首字母组成)；AVL 树具有以下特性：

1. AVL 树的左右子树都是 AVL 树。
2. AVL 树左右子树高度之差的绝对值不超过 1 (-1/0/1)。
3. 通过引入平衡因子来控制 AVL 树的左右子树高度差，平衡因子 = 右子树高度 - 左子树高度。

如上，如果一棵二叉搜索树是高度平衡 (每个节点的平衡因子的绝对值都小于等于1) 的，那它就是AVL树。对于 n 个节点的 AVL 树，其高度为 O(logN)，查找的效率也为 O(logN)。

注意事项：

1. 引入平衡因子只是控制一棵树为平衡树的其中一种方法，我们也可以通过其他方法来控制；在平衡因子控制中，平衡因子是用来评估树的状态的变量；

2. 有的同学可能会疑惑这里的平衡因子的值为什么是 -1/0/1，而不直接调整为0，让 AVL 树变成一棵绝对平衡的树；这是因为在某些节点数下不可能将 AVL 树调整到绝对平衡，比如节点数为 2/4/6 …，在这些情况下不管怎么调整都始终会有一棵子树高度高1；

3. 由于平衡二叉搜索树是通过高度保持平衡的，所以有的地方也把它叫做高度平衡二叉搜索树。

2. AVL树的实现

2.1 AVL树的结构

和二叉搜索树不同，AVL 树需要增加一个变量 bf 即平衡因子来控制树的状态。同时，需要将节点定义为三叉链结构，即增加一个节点指针指向父节点，这是为了方便后面插入节点时修改父节点的平衡因子。

//结点结构
template<class K, class V>
struct AVLTreeNode
{// 需要parent指针，后续更新平衡因⼦可以看到 pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // balance factorAVLTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr),_bf(0){}
};//AVL树结构
template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public://...
private:Node* _root = nullptr;
}

2.2 AVL树的插入

AVL 树的插入前面部分和二叉搜索树的插入很类似，比当前节点大就往右边走，小就往左边走，相等就插入失败，走到空位就插入。不过二叉搜索树插入的是键值 key，而这里插入的是键值对 pair<K, V>，所以在于结点进行比较的时候是 cur->_kv.first（当前遍历到的节点） 和 kv.first（待插入节点） 进行比较。同时，在链接节点时需要注意修改节点父节点指针的指向，因为 AVL 树的节点是三叉链结构。

在节点已经插入完成之后就要进行平衡因子的更新了，下面对平衡因子的更新进行介绍：

1. 更新父节点的平衡因子：每插入一个新节点后都需要更新父节点的平衡因子，由于平衡因子 = 左子树高度 - 右子树高度，所以往左插入 -- 父节点平衡因子，往右插入 ++ 父节点平衡因子即可。

2. 更新祖先节点的平衡因子：祖先节点的更新则比较复杂，一共有三种情况：

   • 如果更新后父节点的平衡因子为0，说明插入前父节点的平衡因子为1/-1，左右子树高度不同，且此次插入刚好插入的是矮的那边，此时子树整体高度不变，不用继续向上更新祖先节点的平衡因子。

     具体示例： 更新到中间节点3为根的子树高度不变，平衡因子为0，不会影响上一层，更新结束。

     

   • 如果更新后父节点的平衡因子为1/-1，说明插入前父节点的平衡因子为0，左右子树高度相同，插入后改变了左子树/右子树的高度，子树整体高度也变了，此时需要继续向上更新祖先节点的平衡因子，且最多会更新到根节点的平衡因子。

     具体示例： 最坏更新到根节点停止。

     

   • 如果祖先平衡因子变为2/-2，此时这棵子树不再是 AVL树，需要对其进行旋转将其重新调整为 AVL树。

     具体示例： 更新到10结点，平衡因子为2,10所在的子树已经不平衡，需要旋转处理。

     

   • 补充： 祖先节点平衡因子更新过程中，如果祖先节点的平衡因子变为0或者更新到了根节点，则停止更新。

**注意：**如上，在某些情况下需要更新祖先节点的平衡因子，这也是为什么要将 AVL 树的节点结构定义为三叉链的原因，即为了能够更方便的找到父节点的地址。

插入节点及更新平衡因子的代码实现

bool Insert(const pair<K, V>& kv)
{// 搜索正确位置节点if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){// 比节点大的走右边if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}// 比节点小的走左边else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}// 相等的报错返回else{return false;}}// 创建新节点并将其链接到父节点上cur = new Node(kv);// 大于父节点连接在其右子树上if (parent->_kv.first < kv.first){parent->_right = cur;}// 小于父节点连接在其左子树上else{parent->_left = cur;}cur->_parent = parent;// 更新平衡因⼦ while (parent){// 更新平衡因⼦ // 插入左子树父节点平衡因子--，插入右子树付姐蒂娜平衡因子++if (cur == parent->_left)parent->_bf--;elseparent->_bf++;//检查父节点平衡因子，判断是否需要向上更新if (parent->_bf == 0){// 更新结束 break;}else if (parent->_bf == 1 || parent->_bf == -1){// 继续往上更新 cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){// 不平衡了，旋转处理...break;}else{//其余情况，前面的更新已经出现问题assert(false);}}return true;
}

2.3 AVL树的旋转

当某一个节点的平衡因子为 2/-2 时，要对以这个节点为根节点的子树进行旋转，让这课子树重新变为 AVL 树。

说明：下面的图中，有些结点给的是具体值，如10和5等结点，这里是为了方便理解，实际上是什么值都可以，只要大小关系符合搜索树的性质即可。

2.3.1 旋转的原则

1. 保持搜索树的规则
2. 让旋转的树从不平衡变平衡，其次降低旋转树的高度

旋转总分为四种，左单旋/右单旋/左双旋/右左双旋。

1. 左单旋：新节点插入较高右子树的右侧（右右）。
2. 右单旋：新节点插入较高左子树的左侧（左左）。
3. 先左单旋再右单旋：新节点插入较高左子树的右侧（左右）。
4. 先右单旋再左单旋：新节点插入较高右子树的左侧（右左）。

2.3.2 右单旋

2.3.2.1 原理介绍

本图1展示的是10为根的树，有a/b/c抽象为三棵高度为h的子树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是一个整棵树中局部的子树的根。这里a/b/c是高度为h的子树，是一种概括抽象表示，它代表了所有右单旋的场景，实际上右单旋有很多种，具体图2/图3/图4/图5进行了详细描述。

在a子树中插入一个新结点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平衡因子从-1变成-2，10为根的树左边高度差超过1，违反平衡规则。10为根的树左边太高了，需要往右边旋转，控制两棵树的平衡。

**右旋转的核心步骤：**因为5 < b子树的值 < 10，将b变成10的左子树，10变成5的右子树，5变成这棵新树的根，符合搜索树的规则，控制了平衡，同时这棵树的高度恢复到插入之前的h+2，符合旋转规则。如果插入之前10为整棵树根的一个局部子树，旋转后不会再影响上一层，插入结束了。

图一：综述

图二：h == 0

图三：h == 1

图四：h == 2

图五：h == 3

2.3.2.2 代码实现

void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;// 需要注意除了要修改孩⼦指针指向，还是修改⽗亲 parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;// parent有可能是整棵树的根，也可能是局部的⼦树 // 如果是整棵树的根，要修改_root if (parentParent == nullptr){_root = subL;subL->_parent = nullptr;}// 如果是局部的指针要跟上⼀层链接 else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}//调整平衡因子parent->_bf = subL->_bf = 0;
}

2.3.3 左单旋

2.3.3.1 原理介绍

其基本原理与右单旋相似，不做过多赘述。

**左单旋的核心步骤：**因为10 < b子树的值 < 15，将b变成10的右子树，10变成15的左子树，15变成这棵新树的根，符合搜索树的规则，控制了平衡，同时这棵树的高度恢复到插入之前的h+2，符合旋转规则。如果插入之前10为整棵树根的一个局部子树，旋转后不会再影响上一层，插入结束了。

图一：综述

2.3.3.2 代码实现

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}parent->_bf = subR->_bf = 0;
}

2.3.4 左右双旋

2.3.4.1 原理介绍

上面讨论在左单旋和右单旋都是插入后为直线的情况，那么如果插入后是折线呢？如下：上面讨论在左单旋和右单旋都是插入后为直线的情况，那么如果插入后是折线呢？如下：

可以看到，如果插入后形成的是一条直线，即在较高右子树的右侧插入或在较高左子树的左侧插入的话，那么经过一次左单旋或右单旋就能解决问题。但是如果插入后是一条折线，即在较高右子树的左侧插入或在较高左子树的右侧插入的话，单纯的左单旋或右单旋并不能解决问题。如上图所示，情况3经过左单旋其实是变成了情况4，而情况4经过右单旋又变成了情况3，所以在这种情况需要左单旋和右单旋配合从而使子树变为 AVL 树，即进行左右双旋或右左双旋。

下面图一和图二分别为左和右双旋中h=0和h=1具体场景分析，通过图7和图8可以看到，左边高时，如果插入位置不是在a子树，而是插入在b子树，b子树高度从h变成h+1，引发旋转，右单旋无法解决问题，右单旋后，树依旧不平衡。

右单旋解决的纯粹的左边高，但是插入在b子树中，10为根的子树不再是单纯的左边高，对于10是左边高，但是对于5是右边高，需要用两次旋转才能解决，以5为旋转点进行一个左单旋，以10为旋转点进行一个右单旋，这棵树就平衡了。

图一：h==0

图二：h==1

下图将a/b/c子树抽象为高度h的AVL子树进行分析，另外需要把b子树的细节进一步展开为8和左子树高度为h-1的e和f子树，因为要对b的父亲5为旋转点进行单旋，左单旋需要动树中的左子树。b子树中新增加点的位置不同，平衡因子更新的细节也不同，通过观察8的平衡因子不同，这里要分三个场景讨论。

• 场景1：h >= 1时，新增结点插入在e子树，e子树高度从h-1并不断更新8->5->10平衡因子，引发旋转，其中8的平衡因子为-1，旋转后8和5平衡因子为0，10平衡因子为1。

• 场景2：h >= 1时，新增结点插入在f子树，f子树高度从h-1变化为h并不断更新8->5->10平衡因子，引发旋转，其中8的平衡因子为1，旋转后8和10平衡因子为0，5平衡因子为-1。

• 场景3：h = 0时，a/b/c都是空树，b自己就是一个新增加点，不断更新5->10平衡因子，引发旋转，其中8的平衡因子为0，旋转后8和10和5平衡因子均为0。

2.3.4.2 代码实现

void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;//先单左旋在单右旋RotateL(parent->_left);RotateR(parent);//调整平衡因子if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else{assert(false);}
}

2.3.5 右左双旋

2.3.5.1 原理介绍

右左双旋跟左右双旋类似，先进行右单旋，在进行左单旋即可。

在根据下面三个场景调整平衡因子：

• 场景1：h >= 1时，新增结点插入在e子树，e子树高度从h-1变为h并不断更新12->15->10平衡因子，引发旋转，其中12的平衡因子为-1，旋转后10和12平衡因子为0，15平衡因子为1。
• 场景2：h >= 1时，新增结点插入在f子树，f子树高度从h-1变为h并不断更新12->15->10平衡因子，引发旋转，其中12的平衡因子为1，旋转后15和12平衡因子为0，10平衡因子为-1。
• 场景3：h == 0时，a/b/c都是空树，b自己就是一个新增结点，不断更新15->10平衡因子，引发旋转，其中12的平衡因子为0，旋转后10和12平衡因子均为0。

2.3.5.2 代码实现

void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}
}

2.3.6 总结

假如以 parent 为根的子树不平衡，即 parent 的平衡因子为 2 或者 -2，则以下情况考虑旋转：

1. parent 的平衡因子为 2，说明 parent 的右子树高，设 parent 的右子树的根为 ssubR

   • 当 ssubR 的平衡因子为 1 时，执行左单旋；
   • 当 ssubR 的平衡因子为 -1 时，执行右左双旋；

2. parent 的平衡因子为 -2，说明 parent 的左子树高，设 parent 的左子树的根为 subL

   • 当 subL 的平衡因子为 -1 时，执行右单旋；
   • 当 subL 的平衡因子为 1 时，执行左右双旋；

旋转完成后，原 parent 为根的子树的高度降低为未插入时的高度，此时这棵子树已经平衡，不需要再向上更新。

2.4 AVL树的查找

那二叉搜索树逻辑实现即可，搜索效率为 O(logN)

Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;
}

2.5 AVL树的删除

因为 AVL 树是一棵二叉搜索树，所以它的删除过程和二叉搜索树其实差不多，先找到删除的节点，然后删除分三种情况：

1. 删除的节点左边为空，则托孤后直接删除；
2. 删除的节点右边为空，则托孤后直接删除；
3. 删除的节点左右都不为空，则替换左边最大节点或右边最小节点进行删除；

删除后也需要调整父节点的平衡因子，只是删除后父节点及祖先节点平衡因子的变化和插入时平衡因子的变化一定程度上可以说是相反的，删除左孩子父节点平衡因子++，删除右孩子父节点平衡因–。

如果删除后父节点的平衡因子为 1/-1，说明删除前平衡因子为0，则删除不会改变子树的高度，不需要继续往上调整，如果删除后父节点平衡因子变为0，说明删除前为 1/-1，则此次删除改变了子树的高度，需要向上调整祖先节点的平衡因子，最坏情况下调整到根。

如果祖先的平衡因子调整后变为 2/-2，则需要进行旋转，旋转仍然分为四类：左单旋、右单旋、左右双旋和右左双旋。

所以 AVL 树的删除仅仅是比 AVL 树的插入复杂一些，但是原理都是一样的，所以这里不对它进行过多探讨，仅仅作为了解。

3. AVL树的验证

在完善了 AVL 树的插入之后，我们可以验证一下通过我们的程序构建出来的树到底是不是一棵 AVL 树，验证一共分为两部分：

• 验证是否为二叉搜索树；
• 验证二叉搜索树是否平衡；

验证二叉搜索树很简单，我们向树中插入数据，然后实现一个 InOrder 函数看遍历得到的数据是否有序即可。

//中序遍历
void InOrder() 
{return _inOrder(_root);
}void _inOrder(Node* root) 
{if (root == nullptr)return;_inOrder(root->_left);std::cout << root->_kv.first >> root->_kv.second >> std::endl;_inOrder(root->_right);
}

验证平衡树需要求出每个节点的左右子树的高度，看它们差是否为 -1/0/1，同时，在验证平衡的过程中可以顺便将不符合要求的节点的key值打印出来，方便发生错误时进行调试。

//求树的高度
int Height(Node* root) 
{if (root == nullptr)return 0;int leftH = Height(root->_left);int rightH = Height(root->_right);return (leftH > rightH ? leftH : rightH) + 1;
}//判断是否为平衡二叉树
bool IsBanlance() 
{return _IsBanlance(_root)
}bool _IsBanlance(Node* root) 
{if (root == nullptr)return true;//左右高度差的绝对值是否小于等于1int leftH = Height(root->_left);int rightH = Height(root->_right);//如果不平衡我们可以打印一下发生错误的节点的key值if (rightH - leftH != root->_bf) {cout << root->_kv.first << "平衡因子异常" << endl;return false;}//不仅要当前子树为平衡二叉树，子树的左右子树也要为平衡二叉树return abs(rightH - leftH) < 2 && _IsBanlance(root->_left) && _IsBanlance(root->_right);
}