【C++】神奇的AVL树

各位大佬好，我是落羽！一个坚持不断学习进步的大学生。
如果您觉得我的文章有所帮助，欢迎多多互三分享交流，一起学习进步！
也欢迎关注我的blog主页: 落羽的落羽

一、AVL树的概念与性质

AVL树是“平衡搜索二叉树”，它是一颗特殊的二叉搜索树，具备以下特殊性质：

• 它的左右子树都是AVL树
• 它的左右子树的高度差的绝对值不超过1

AVL树相比于普通的二叉搜索树，高度平衡，其左右子树结点数量分布相对均匀。而它的左右平衡其实就是通过控制高度差去控制的。
为了方便控制左右平衡，我们给AVL树的每一个结点增加一个“平衡因子”成员，任何结点的平衡因子等于其右子树的高度减去其左子树的高度。也就是说，一个结点的平衡因子一定为0或1或-1。

由于AVL树是高度平衡的二叉搜索树，因此它的高度可以控制在logN，增删查改的效率也在O(logN)，相比于普通的二叉搜索树有了本质的提升。

二、AVL树的模拟实现

1. AVL树的结构

和我们以前学习树形结构一样，首先应该实现出它的结点的结构：

template<class K, class V>
struct AVLTreeNode
{pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;//后续的插入操作中，需要指向父结点的成员AVLTreeNode<K, V>* _parent;//平衡因子int _bf;AVLTreeNode(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. AVL树的插入

AVL的插入操作的实现，比较复杂。

大概过程是这样的：

• 插入一个值，首先按照二叉搜索树的性质找到正确的位置插入
• 新增结点后，就可能会影响它的祖先结点的高度，所以我们需要更新新增结点→根结点路径上的结点的平衡因子。实际中，最坏情况需要一直更新到根，有些情况可能更新到中间某个结点就能结束了，不会再影响上一层平衡因子，插入过程就算结束了

所以说，AVL树的插入操作其实包括插入+控制平衡（更新平衡因子）两步。在更新平衡因子时，新插入结点可能会使平衡因子的绝对值大于1，打破了左右子树的平衡，就需要进行位置的调整，我们需要对子树进行“旋转”。

2.1 更新平衡因子

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

只有子树的高度变化才会影响当前结点的平衡因子。从新增结点的parent结点开始，若新增结点是parent的右子，parent的平衡因子+1；若新增结点是parent的左子，parent的平衡因子-1。而parent的所在子树高度是否变化决定了是否需要继续往上更新结点的平衡因子。

更新的停止条件，要么是更新到某一个结点平衡因子为0，要么是更新到了根结点结束：

• 不断向上更新，直到更新到根结点，根的平衡因子也是1或-1，就停止了。

• 若更新后parent的平衡因子为0，说明它一定是由-1或1变为了0，这说明更新前parent的子树一边高一边低，新增的结点插入在了低的那边。也就是说，插入新结点后这颗以parent为根的子树的高度不变，那么parent的父结点的平衡因子就不会受到影响，更新结束。
  

• 若更新后parent的平衡因子为1或-1，说明它一定是由0变为的1或-1，说明更新前parent的子树一样高，新增结点后子树一边高一边低。parent所在的子树虽仍符合平衡的要求，但是高度增加了1，因此要继续向上调整parent的父结点的平衡因子。

• 若更新后parent的平衡因子为2或-2，则说明parent的平衡因子是由1变成2，或-1变成-2，说明更新前parent的子树一边高一边低，且新增结点在高的那边，parent所在子树的高的那边更高了，左右高度平衡就被破坏了，此时就需要进行旋转处理。

2.2 旋转

“旋转”要保证搜索树的规则，目的是让树从左右不平衡变平衡，降低旋转树的高度。

旋转分为四种，右单旋、左单旋、左右双旋、右左双旋。它们分别对应不同的场景进行使用。

以下的5、8、10是举例用的数值

2.2.1 右单旋

若更新后parent的平衡因子为-2，说明新增结点在左子树，且若新增结点在左子树的左子树，这种情况需要进行右单旋。

可以看出，5 < b子树 < 10，所以，右单旋就是将10变成5的右子树，b子树变成10的左子树，5变为根结点。这样一来，仍符合搜索树的规则，同时根结点的平衡因子变成了0，保证了左右平衡。

a、b、c子树的具体结构我们不必关心，也没办法举例穷尽所有的情形，只要符合这个模型，都使用上述右单旋的方法。

右单旋代码实现：

void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;parent->_left = subLR;if(subLR) //subLR可能为空subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (parentParent == nullptr) //原parent可能是整棵树的根{_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.2.2 左单旋

若更新后parent的平衡因子为2，说明新增结点在右子树，且若新增结点在右子树的右子树，这种情况需要进行左单旋。

左单旋其实就是右单旋对称的样子，左单旋就是将5变成10的左子树，b子树变成5的右子树，10变为根结点。其余细节和右单旋是一样的道理。

左单旋代码实现：

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;parent->_right = subRL;if (subRL)subRL->_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.2.3 左右双旋

右单旋和左单旋针对的是纯粹的左边高或右边高的情况。若是左子树的右边高，或是右子树的左边高的情况，单旋就不能解决了，需要进行双旋。

若更新后parent的平衡因子为-2，说明新增结点在左子树，且若新增结点在左子树的右子树，这种情况需要进行左右双旋。

“左右双旋”就是先对5为根的子树进行一次左旋，使其变成左边高右边低，再对整体进行一次右旋。所以，我们需要将b子树再拆开一层来分析：

因为我们需要以5为旋转点进行一次左单旋，左单旋需要移动b子树中的左子树。b子树中新增结点的位置的不同，平衡因子的改变也会不同，这里又要分成三种场景讨论：

• 场景1：h>0时，新增结点在e子树时，e子树高度从h-1变为h，经过如图所示的左右双旋后，10的平衡因子变为1，5和8的平衡因子变为0

• 场景2：h>0时，新增结点在f子树时，f子树高度从h-1变为h，经过如图所示的左右双旋后，5的平衡因子变为-1，10和8的平衡因子变为0

• 场景3：h==0时，abc都是空树，b自己就是一个新增结点，经过左右双旋后，三个结点的平衡因子均为0

左右双旋代码实现：

void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);//根据bf的值，判断是新增结点是哪种场景，调整平衡因子if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else //理论上只有上述三种情况，但可能AVL树中某处出现bug，最好上一层检测保险{assert(false);}
}

