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 种旋转：右单旋、左单旋、左右双旋、右左双旋，双旋中又各有三种不同的旋转场景。
本篇文章并没有讲解删除节点，如果大家有兴趣可以自己学习之后实现一下。
