跳到主要内容
C++:AVL 树原理、旋转策略与完整实现代码 | 极客日志
C++ 算法
C++:AVL 树原理、旋转策略与完整实现代码 AVL 树是一种自平衡二叉查找树,通过平衡因子控制左右子树高度差不超过 1。插入新节点后需更新平衡因子,若失衡则通过左旋、右旋或双旋恢复平衡。 AVL 树结构定义、平衡因子逻辑、四种旋转场景及 C++ 完整代码实现,包含插入测试与性能验证,帮助掌握数据结构核心算法。
灰度发布 发布于 2026/3/28 更新于 2026/4/27 7 浏览C++ 的两个参考文档
非官方文档:
官方文档(同步更新):
1 初识 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 树,但是那样会比较绕,最终还是来控制高度。
AVL 树是高度平衡搜索二叉树,要求高度差不超过 1,为什么不是高度差为 0 呢?0 不是更好的平衡吗?我们用画图软件实践操作一下就会发现:不是不想这样设计,而是有些情况是做不到高度差是 0 的——比如一棵树是 2 个结点,4 个结点等情况下,高度差最好就是 1,无法做到高度差是 0——也就是说,不是不想做,而是做不到!
AVL 树整体结点数量和分布和完全二叉树类似,高度可以控制在 logN,那么增删查改的效率也可以控制在 O(logN),相比二叉搜索树有了本质的提升。
2 AVL 树要点解析
2.1 AVL 树的平衡因子逻辑
2.2 AVL 树的插入
2.2.1 AVL 树插入一个值的过程
插入一个值按二叉搜索树规则进行插入。
新增结点以后,只会影响祖先结点的高度,也就是可能会影响部分祖先结点的平衡因子,所以更新从新增结点->根结点路径上的平衡因子,实际中最坏情况下要更新到根,有些情况更新到中间就可以停止了,具体情况我们下面再详细分析。
更新平衡因子过程中没有出现问题,则插入结束。
更新平衡因子过程中出现不平衡,对不平衡子树旋转,旋转后本质调平衡的同时,本质降低了子树的高度,不会再影响上一层,所以插入结束。
2.2.2 更新平衡因子
2.2.2.1 更新原则
插入结点,会增加高度,所以新增结点在 parent 的右子树,parent 的平衡因子++,新增结点在 parent 的左子树,parent 平衡因子--;
parent 所在子树的高度是否变化决定了是否会继续往上更新。
2.2.2.2 更新停止条件
更新后 parent 的平衡因子等于 0,更新中 parent 的平衡因子变化为 -1->0 或者 1->0,说明更新前 parent 子树一边高一边低,新增的结点插入在低的那边,插入后 parent 所在的子树高度不变,不会影响 parent 的父亲结点的平衡因子,更新结束。
更新后 parent 的平衡因子等于 1 或 -1,更新前更新中 parent 的平衡因子变化为 0->1 或者 0->-1,说明更新前 parent 子树两边一样高,新增的插入结点后,parent 所在的子树一边高一边低,parent 所在的子树符合平衡要求,但是高度增加了 1,会影响 parent 的父亲结点的平衡因子,所以要继续向上更新。
更新后 parent 的平衡因子等于 2 或 -2,更新前更新中 parent 的平衡因子变化为 1~>2 或者 -1~>-2,说明更新前 parent 子树一边高一边低,新增的插入结点在高的那边,parent 所在的子树高的那边更高了,破坏了平衡,parent 所在的子树不符合平衡要求,需要旋转处理,旋转的目标有两个——
不断更新,更新到根,跟的平衡因子是 1 或 -1 也停止了。
2.2.3 示例演示 更新到 10 结点,平衡因子为 2,10 所在的子树已经不平衡,需要旋转处理——
更新到中间结点,3 为根的子树高度不变,不会影响上一层,更新结束——
3 探讨 AVL 树的旋转问题
3.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 整棵树的一个局部子树,旋转后不会再影响上一层,插入结束了。
下面的四种情况演示只是作为参考,比较抽象,具象图画不完的,但是抽象图可以很好地代表具象图,具象图也是这个逻辑,大家作为参考就好了——
3.1.1 情况 1:插入前 a / b / c 高度 h == 0
3.1.2 情况 2:插入前 a / b / c 高度 h == 1
3.1.3 情况 3:插入前 a / b / c 高度 h == 2
3.1.4 情况 4:插入前 a / b / c 高度 h == 3
3.2 左单旋转 如下图所展示的是 10 为根的树,有 a / b / c 抽象为三棵高度为 h 的子树 (h >= 0),a / b / c 均符合 AVL 树的要求。10 可能是整棵树的根,也可能是一个整棵树中局部的子树的根。这里 a / b / c 是高度为 h 的子树,是一种概括抽象表示,他代表了所有右单旋的场景,实际右单旋形态有很多种,具体跟上面左旋类似。
在 a 子树中插入一个新结点,导致 a 子树的高度从 h 变成 h + 1,不断向上更新平衡因子,导致 10 的平衡因子从 1 变成 2,10 为根的树左右高度差超过 1,违反平衡规则。10 为根的树右边太高了,需要往左边旋转,控制两棵树的平衡。
旋转核心步骤,因为 10 < b 子树的值 < 15,将 b 变成 10 的右子树,10 变成 15 的左子树,15 变成这棵树新的根,符合搜索树的规则,控制了平衡,同时这棵的高度恢复到了插入之前的 h + 2,符合旋转原则。如果插入之前 10 整棵树的一个局部子树,旋转后不会再影响上一层,插入结束了。
3.3 左右双旋 通过下面情况 1 和情况 2 的两张图,我们可以观察到:**当左边高时,如果插入位置不是在 a 子树,而是插入在 b 子树,b 子树高度从 h 变成 h + 1,引发旋转,右单旋无法解决问题,右单旋后,我们的树依旧不平衡。**右单旋解决的纯粹的左边高,但是插入在 b 子树中,10 为跟的子树不再是单纯的左边高,对于 10 是左边高,但是对于 5 是右边高,需要用两次旋转才能解决——以 5 为旋转点进行一个左单旋,以 10 为旋转点进行一个右单旋,这棵树就平衡了。
这个顺序是有讲究的,不能调换,这里不能说先左单旋再右单旋,大家可以自己去画图软件上面画一画,这里一定是左单旋再右单旋,先变成纯粹的左单旋,再右单旋,才平衡。
3.3.1 情况 1:插入前 a / b / c 高度 h == 0
3.3.2 情况 2:插入前 a / b / c 高度 h == 1 上面两张图分别为左右双旋中 h == 0 和 h == 1 两种情况的具体场景的流程分析,下面我们将 a / b / c 子树抽象为高度 h 的 AVL 子树进行分析,另外我们需要把 b 子树的细节进一步展开为 8 和左子树高度为 h -1 的 e 和 f 子树,因为我们要以 b 的父亲节点 5 为旋转点进行左单旋,左单旋需要动 b 树中的左子树。b 子树中新增结点的位置不同,平衡因子更新的细节也不同,通过观察 8 的平衡因子不同,这里我们要分三个场景讨论——
3.4 右左双旋 了解了左右双旋转的实现逻辑之后,右左双旋的流程也可以自己试着分析一下。
4 AVL 树的实现层
4.1 AVL 树的结构
4.2 AVL 树的插入 AVL 树的插入,跟搜索二叉树的插入规则一样,多了一个平衡因子(右子树高度 - 左子树高度),其它都是一样的,我们可以直接复用搜索二叉树的插入即可,不过还是有区别的——
4.3 AVL 树的旋转:实现
4.3.1 右单旋转
4.3.2 左单旋转
4.3.3 左右双旋
4.3.4 右左双旋
4.4 AVL 树的删除 AVL 树的删除我们不做过多介绍,很复杂,像前面介绍二叉搜索树的时候也是,插入并不复杂,但是删除非常麻烦,AVL 树底层是一棵搜索二叉树,所以它的删除也是非常棘手的一个问题!
图书推荐:《殷人昆 数据结构:用面向对象方法与 C++ 语言描述》
简单介绍一下 AVL 树删除的一个大致过程:用搜索二叉树的方式进行删除——
5 完整代码示例与实践演示(测试)
AVLTree.h: #pragma once
#include <iostream>
#include <vector>
using namespace std;
#include <assert.h>
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 >
struct AVLTree {
typedef AVLTreeNode<K, V> Node;
public :
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 ) {
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);
} else {
assert (false );
}
break ;
} else {
assert (false );
}
}
return true ;
}
void RotateR (Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr ;
} else {
if (parentParent->_left == parent)
{
parentParent->_left = subL;
} else {
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
parent->_bf = subL->_bf = 0 ;
}
void RotateL (Node* parent) {
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
Node* parentParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root) {
_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 ;
}
void RotateLR (Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL (parent->_left);
RotateR (parent);
if (bf == 0 ) {
parent->_bf = 0 ;
subL->_bf = 0 ;
subLR->_bf = 0 ;
} else if (bf == 1 ) {
parent->_bf = 0 ;
subL->_bf = -1 ;
subLR->_bf = 0 ;
} else if (bf == -1 ) {
parent->_bf = 1 ;
subL->_bf = 0 ;
subLR->_bf = 0 ;
} else {
assert (false );
}
}
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 );
}
}
Node* Find (const K& key) {
Node* cur = _root;
while (cur) {
if (cur->_kv.first < key) {
cur = cur->_right;
} else if (cur->_kv.first > key) {
cur = cur->_left;
} else {
return cur;
}
}
return nullptr ;
}
int Size () { return _Size(_root); }
int Height () { return _Height(_root); }
bool IsBalanceTree () { return _IsBalanceTree(_root); }
void InOrder () { _InOrder(_root); cout << endl; }
private :
int _Size(Node* root) {
if (root == nullptr ) return 0 ;
return _Size(root->_left) + _Size(root->_right) + 1 ;
}
int _Height(Node* root) {
if (root == nullptr ) return 0 ;
int lh = _Height(root->_left);
int rh = _Height(root->_right);
return lh > rh ? lh + 1 : rh + 1 ;
}
bool _IsBalanceTree(Node* root) {
if (nullptr == root) return true ;
int lh = _Height(root->_left);
int rh = _Height(root->_right);
if (rh - lh != root->_bf || abs (root->_bf) >= 2 ) {
cout << root->_kv.first << ":平衡因子异常" << endl;
return false ;
}
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
int _InOrder(Node* root) {
if (root == nullptr ) return 0 ;
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
private :
Node* _root = nullptr ;
};
Test.cpp: #define _CRT_SECURE_NO_WARNINGS 1
#include "AVLTree.h"
void TestAVLTree1 () {
AVLTree<int , int > t;
int a[] = { 4 , 2 , 6 , 1 , 3 , 5 , 15 , 7 , 16 , 14 };
for (auto e : a) {
if (e == 14 ) {
int i = 0 ;
}
t.Insert ({ e,e });
cout << e << "->" << t.IsBalanceTree () << endl;
}
cout << t.IsBalanceTree () << endl;
}
void TestAVLTree2 () {
const int N = 100000 ;
vector<int > v;
v.reserve (N);
srand (time (0 ));
for (size_t i = 0 ; i < N; i++) {
v.push_back (rand () + i);
}
size_t begin2 = clock ();
AVLTree<int , int > t;
for (auto e : v) {
t.Insert (make_pair (e, e));
}
size_t end2 = clock ();
cout << "Insert:" << end2 - begin2 << endl;
cout << t.IsBalanceTree () << endl;
cout << "Height:" << t.Height () << endl;
cout << "Size:" << t.Size () << endl;
size_t begin1 = clock ();
for (size_t i = 0 ; i < N; i++) {
t.Find ((rand () + i));
}
size_t end1 = clock ();
cout << "Find:" << end1 - begin1 << endl;
}
int main () {
TestAVLTree1 ();
return 0 ;
}
TestAVLTree1() 函数测试
TestAVLTree2() 函数测试
6 调试技巧 有些开发者喜欢通过对比代码的方式来解决 BUG,看看和别人写的哪里不一样?其实这是在走捷径!学习的意义:学知识,就是——锻炼学习能力、分析能力、解决问题能力。对比代码、问别人、求助于 AI……其实后面的两种能力都没有得到锻炼,这对于我们今后的工作是没有好处的。
调试的技巧有很多种,我们平常通过简单地调试实际上只能解决一小部分问题,很多问题仅凭调试是解决不了问题的。我们可以打印、可以打印日志(这个在公司里面很常用)——
7 关于 AVL 树和红黑树这部分知识的学习的说明 AVL 树、红黑树本质上不用特别熟悉,手撕链表什么的代表代表你的能力。
相关免费在线工具 加密/解密文本 使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
Gemini 图片去水印 基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,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