2.2.4 右左双旋

右左双旋，和左右双旋是一样的道理。若更新后parent的平衡因子为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);}
}

可以看出，不论进行了哪一种旋转后，根结点的平衡因子都会变成0。也就是说，向上更新结点平衡因子的过程中，遇到进行旋转的结点后，也可以停止向上更新了。

2.3 完整实现

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);cur->_parent = parent;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}//更新平衡因子while (parent){if (cur == parent->_right){parent->_bf++;}else if (cur == parent->_left){parent->_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){if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}break;}else{assert(false);}}return true;}

3. 检测是否平衡

我们要检查自己手搓的AVL树是否左右平衡，不仅要检查左右子树高度差是否在1以内，还要检查平衡因子的控制是否正确:

//计算树的高度
int _Height(Node* root)
{if (root == nullptr){return 0;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

//递归判断每一棵子树是否都合格
bool _IsBalanceTree(Node* root)
{if (root == nullptr){return true;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;if (abs(diff) >= 2){cout << root->_kv.first << "：高度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "：平衡因子异常" << endl;return false;}return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

bool IsBalanceTree()
{return _IsBalanceTree(_root);
}

4. 简单测试

简单测试一下我们的AVL树是否合格：

中序遍历结果是升序的，说明搜索树的性质没问题，并且树是平衡了，证明我们的AVL树没有问题！

本篇完，感谢阅读！