【C++】高阶数据结构 -- 平衡二叉树（AVLTree）
本篇文章主要讲解一种特殊的 BST -- 平衡二叉树（AVLTree）
目录
2 AVLTree 的增删查改（不允许插入重复 key 的 key-value 场景）
1 平衡二叉树的概念
平衡二叉树是一种特殊的二叉搜索树，它不仅满足二叉搜索树的性质，而且在二叉搜索树的基础上实现了自平衡，能使得左子树与右子树的高度差不超过1，从而提高了查找效率。
AVLTree 是最早的平衡二叉树，其是由两位苏联数学家 Georgy Adelson-Velsky 和 Evgenii Landis 在 1962 年发表在 《An algorithm for the organization of information》论文上。AVLTree 的明名正式取自这两位发明者的名字首字母。
在 AVLTree 中每个节点都有一个平衡因子 (balance factor)，该平衡因子可以是左子树的高度减去右子树的高度，也可以是右子树的高度减去左子树的高度，我们这里选择平衡因子为右子树的高度减去左子树的高度，而对于 AVLTree 来说，每个节点左右子树的高度差不能超过1，所以平衡因子只能是 0、1、-1。这里的平衡因子不是必须的，但是有了平衡因子可以帮助我们观察和检测整棵 AVLTree 的结构。
那么根据 BST 的结构，AVLTree 的结构也与之类似。AVLTree 要么是一棵空树，要么就是一棵如下结构的二叉树：
（1） 每个节点的左子树和右子树的高度差不能超过1，也就是平衡因子只能为 0、1、-1
（2） 每个节点的左子树又是一棵 AVLTree
（3） 每个节点的右子树又是一棵 AVLTree
以下的这棵树就是一棵 AVLTree：
红色的就是每个节点的平衡因子。需要注意的是 AVLTree 也是一棵 BST，在满足平衡的同时也需要满足二叉搜索树的规则。
以下的这棵树就不是一棵 AVLTree：
因为其有一个节点的平衡因子为 2，大于1，所以其不是一棵 AVLTree。
所以对于 AVLTree 来说，由于左右子树的高度差不能超过1，所以其高度会和完全二叉树类似，高度可以控制在 logN 级别，而二叉搜索树的搜索次数就是其高度次，所以 AVLTree 增删查改的效率就是 logN 级别，比起 BST 来说会有很大的提升。
2 AVLTree 的增删查改（不允许插入重复 key 的 key-value 场景）
1） AVLTree 的节点结构
由于实现的 key-value 场景，所以在节点里面我们直接使用 pair<K, V> 对象来作为数据类型，另外左孩子、右孩子也必不可少。在上一小节里面，我们知道了在 AVLTree 里面可以利用一个平衡因子(balance factor)来帮助我们检测整棵 AVLTree 的结构，所以我们选择在节点结构里面再添加一个平衡因子 _bf，帮助我们检测与更新 AVL 树。
那么节点里面有没有别的需要添加的成员变量呢？在这里我们选择添加一个 _parent 指针变量来指向当前节点的父亲节点。添加该成员变量的原因是因为在后面更新 AVL 树的结构时方便找到父节点，但是你不添加 _parent 也是可以的，只是添加了之后更加方便。
template<class K, class V> struct AVLNode { pair<K, V> _data; AVLNode<K, V> _left; AVLNode<K, V> _right; AVLNode<K, V> _parent; int _bf; AVLNode(const pair<K, V>& data) :_data(data) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} };那么有了节点结构之后，整棵树的结构也就很好写了。因为只需要有一个根就可以找到整棵树，那么我们只需要一个根节点的成员变量就可以了：
template<class K, class V> class AVLTree { typedef AVLNode<K, V> Node; public: private: Node* _root = nullptr; };2） AVLTree 的插入
由于 AVL 树依然是一棵 BST，所以插入节点前面情况与 BST 插入是相同的，也就是：
（1） 如果树为空，直接创建当前节点
（2） 创建 parent 指针与 cur 指针，parent = nullptr, cur = _root
（3） 根据要插入数据 key 的大小来判断插入到左边还是右边，直到 cur 为空
（4） 创建节点，改变 parent 节点指向与 cur 中的 _parent 指针
具体代码为：
bool Insert(const pair<K, V>& data) { if (_root == nullptr) { _root = new Node(data); return true; } Node* cur = _root, *parent = nullptr; while (cur) { if (data.first > cur->_data.first) { parent = cur; cur = cur->_right; } else if (data.first < cur->_data.first) { parent = cur; cur = cur->_left; } else return false; } //找到了该插入的位置 cur = new Node(data); //更改parent 指向 if (data.first > parent->_data.first) parent->_right = cur; else parent->_left = cur; //不要忘记更改 cur 的 _parent 指针 cur->_parent = parent; return true; }但是在 AVLNode 中还有一个 _bf 平衡因子成员，我们需要来更新它。更新平衡因子比较复杂，接下来我们来看一下如何更新平衡因子。
（1） 如何更新平衡因子
平衡因子更新原则：
之前在 AVLTree 的概念那一小节我们选择平衡因子 = 右子树高度 - 左子树高度，所以在新插入一个节点之后，首先就会对其 parent 节点的高度产生影响，我们需要先更新 parent 节点的平衡因子，也就是如果在右子树插入，那么右子树的高度就会 +1，所以 ++_bf 就可以；如果插入到左子树，那么左子树的高度就会 +1，需要 --_bf。那么这里只更新 parent 节点的平衡因子就可以吗？我们来看这么一种情况：
红色节点为新插入的节点，将 parent 节点的平衡因子更新为了 -1，但是看 38 的 parent 节点 30，其右子树的高度变为了 2，所以应该也将其更新为 1，对于根节点也是一样的，由于其右子树节点高度变为了 3，所以其平衡因子应该更新为 0。所以插入一个节点之后，不仅要更新当前节点父亲节点的平衡因子，其所有祖先的平衡因子都要更新。究其原因就是因为如果插入节点的 parent 子树高度变化了，其所有祖先的高度也必然会发生变化，所以所有祖先的平衡因子都要更新。
总结一下平衡因子更新原则：
a. 平衡因子 = 右子树高度 - 左子树高度
b. 插入在左子树，parent 的平衡因子 ++；插入在右子树，parent 的平衡因子 --
c. 如果 parent 的子树高度变化了，就需要向上更新，直到其祖先节点的高度不变或者更新到根节点
平衡因子停止更新的条件：
a. 如果 parent 节点的平衡因子更新为了 0，也就是由 1->0 或者 -1->0，说明更新之后，其左右子树的高度相等了，那就不需要再进行更新了，更新结束
b. 如果 parent 节点的平衡因子更新为了 1 或者 -1，那就说明其子树的高度改变了，那就需要继续向上更新
c. 如果 parent 节点的平衡因子更新为了 2 或者 -2，那就说明节点是插入到了更高的子树里，这时候整棵树已经不平衡了，所有的平衡因子不是 1,0,-1 了，这时候需要进行旋转处理，将 parent 及其子树重新旋转成为一棵 AVL 树，进行旋转之后，整棵树会恢复平衡，此时也不需要进行平衡因子的更新了，更新结束
d. 如果一直更新到根，更新完 _root 节点的平衡因子之后，更新也会结束
以下是对应于上面四种情况的图形：
a：
此时 parent->_bf 更新为 0，不影响其他祖先的平衡因子，所以更新结束。
b 上面已经演示过了，就不再演示。
c：
更新平衡因子时出现了 -2，此时需要进行旋转处理，旋转之后的树会变为：
旋转完之后，其就变成了一棵 AVL 树，所以就不需要更新平衡因子了，直接退出即可。
d 比较简单，就不演示了。
所以插入完节点之后，我们需要更新平衡因子，而且需要更新到根。这部分代码为：
bool Insert(const pair<K, V>& data) { if (_root == nullptr) { _root = new Node(data); return true; } Node* cur = _root, *parent = nullptr; while (cur) { if (data.first > cur->_data.first) { parent = cur; cur = cur->_right; } else if (data.first < cur->_data.first) { parent = cur; cur = cur->_left; } else return false; } //找到了该插入的位置 cur = new Node(data); //更改parent 指向 if (data.first > parent->_data.first) parent->_right = cur; else parent->_left = cur; //不要忘记更改 cur 的 _parent 指针 cur->_parent = parent; //更新平衡因子 while (parent) { if (cur == parent->_left) --parent->_bf; else ++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) { //旋转处理 //结束之后，也不需要更新了 break; } else { //为了处理平衡因子出错的情况 assert(false); } } return true; }接下来就是 AVL 树里面最难的部分，也就是如何将一棵不平衡树旋转成为一棵平衡树，我们来仔细讲解这部分。
（2） AVL 树的旋转
在 AVL 树中为了使得整棵树保持平衡的特性，以保持较高的查找效率，当有节点出现平衡因子为 2 或者 -2 时，AVL 树会进行旋转的操作，使得所有节点的平衡因子重新变为 1，0，-1。
AVL 树中共有四种旋转方式，分别是右单旋、左单旋、左右双旋、右左双旋，分别对应四种不同的情况。
右单旋
如果出现了以下的情况，我们会对整棵树进行右单旋：
当 10 插入在 15 的左子树里面时，使得本来就高的左子树变得更加高时，这时候就要采取右单旋的形式。如果用一个抽象图来表示的话就是这样的：
20 的平衡因子本来是 -1，左子树高度为 h+1，右子树高度为 h，但是在 14 的左子树 A 插入一个节点之后使得 20 的左子树高度变为了 h+2，也就是在本来就高的左子树又插入了一个节点，使得平衡因子变为了 -2，此时就需要使用右单旋来解决这种场景。
右单旋的旋转步骤
这里就以上面那幅抽象图演示右单旋的具体步骤。
a. 先将 20 的左子树的根节点，也就是 14 旋转成为这棵树或者子树的根，将 20 变为 14 的右子树的根节点
b. 再将 14 的右子树变为 20 的左子树，也就是 B 变为 20 的左子树
按照上面的旋转步骤，旋转之后的树如图所示：
经过右单旋之后，树的高度由原来的 h+3 变为了旋转之后的 h+2，高度不仅变回了插入节点之前的高度，而且 14 和 20 的平衡因子也变为了 0。最重要的是，如果这棵树是一棵子树，其是不影响树中的其他部分的，而且整棵树的高度恢复成为了插入之前的高度，别的节点的平衡因子也不必改变，这样不仅完成了树平衡的调整，也完成了平衡因子的更新。
右单旋代码
void RotateR(Node* parent) { Node* Parent = parent->_parent; Node* subLR = parent->_left->_right; Node* subL = parent->_left; //不要忘记更改父亲的指向 //parent 可能为根节点 if (parent == _root) _root = subL; else { if (parent == Parent->_left) Parent->_left = subL; else Parent->_right = subL; } //subL 的父亲节点也需要更改 subL->_parent = Parent; //更改左右孩子指向 parent->_left = subLR; subL->_right = parent; //不要忘记更改 parent 以及 subLR 的父亲指向 parent->_parent = subL; if (subLR) subLR->_parent = parent; //最后不要忘记更新平衡因子 subL->_bf = parent->_bf = 0; }在写代码的时候，不要只顾着更改左孩子与右孩子指针指向。由于在 AVLNode 中还有 _parent 指针，所以我们也需要更改 _parent 指针指向，在右单旋过程中，一共需要更改的节点有三个，前两个就是上面图中的 20 与 14，还有一个就是 14 右子树中的根节点，也就是 B 的根节点，这些节点的 _parent 指针都需要改变。但是 B 可能为空树，所以我们需要先判断 B 根节点是否为空，再去更改 _parent 指向。
左单旋
左单旋与右单旋正好相反，但是大致逻辑是相同的，这里就只展示抽象图。
在右单旋中，是在高的左子树中再插入节点使之变得更高，会用右单旋；而在左单旋中，适合于在高的右子树插入节点，使右子树变得更高的情况。整棵子树的根节点平衡因子会由原来的 1 变为 2。
左单旋的旋转步骤
还是以上面那幅抽象图来说明左单旋的旋转步骤。
a. 先将 20 的右子树的根节点，也就是 28 旋转成为这棵树或者子树的根，将 20 变为 28 的左子树的根节点
b. 再将 28 的左子树变为 20 的右子树，也就是 B 变为 20 的右子树
旋转之后的树如图所示：
和右单旋一样，左单旋之后的树依然会恢复到之前树的高度，也就是 h+2；同时，20 与 28 的平衡因子也同步更新为 0。
左单旋代码
void RotateL(Node* parent) { Node* Parent = parent->_parent; Node* subR = parent->_right; Node* subRL = subR->_left; //不要忘记更改父亲的指向 //parent 可能为根节点 if (parent == _root) _root = subR; else { if (parent == Parent->_left) Parent->_left = subR; else Parent->_right = subR; } //subR 的父亲节点也需要更改 subR->_parent = Parent; //更改孩子指向 subR->_left = parent; parent->_right = subRL; //不要忘记更改 parent 与 subRL 的父亲指向 parent->_parent = subR; if (subRL) subRL->_parent = parent; //更新平衡因子 parent->_bf = subR->_bf = 0; }依然是不要忘记更改 _parent 指针的指向与更新平衡因子。
左右双旋
如果出现了以下场景，是会采用左右双旋的场景：
与右单旋类似，都是在高的左子树里面插入节点使得左子树变得更高；但是与右单旋不同的是，其并不是在其左子树的左子树里面插入，而是在其左子树的右子树里面插入，也就是不在 A 里面插入，而在 B 里面插入时，会采用左右双旋的方式来恢复平衡。
左右双旋的旋转步骤
根据名字来看，左右双旋具体的旋转步骤是先用一次左单旋，再用一次右单旋。具体的旋转步骤如下：
a. 先以 14 为父亲节点，进行一次左单旋，也就是 RotateL(14)
b. 再以 20 为父亲节点进行一次右单旋，也就是 RotateR(20)
但是呢，左右双旋具体又分为三种情况。但是这三种情况仅仅是平衡因子更新不同，旋转步骤都是相同的：
情况一
第一种情况是因为插入在了 16 的左子树从而导致 20 的平衡因子由 -1 变为了 -2，旋转之后的树如图。
经过旋转之后，原来的孙子节点 16 现在变成了整棵子树的根节点，平衡因子更新为了 0；原来的祖先节点 14 和 20 分别变成了 16 的左孩子和右孩子，平衡因子分别更新为了 0 和 1；同时整棵树的高度也变成了插入之前的高度 h+2，所以旋转之后也不必更新其他节点的平衡因子了。
情况二
情况二是因为在 16 的右子树中插入使得 20 的左子树变高。旋转之后的树如图所示。
情况二中 16 的平衡因子依旧为 0，但是 20 的平衡因子变为了 0,14 的平衡因子变为了 -1。
情况三
第三种情况比较特殊，就是在 14 为叶子节点，且 20 右子树为空的情况。此时在 14 的右子树插入节点，使得 20 的左子树变高。旋转之后的树如图所示。
旋转之后，三个节点的平衡因子都变为了 0。
左右双旋代码
void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; //先以 subL 为 parent 进行左单旋 RotateL(subL); //再以 parent 为 parent 进行右单旋 RotateR(parent); //根据三种情况进行平衡因子的更新 //插入到 subLR 的左子树 if (bf == -1) { subL->_bf = 0; parent->_bf = 1; subLR->_bf = 0; } //插入到 subLR 的右子树 else if (bf == 1) { subL->_bf = -1; parent->_bf = 0; subLR->_bf = 0; } //subLR 为叶子节点 else if (bf == 0) { subL->_bf = parent->_bf = 0; } else { //进行差错处理 assert(false); } }在这里面就不需要更新 _parent 指针了，因为 RotateL 与 RotateR 函数会帮助我们更新的。
右左双旋
右左双旋与左右双旋恰好相反，与左单旋的情况类似，在下面这种情况下会进行右左双旋。
就是在原本更高的右子树里再插入节点，只不过不是在 28 的右子树中插入，而是在左子树中插入；即不是在 C 中插入，而是在 B 中插入，这时候就需要进行右左双旋。
右左双旋的旋转步骤
从名字来看，右左双旋呢就是先经历一次右单旋，再进行一次左单旋。以上面的抽象图来说步骤就是：
a. 先以 28 为父亲节点进行一次右单旋，也就是 RotateR(28)
b. 再以 20 为父亲节点进行一次左单旋，也就是 RotateL(20)
右左双旋呢，也分为三种情况，与左右双旋的三种情况类似。具体三种情况如图。
情况一
情况一是在 20 的右子树的 28 的左子树 25 的右子树中插入节点导致右子树高，进行右左双旋后的树如图所示。
旋转之后，25 与 28 的平衡因子变为了 0, 20 的平衡因子变为了 -1。
情况二
节点因为插入在了 20 的孙子节点 25 的左子树而导致右子树变高，进行右左双旋后的树如图所示。
此时平衡因子是 25 和 20 更新为了 0, 28 更新为了 1。
情况三
第三种情况就是插入的 25 为叶子节点的情况，此时右左双旋之后的树如图所示。
此时三个节点的平衡因子都更新到了 0。
右左双旋代码
void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; //先以 subR 为 parent 进行右单旋 RotateR(subR); //再以 parent 为 parent 进行左单旋 RotateL(parent); //根据不同情况更新平衡因子 if (bf == 0) { subR->_bf = parent->_bf = 0; } else if (bf == -1) { parent->_bf = 0; subR->_bf = 1; subRL->_bf = 0; } else if (bf == 1) { parent->_bf = -1; subR->_bf = 0; subRL->_bf = 0; } else { assert(false); } }上面就是旋转的四种情况，尤其是双旋，比较复杂，但是理清了逻辑之后还是很好实现的。
3） AVLTree 的查找
查找的话就很简单了，跟 BST 的查找逻辑相同，这里就不再赘述。只不过对于 AVL 树来说，其查找效率是 O(logN) 的，效率更高。
查找代码
Node* Find(const K& key) { Node* cur = _root; while (cur) { if (key > cur->_data.first) cur = cur->_right; else if (key < cur->_data.first) cur = cur->_left; else return cur; } return nullptr; }3 AVLTree 的检测
由于 AVL 树的结构比较复杂，所以我们这里可以采用一定的算法来检测当前这棵树是否是 AVL 树，这里我们采用检测每个节点平衡因子的方法来检测是否是一棵 AVL 树。
既然检测平衡因子，首先我们先需要一个计算二叉树高度的函数，之后我们计算出左子树的高度与右子树的高度，用右子树高度减去左子树高度就得到了当前节点的平衡因子，然后我们检测平衡因子的绝对值是否大于等于 2，如果是，那就说明高度出问题了；如果平衡因子与当前节点的平衡因子不相等，那就说明是平衡因子出问题了。
计算二叉树高度
这个函数我们在二叉树时实现过，首先如果是空树，那高度肯定为0；然后我们递归的计算左子树高度，再递归的计算右子树高度；最后返回的是左右子树高度中较大值 + 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; }检测是否平衡
这个函数也很简单。首先，如果是一棵空树，那肯定是一棵 AVL 树；然后计算出左子树高度，再计算出右子树高度，用右子树高度减去左子树高度得到平衡因子，然后判断平衡因子绝对值是否大于等于 2 或者是否与当前节点平衡因子相等；最后再递归的检查左子树与右子树是否是二叉平衡树就可以了。
代码
bool _IsBalance(Node* root) { //空树也是一棵AVL树 if (root == nullptr) return true; int LeftHeight = Height(root->_left); int RightHeight = Height(root->_right); int dif = RightHeight - LeftHeight; if (dif >= 2 || dif <= -2) { std::cout << root->_data.first << "高度差异常" << std::endl; return false; } if (dif != root->_bf) { std::cout << root->_data.first << "平衡因子异常" << std::endl; return false; } //如果左边与右边都是AVL树，那就是一棵AVL树 return _IsBalance(root->_left) && _IsBalance(root->_right); }4 总结
在这里给出 AVLTree 的所有实现代码：
//AVLTree.hpp #pragma once #include <iostream> #include <assert.h> using namespace std; template<class K, class V> struct AVLNode { pair<K, V> _data; AVLNode<K, V>* _left; AVLNode<K, V>* _right; AVLNode<K, V>* _parent; int _bf; AVLNode(const pair<K, V>& data) :_data(data) ,_left(nullptr) , _right(nullptr) ,_parent(nullptr) ,_bf(0) {} }; template<class K, class V> class AVLTree { typedef AVLNode<K, V> Node; void RotateR(Node* parent) { Node* Parent = parent->_parent; Node* subLR = parent->_left->_right; Node* subL = parent->_left; //不要忘记更改父亲的指向 //parent 可能为根节点 if (parent == _root) _root = subL; else { if (parent == Parent->_left) Parent->_left = subL; else Parent->_right = subL; } //subL 的父亲节点也需要更改 subL->_parent = Parent; //更改左右孩子指向 parent->_left = subLR; subL->_right = parent; //不要忘记更改 parent 以及 subLR 的父亲指向 parent->_parent = subL; if (subLR) subLR->_parent = parent; //最后不要忘记更新平衡因子 subL->_bf = parent->_bf = 0; } void RotateL(Node* parent) { Node* Parent = parent->_parent; Node* subR = parent->_right; Node* subRL = subR->_left; //不要忘记更改父亲的指向 //parent 可能为根节点 if (parent == _root) _root = subR; else { if (parent == Parent->_left) Parent->_left = subR; else Parent->_right = subR; } //subR 的父亲节点也需要更改 subR->_parent = Parent; //更改孩子指向 subR->_left = parent; parent->_right = subRL; //不要忘记更改 parent 与 subRL 的父亲指向 parent->_parent = subR; if (subRL) subRL->_parent = parent; //更新平衡因子 parent->_bf = subR->_bf = 0; } void RotateLR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; int bf = subLR->_bf; //先以 subL 为 parent 进行左单旋 RotateL(subL); //再以 parent 为 parent 进行右单旋 RotateR(parent); //根据三种情况进行平衡因子的更新 //插入到 subLR 的左子树 if (bf == -1) { subL->_bf = 0; parent->_bf = 1; subLR->_bf = 0; } //插入到 subLR 的右子树 else if (bf == 1) { subL->_bf = -1; parent->_bf = 0; subLR->_bf = 0; } //subLR 为叶子节点 else if (bf == 0) { subL->_bf = parent->_bf = 0; } else { //进行差错处理 assert(false); } } void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; //先以 subR 为 parent 进行右单旋 RotateR(subR); //再以 parent 为 parent 进行左单旋 RotateL(parent); //根据不同情况更新平衡因子 if (bf == 0) { subR->_bf = parent->_bf = 0; } else if (bf == -1) { parent->_bf = 0; subR->_bf = 1; subRL->_bf = 0; } else if (bf == 1) { parent->_bf = -1; subR->_bf = 0; subRL->_bf = 0; } else { assert(false); } } int _Height(Node* root) const { if (root == nullptr) return 0; int LeftHeight = _Height(root->_left); int RightHeight = _Height(root->_right); return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1; } bool _IsBalance(Node* root) const { //空树也是一棵AVL树 if (root == nullptr) return true; int LeftHeight = _Height(root->_left); int RightHeight = _Height(root->_right); int dif = RightHeight - LeftHeight; if (dif >= 2 || dif <= -2) { std::cout << root->_data.first << "高度差异常" << std::endl; return false; } if (dif != root->_bf) { std::cout << root->_data.first << "平衡因子异常" << std::endl; return false; } //如果左边与右边都是AVL树，那就是一棵AVL树 return _IsBalance(root->_left) && _IsBalance(root->_right); } size_t _size(Node* root) const { //利用递归来算节点个数 if (root == nullptr) return 0; return _size(root->_left) + _size(root->_right) + 1; } public: bool Insert(const pair<K, V>& data) { if (_root == nullptr) { _root = new Node(data); return true; } Node* cur = _root, *parent = nullptr; while (cur) { if (data.first > cur->_data.first) { parent = cur; cur = cur->_right; } else if (data.first < cur->_data.first) { parent = cur; cur = cur->_left; } else return false; } //找到了该插入的位置 cur = new Node(data); //更改parent 指向 if (data.first > parent->_data.first) parent->_right = cur; else parent->_left = cur; //不要忘记更改 cur 的 _parent 指针 cur->_parent = parent; //更新平衡因子 while (parent) { if (cur == parent->_left) --parent->_bf; else ++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) { Node* subL = parent->_left; if (subL->_bf == -1) { //右单旋 RotateR(parent); } else if (subL->_bf == 1) { //左右双旋 RotateLR(parent); } else { assert(false); } } else { Node* subR = parent->_right; if (subR->_bf == 1) { //左单旋 RotateL(parent); } else if (subR->_bf == -1) { //右左双旋 RotateRL(parent); } else { assert(false); } } //结束之后，也不需要更新了 break; } else { //为了处理平衡因子出错的情况 assert(false); } } return true; } Node* Find(const K& key) { Node* cur = _root; while (cur) { if (key > cur->_data.first) cur = cur->_right; else if (key < cur->_data.first) cur = cur->_left; else return cur; } return nullptr; } size_t Height() const { return _Height(_root); } bool IsBalance() const { return _IsBalance(_root); } size_t size() const { return _size(_root); } private: Node* _root = nullptr; }; //testAVLTree.cpp #include "AVLTree.hpp" #include <vector> int main() { //这里直接采用随机值测试 const int N = 100000; vector<int> v; v.reserve(N); srand(time(NULL)); for (size_t i = 0; i < N; i++) { v.push_back(rand() + i); } //测试性能 size_t begin1 = clock(); AVLTree<int, int> t; for (auto& e : v) { t.Insert({ e, e }); } size_t end1 = clock(); cout << "Insert: " << end1 - begin1 << endl; cout << "is balance: " << t.IsBalance() << endl; cout << "Height: " << t.Height() << endl; cout << "Size: " << t.size() << endl; //查找 size_t begin2 = clock(); for (size_t i = 0; i < N; i++) { t.Find(rand() + i); } size_t end2 = clock(); cout << "Find: " << end2 - begin2 << endl; return 0; }这篇文章主要是讲解第一个二叉平衡树 -- AVL 树的实现，其中最难的就是如何旋转来实现树的平衡。旋转共包括 4 种旋转：右单旋、左单旋、左右双旋、右左双旋，双旋中又各有三种不同的旋转场景。
本篇文章并没有讲解删除节点，如果大家有兴趣可以自己学习之后实现一下。
