跳到主要内容 C++ AVL 树详解：概念、插入与旋转操作 | 极客日志
C++ 算法
C++ AVL 树详解：概念、插入与旋转操作 介绍 C++ 中 AVL 树的定义、平衡因子计算及插入机制。详细阐述了四种旋转操作（左单旋、右单旋、左右双旋、右左双旋）的原理与代码实现，用于维持二叉搜索树的平衡性。同时提供了树高度计算与平衡验证函数，确保数据结构符合 AVL 标准。
疯疯癫癫 发布于 2026/3/22 更新于 2026/4/16 C++ AVL 树详解：概念、插入与旋转操作
1. AVL 树的概念
在前面我们介绍了二叉搜索树，这棵树可以用来进行查找操作，其查找的时间复杂度取决于该树的高度。最好的情况是该树接近于满二叉树，查找的时间复杂度为 O(log2N)。但是由于其特定的插入方式导致我们无法控制树的高度，使得每一个结点两边子树的高度差距过大，导致它的高度会接近于 N，使得查找的时间复杂度变为 O(N)。
有没有一种方法可以使得我们的二叉搜索树的查找效率恒为 O(log2N)？答案是有的，也就是本章要介绍的 AVL 树，即平衡二叉搜索树。
从名字可以看到，平衡二叉搜索树与二叉搜索树间的区别就在于'平衡'二字！对于平衡二叉搜索树叫做 AVL 树是得益于它的发明者 G. M. Adelson-Velsky 和 E. M. Landis 是两个前苏联的科学家，因此采用他们名字的缩写来命名这棵特殊的二叉搜索树。
AVL 树是一颗空树或者具备下列性质的二叉搜索树：它的左右子树都是 AVL 树，且左右子树的高度差的绝对值不超过 1。AVL 树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。
由此我们可以得知平衡二字指的是每一个结点的左右子树的高度要保持平衡，高度差不能超过 1。
AVL 树整体结点数量和分布和完全二叉树类似，高度可以控制在 log2N，那么增删查改的效率也可以控制在 log2N，相比二叉搜索树有了本质的提升。
2. 平衡因子
了解了平衡之后我们知道对于 AVL 树来说最重要的就是控制平衡。那么我们该怎么去判断一棵二叉搜索树是否平衡呢？这里引入了一个新的概念：平衡因子 (balance factor) 。在 AVL 树中每一个结点都有一个平衡因子，它的值等于该结点的右子树高度减去左子树高度，也就是说在 AVL 树中每一个结点的平衡因子的值都只能为 1、-1、0，否则该树就不是一棵 AVL 树。但是 AVL 树并不是必须要平衡因子，只是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像一个风向标一样。
AVL 树的结构
那么有了平衡因子后 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 ) {}
};
template <class K , class V >
class AVLTree {
typedef AVLTreeNode<K, V> Node;
public :
private :
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
nullptr
因为之前我们学习 set 和 map 时了解了 pair 类，因此这里直接采用 key_value 的模式。把上面的代码与我们之前二叉搜索树的代码做比较，可以发现，AVL 树只比二叉搜索树多了两个成员变量，分别是父节点的指针和平衡因子。新增父节点的指针是为了在 AVL 树中插入数据时可以更好的更新平衡因子。
3. AVL 树的插入
3.1 插入的大致过程 对于 AVL 树的插入我们仍按照正常二叉搜索树的插入方式去进行插入，不过再插入过后需要对相应的平衡因子进行更新，因为插入一个数据可能会导致树的高度变化。
新增结点后，如果高度增加，那么只会影响该结点的祖先结点的高度，也就是会影响到祖先结点的平衡因子。
当我们插入了结点 9 之后，它的祖先结点的平衡因子可能会被影响，也就是 8 和 6，插入完成之后，我们需要对可能被影响的结点的平衡因子进行更新。
所以更新从新增结点->根结点路径上的平衡因子，最坏情况下要更新到根结点，有些情况更新到中间就可以停止了，具体情况我们下面再详细分析。
在平衡因子更新的途中，如果某个结点的平衡因子的变为 -2 或 2，则说明插入数据之后导致该树变得不平衡了，因此需要对不平衡的子树进行旋转 操作，使这棵树从不平衡变为平衡，还是一棵 AVL 树。至于什么是旋转我们下面再详细介绍。
当更新平衡因子的途中没有出现问题，那么插入操作就结束了。下面让我们来看一看平衡因子到底该怎么更新。
3.2 平衡因子的更新
更新原则：
平衡因子 = 右子树高度 - 左子树高度
只有子树高度变化才会影响当前结点平衡因子。
插入结点，会增加高度，所以新增结点在 parent 的右子树，parent 的平衡因子++，新增结点在 parent 的左子树，parent 平衡因子–。 parent 所在子树的高度是否变化决定了是否会继续往上更新。
插入的结点的平衡因子为 0。
更新之后：
不断更新，更新到根结点，根结点的平衡因子不为 2 或 -2，插入结束。
更新后 parent 的平衡因子等于 2 或 -2，说明在更新前 parent 的平衡因子为 1 或者 -1，更新前 parent 子树一边高一边低，新增的插入结点在高的那边，parent 所在的子树高的那边更高了，破坏了平衡，parent 所在的子树不符合平衡要求，需要旋转 处理，通过旋转操作使子树变得平衡且高度降低 1，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束。
更新后 parent 的平衡因子等于 1 或 -1，说明在更新前 parent 的平衡因子为 0，更新前 parent 子树两边一样高，新增的插入结点后，parent 所在的子树一边高一边低（高度差为 1），parent 所在的子树符合平衡要求，但是高度增加了 1，会影响 parent 的父亲结点的平衡因子，所以要继续向上更新。
更新后 parent 的平衡因子等于 0，说明在更新前 parent 的平衡因子为 1 或者 -1，更新前 parent 的子树一边高一边低（差值为 1），新增的结点插入在低的那边，插入后 parent 所在的子树高度不变，不会影响 parent 的父亲结点的平衡因子，插入结束。
总的来说，更新平衡因子我们需要去遍历插入结点的所有祖先结点，在更新这些祖先结点的途中，如果更新完平衡因子为 0，那么就停止循环，插入结束；如果更新完平衡因子为 2 或 -2，那么通过旋转操作后停止循环，插入结束；如果更新后为 1 或 -1，那么继续向上循环更新，直到根结点。下面我们来看一下代码实现：
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--;
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 ;
}
4. 旋转 上面在更新平衡因子时，当我们的树不平衡时需要通过旋转操作来使我们的树重新变为平衡，由此可见旋转是 AVL 树的重中之重，也是 AVL 树的根基，是 AVL 树之所以能够平衡的原因。
4.1 旋转的目标：
把 parent 子树旋转平衡。
降低 parent 子树的高度
针对不同的情况，我们的旋转一共分为四种：右单旋、左单旋、右左双旋，左右双旋 。下面让我们分别看一下这些旋转操作的原理以及如何实现。
在上图中，a、b、c 为是三棵子树且均为 AVL 树，我们把它们抽象为一个个整体式为了方便旋转的进行，这是因为在进行右单旋时我们只需要用到这三棵子树的第一个结点，其他的结点不会影响我们的右单旋操作。这里可以看到 a、b、c 这三颗子树的高度都是相同的，都为 h，可能大家会对此感到疑惑，如果不都为 h 呢？上图只是 AVL 树的一种情况，随着我们的讲解相信可以解答你的疑惑。
4.2 右单旋 对于上图的 AVL 树，我们新插入一个结点，如果这个结点大于 10，往右边走，那么 b 子树的高度可能不变也可能加一。
我们假设 b 子树是箭头所指的那棵树，高度为 3，那么当我们插入数据时这个结点可能存在的位置有七种情况，我们可以看到在这七种情况中有六种情况 b 子树的高度加一，一种情况 b 子树的高度不变，不论高度是否加一通过更新平衡因子后我们都可以发现并不会出现不平衡的情况，也就是说如果插入的结点在 b 子树下，那么就不需要进行旋转，因为它已经是平衡的了。
那么当插入的数据在 a 子树并且 a 子树的高度加一，那么就会导致 10 这个结点的平衡因子更新为 -2，10 为根的树左右高度差超过 1，违反平衡规则。10 为根的树左边太高了，需要往右边旋转，也就是进行右单旋，控制两棵树的平衡。
从上图我们也能看出，当parent 的平衡因子为 -2，parent->left 的平衡因子为 -1 时，我们需要进行右单旋 。右单旋的具体操作步骤如下（以上图为例）：
1、把 b 变为 10 的左子树
2、10 变成 5 的右子树
3、5 成为这棵树新的根
4、旋转完成后的平衡因子只需要把 5 和 10 的改为 0 即可
因为 5 < b 子树的值 < 10，将 b 变成 10 的左子树，10 变成 5 的右子树，5 变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的高度恢复到了插入之前的 h+2，符合旋转原则。如果插入之前这棵树是一个局部子树，旋转后不会再影响上一层，插入结束了。
void RotateR (Node* parent) if (subLR)
subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root) {
_root = subL;
subL->_parent = nullptr ;
} else {
if (parent == Pparent->_left) {
Pparent->_left = subL;
} else {
Pparent->_right = subL;
}
subL->_parent = Pparent;
}
parent->_bf = 0 ;
subL->_bf = 0 ;
}
4.3 左单旋 左单旋的使用场景与右单旋刚好相反，当最右子树的高度高于左边时，我们要进行左单旋。
也就是 a 子树的高度加一时，我们要进行左单旋，这时 a 子树是右子树。从上图我们也能看出，当parent 的平衡因子为 2，parent->right 的平衡因子为 1 时，我们需要进行左单旋 。左单旋的具体操作步骤如下（以上图为例）：
1、把 b 变为 10 的右子树
2、10 变成 15 的左子树
3、15 成为这棵树新的根
4、旋转完成后的平衡因子只需要把 10 和 15 的改为 0 即可
因为 10 < b 子树的值 < 15，将 b 变成 10 的右子树，10 变成 15 的左子树，15 变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的高度恢复到了插入之前的 h+2，符合旋转原则。如果插入之前 10 整棵树的一个局部子树，旋转后不会再影响上一层，插入结束了。
void RotateL (Node* parent) if (subRL)
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root) {
_root = subR;
subR->_parent = nullptr ;
} else {
if (parent == Pparent->_left) {
Pparent->_left = subR;
} else {
Pparent->_right = subR;
}
subR->_parent = Pparent;
}
parent->_bf = 0 ;
subR->_bf = 0 ;
}
左单旋和右单旋的思路是一致的，我们可以把它们看作互为镜像，一个用于最左子树高于右子树的情况，一个用于最右子树高于左子树的情况。
4.4 左右双旋 在下图中，如果 a 子树的高度加一，我们要进行右单旋，那么如果是 b 子树的高度的高度加一呢？
下面让我们来看一看如果是 b 子树的高度加一通过右单旋还能否解决我们的问题：
通过上图我们可以看到再对其进行右单旋后 5 的平衡因子变为了 2，还是处于不平衡状态，右单旋并不能解决我们的问题，那么对于parent 的平衡因子为 -2，parent->left 的平衡因子为 1 时，我们需要通过左右双旋 去解决。
左右双旋，顾名思义，进行两次旋转，先进行左单旋，再进行右单旋。
右单旋解决的纯粹的左边高，但是插入在 b 子树中，10 为跟的子树不再是单纯的左边高，对于 10 是左边高，但是对于 5 是右边高，需要用两次旋转才能解决，以 5 为旋转点进行一个左单旋，以 10 为旋转点进行一个右单旋，这就叫做左右双旋，这样这棵树就平衡了。
对于这种情况，我们需要先以 5 为旋转点进行左单旋，然后再以 10 为旋转点进行右单旋。这时我们需要再将 b 子树近一步进行拆解，以便进行左单旋。
我们将 b 子树分为一个结点以及这个结点的左右子树 e、f，我们假设这个结点的值为 8。8 的左右子树的高度都为 h-1。当我们插入一个结点到 b 子树中时，它有可能在 e 子树下，使 e 子树的高度加一，也有可能在 f 子树下，使 f 子树的高度加一，我们需要分类讨论这是因为不同的位置会导致旋转完成之后更新的平衡因子不同。
从上图我们可以看到，新增的结点在 e 子树下和在 f 子树下会导致最后 5 和 10 结点的平衡因子不同，因此我们在进行左右双旋之前要先记录 8 位置的平衡因子，方便旋转完后正确的更新平衡因子。
下面我们来将上图中第一中情况的旋转步骤详细地给大家画出来，方便大家理解：
除此之外还有一种特殊情况，也就是 a、b、c 三棵子树的高度为 0，也就是都为空树时：
这种情况也是先对 5 进行左旋，然后对 10 进行右旋，步骤是一样的，不同的地方在于平衡后 5 和 10 结点的平衡因子都变为 0。总的来说要进行左右旋转的情况是parent 的平衡因子为 -2，parent->left 的平衡因子为 -1 ，此外我们还需要记录 parent->left->right 的平衡因子 ，以便更新对应结点平衡后的平衡因子。
下面让我们来看一下代码演示，双旋的思路虽然不太好想，但是代码很好写，只需要复用我们之前写过的左单旋和右单旋即可：
void RotateLR (Node* parent) 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 );
}
}
4.5 右左双旋 与左右双旋相同，右左双旋是用于解决左单旋无法解决问题的时候，也就是说新插入的元素使 b 子树的高度加一，观察下图：
至于为什么要进行右左双旋与上面进行左右双旋的原因是一样的，这里就不再赘述。与左右双旋刚好相反，右左双旋的操作是先以 15（以上图为例）为旋转点进行右单旋，然后以 10 为旋转点进行左单旋即可。
和左右双旋一样，我们要先将 b 子树进行进一步拆解，以便进行右单旋。对于旋转后相应结点的平衡因子更新我们也需要提前记录 b 子树根节点的平衡因子。下面来让我们直接看其中一种情况的具体旋转过程：
void RotateRL (Node* parent) 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 );
}
}
4.6 旋转小结 上面四种旋转情况便能解决我们在 AVL 树中遇到不平衡的问题，下面我们来做一个总结，看一看在什么情况下用哪种旋转：
右单旋：parent 的平衡因子为 -2，parent->left 的平衡因子为 -1
左单旋：parent 的平衡因子为 2，parent->right 的平衡因子为 1
左右单旋：parent 的平衡因子为 -2，parent->left 的平衡因子为 1
右左单旋：parent 的平衡因子为 2，parent->right 的平衡因子为 -1
5. AVL 的其他功能 其实对于 AVL 树来说，最重要的功能就是旋转，只要我们掌握了旋转，那么就可以说我们掌握了 AVL 树。AVL 树的查找操作与普通的二叉搜索树基本上一模一样，它的插入和删除操作与普通的二叉搜索树相比都是只多了更新平衡因子的操作，在平衡因子更新后不合法时对其进行旋转。具体的代码这里都不再一一进行详细介绍，大家可以自己去尝试写出来。
那么我们该如何检查一棵 AVL 树是否合格呢？相信大家可能会说可以通过判断平衡因子来检测，但如果平衡因子也出现异常了呢？因此我们需要通过检查左右子树高度差的程序进行反向验证，同时检查一下结点的平衡因子更新是否出现了问题。
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 (nullptr == root)
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);
}
大家如果感兴趣可以自己去尝试写一下 AVL 树的插入和删除操作的代码。
