跳到主要内容C++ AVL 树详解：概念、插入与旋转 | 极客日志C++算法
C++ AVL 树详解：概念、插入与旋转
AVL 树是一种自平衡二叉查找树，通过控制左右子树高度差不超过 1 来保证平衡。文章介绍了 AVL 树的概念、平衡因子定义、插入操作中的平衡因子更新机制以及四种旋转方式（左单旋、右单旋、左右双旋、右左双旋）的实现原理。重点阐述了如何通过 parent 指针追踪路径并判断是否需要旋转，确保增删查改效率维持在 O(logN)。
古灵精怪4 浏览 AVL 树
概念
- AVL 树是最先发明的自平衡二叉查找树，AVL 是一颗空树，或者具备下列性质的二叉搜索树：它的左右子树都是 AVL 树，且左右子树的高度差的绝对值不超过 1。AVL 树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。
- AVL 树得名于它的发明者 G.M.Adelson-Velsky 和 E.M.Landis 是两个前苏联的科学家，他们在 1962 年的论文《An algorithm for the organization of information》中发表了它。
- AVL 树实现这里我们引入一个平衡因子(balance factor) 的概念，每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1。AVL 树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像一个风向标一样。
- 为什么 AVL 树是高度平衡搜索二叉树，要求高度差不超过 1，而不是高度差是 0 呢？不是不想这样设计，而是有些情况是做不到高度差是 0 的。比如一棵树是 2 个结点，4 个结点等情况下，高度差最好就是 1，无法作为高度差是 0。
- AVL 树整体结点数量和分布和完全二叉树类似，高度可以控制在 logN，那么增删查改的效率也可以控制在 O(logN)，相比二叉搜索树有了本质的提升。
不平衡示例：
AVL 树的实现
结点结构：
以前我们的树结点指针里存放值和左右孩子结点指针，现在多出了一个 parent 结点以及平衡因子，而且存的值是 pair 类型的。
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) {}
};
树的大概框架：
template<class , >
{
AVLTreeNode<K, V> Node;
:
:
Node* _root = ;
};
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
K
class
V
class
AVLTree
typedef
public
private
nullptr
AVL 树的插入
我们可以先写出和原本区别不大的部分，比如肯定都是先比当前值小就往左走，比当前值大就往右走……
bool insert(const pair<K, V>& kv) {
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur) {
if (kv.first < cur->_kv.first) {
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first) {
parent = cur;
cur = cur->_right;
}
else {
return false;
}
}
cur = new Node(kv);
cur->_parent = parent;
return true;
}
我们先停在这一步，接下来我们需要考虑怎么去更改原本存在的结点的平衡因子以及控制平衡的问题，因为新插入的结点的平衡因子肯定是 0 不需要改，直接用缺省值。
注意更新原则的第 2 点，只有子树高度变化才会影响当前平衡因子。也就是说对于插入结点的某个祖先来说，如果其实左右子树高度差并没有变化，就没有影响到它的平衡因子，也就是插入一个结点并不一定会影响它的全部祖先。
对于最上面这个节点来说，原本平衡因子就为 -1，插入后还是 -1。
下图我们可以看到更新平衡因子我们需要倒着往祖先走不断更新直到不需要再更新，所以这就是为什么要在结点里设计 parent 指针。
有些地方有人没有设计 parent。而是通过栈或 vector 将路径存起来：8 10 14 13。更新的时候就在容器中不断去取。但有 parent 更便利。parent 不是必须的。
第 4 点：我们从第 3 点原则知道插入结点的 parent 结点的平衡因子是肯定会改变的，要么 ++ 要么--，但是是否会继续往上更新，得看parent 所在子树的高度是否变化。
如果本来这棵树就没有变高，parent 以上的结点的平衡因子就不会改变。
所以接下来的关键问题就是，怎么知道 parent 所在子树的高度是否变化呢？
仍然以上面这张图为例，我们看更新停止条件的第 2 点：
更新后 parent 的平衡因子等于 1 或 -1，parent 所在子树高度肯定变了。因为这说明 parent 的平衡因子的变化过程要么是 0->1，要么是 0->-1，因为根据我们的更新原则的第 3 点，这个 parent 的平衡因子要么是 ++ 得到的要么是--得到的，说明它原来是 0。（倒推思考）因为如果不是这样的话，插入之前根本就不是 AVL 树了。（我们前提它是一颗 AVL 树，要插入后继续保持为 AVL 树）；所以这种情况的高度就增加了，所以要继续往上更新平衡因子。
可以看到对于现在的 parent 来说，插入结点是在右子树的，所以平衡因子要 ++，1->2。
所以现在我们来到了更新停止条件的第 3 种：更新后 parent 的平衡因子等于 2 或 -2：同样我们进行倒推，++ 或者--来到 2 或者 -2，说明原本是 1->2 或者 -1->-2，同样只能是这两种情况，否则原本根本就不是 AVL 树了。这种情况说明我们的插入结点到了本来就更高的那一边，破坏了平衡，可以说是'雪上加霜'。我们需要旋转处理。旋转之后也不需要再往上继续更新了，因为旋转顶多让它的高度降低 1，而原本是 AVL 树，降低 1 又变回了 AVL 树。
我们再来看下面这张图，parent 走到 3，因为插入结点在其左子树，平衡因子--，也就是更新后 parent 的平衡因子等于 0 的情况：倒推得出是从 1->0 或者从 -1->0 的。这说明原本这棵树是一边高一边低，但是现在变成平衡了，所以也不用继续往上更新了。这种让不平衡的树变平衡了的，可以说'雪中送炭'。
所以如果更新后 parent 的平衡因子为 0，我们才不需要继续更新，否则就要更新。
可以说更新的继续条件是更新后 parent 的平衡因子为 1 或 -1，而更新停止的条件是更新后 parent 的平衡因子为 0 或 2 或 -2。
但在一种情况下，更新后 parent 的平衡因子为 1 或 -1，却也结束了：
也就是已经更新到根结点的情况。如果 parent 都已经走到根了，也没法再继续往上更新了。
while (parent) {
if (parent->_left == cur) parent->_bf -= 1;
else parent->_bf += 1;
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) {
}
else {
assert(false);
}
}
旋转
旋转的原则
- 保持搜索树的规则
- 让旋转的树从不平衡变平衡，其次降低旋转树的高度
旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。
右单旋
本图 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 整棵树的一个局部子树，旋转后不会再影响上一层，插入结束了。
具体来看：
情况 1：
假如 abc 现在是这种情况，也就是都为空树，插入 a 后向上调整到 10 发现平衡因子为 -2，所以需要旋转。
怎么旋转？让 5 的右子树也就是 b 变成 10 的左边，10 变成 5 的右子树，就得到了最右边的这种。
这就是抽象的情况之外的具体情况 1，是较为简单的一种情况：插入前 abc 高度都为 h 而 h 为 0。
情况 2：
可以看到就是把 5 的右子树变为 10 的左子树，然后把 10 变为 5 的右子树。
所以从上面我们可以看出，无论 h 是 0 还是 1，旋转的逻辑都是一样的。
情况 3：
第三层可以有 1 个结点，2 个，3 个，各自有 4、6、4 种情况，一共 14 种，再加上满二叉树情况，一共 15 种情况。
bc 各有 15 种情况，所以 bc 有 15*15=256 种情况。
我们再来看a 的情况：a 要保证的是插入了之后自己没有发生旋转（也就是在 a 子树以上的部分进行旋转），但是高度又变了所以往上调整。
a 如果是 x 这种满二叉树的结构，插入位置有 8 个。
其次，如果 a 不是满二叉树的结构，a 的结构最后一层必须保留 3 个结点，否则也无法满足我们要在 a 插入后自己没有发生旋转但高度又改变的条件。
如果插入到左下角结点，自身就要旋转了；如果插入到右边 3 个位置则 y-C 这棵树的高度并没有变化，也不会引发以上的结点的平衡因子的变化。
我们可以对比一下这两种情况，左边这种是 4 个结点的左右孩子处都可以插入，也就是 8 种情况；右边这种是只能在有两个结点的位置插入，因为如果在左边要么就不会引发向上更新要么就自身旋转了。4 个结点保留 3 个有 4 种情况，每种情况都在有两个结点的那边插入，有 4 种插入情况（因为有两个节点），所以一共有 8+4*4 种 a 的情况。
a 的情况
bc 的情况就是 15 *15(8+4 *4) 最终为 5400 种情况。
左单旋
这是一个 10 为根的树，有 a、b、c 抽象为三棵高度为 h(h>0) 的子树，a、b、c 均符合 AVL 树的要求。
我们可以看到，15 这个结点的平衡因子是 0，10 这个节点的平衡因子是 1。
10 可能是整棵树的根，也可能是一个整棵树中局部的子树的根。
这是一种概括抽象表示，这代表了所有右单旋的场景，实际右单旋形态有很多种。
可以看到在 a 子树中插入一个新节点，导致 a 子树的高度从 h 变成 h+1，不断向上更新平衡因子，导致 10 的平衡因子从 1 变成 2，10 为根的树左右高度差超过 1，违反平衡规则。所以需要往左边旋转，控制两棵树的平衡。
旋转方式：b 变成 10 的右子树，10 变成 15 的左子树，15 成为这棵树的新的根。因为 b 一定比 10 大，所以可以成为 10 的右子树；10 比 15 小，所以可以变成 15 的左子树。这都满足二叉搜索树规则。
10、b、c 都比 15 小，所以做它的左子树没有问题。
