AVL 树是一种自平衡二叉查找树，通过平衡因子控制左右子树高度差不超过 1。本文介绍了 AVL 树的结构、平衡因子定义、旋转操作（左旋、右旋、左右双旋、右左双旋）及插入删除逻辑。提供了完整的 C++ 代码实现，包含节点结构、插入更新平衡因子、旋转修复不平衡以及平衡检测功能。时间复杂度为 O(log n)，适合频繁查询场景。
**AVL树（Adelson-Velsky and Landis Tree）是一种自平衡的二叉查找树（Binary Search Tree, BST），它的特点是每个节点的左子树和右子树的高度差（称为平衡因子）不能超过1。**AVL树是由俄罗斯数学家Adelson-Velsky和Landis于1962年提出的。
AVL树与普通的二叉搜索树一样，满足以下两个条件：
对于树中某个节点 ( N )，其平衡因子 ( BF(N) ) 定义为： BF(N) = 右子树高度 - 左子树高度
为了保持AVL树的平衡性，当插入或删除节点后，树可能会失去平衡。此时需要通过旋转操作来恢复平衡。常见的旋转操作有四种：
平衡性与时间复杂度
优点：
缺点：
AVL树的结构跟二叉搜索树几乎是类似的，我们需要添加一个 int 变量来记录平衡因子，且增加一个 parent 结点指针来辅助平衡因子的找寻和修改，在后续的旋转操作我们会认识到它的作用。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
template<class K, class V>
struct AVLTreeNode {
pair<K, V> _kv;
AVLTreeNode<K, V>* _parent;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
int _BF;
AVLTreeNode(const pair<K, V>& kv) : _kv(kv), _parent(nullptr), _left(nullptr), _right(nullptr), _BF(0){}
};
template<class K,class V>
class AVLTree {
using Node = AVLTreeNode<K, V>;
public:
//AVL树的构建和操作
bool Insert(const pair<K, V>& kv) {}
void RotateR(Node* parent) {}
void RotateL(Node* parent){}
void RotateLR(Node* parent) {}
void RotateRL(Node* parent) {}
Node Find(const K& key){}
private:
Node* _root = nullptr;
};
int main() {
return 0;
}
平衡因子 = 右子树高度 - 左子树高度 只有子树高度变化才会影响当前结点平衡因子。插入结点，会增加高度，所以新增结点在 parent 的右子树，parent 的平衡因子++，新增结点在 parent 的左子树，parent 平衡因子-- parent 所在子树的高度是否变化决定了是否会继续往上更新
图例展示
更新到 10 结点，发现平衡因子变为 2，破坏了 10 子树结构，需要进行旋转。
更新到中间结点，3 为根的子树高度不变，不会影响上一层，更新结束
最坏的情况一直更新到根结点
当一个新节点插入AVL树时，首先按照二叉查找树的方式插入节点。然后，通过遍历树的路径来检查是否有节点失衡，如果有，进行相应的旋转操作。
先找到插入结点的位置，在进行插入，然后检查更新平衡因子，这里我们在前面定义的_parent 的作用就逐渐体现出来了。
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 (kv.first < parent->_kv.first) {
parent->_left = cur;
} else
parent->_right = 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
return false;
}
}
保持搜索树的规则，让旋转的树从不满足变平衡，其次降低旋转树的高度
旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。
说明：下面的图中，有些结点给的是具体值，方便观察。
图例文字描述
图展示的是 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 为根的树左边太高了，需要往右边旋转，控制两棵树的平衡。旋转核心步骤，因为 5 < b 子树的值 < 10，将 b 变成 10 的左子树，10 变成 5 的右子树，5 变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的高度恢复到了插入之前的 h+2，符合旋转原则。如果插入之前 10 是整棵树的一个局部子树，旋转后不会再影响上一层，插入结束了。
右单旋的详细描述
右单旋代码
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;
// parent 有可能是整棵树的根，也可能是局部的⼦树
// 如果是整棵树的根，要修改_root
// 如果是局部的指针要跟上⼀层链接
if (parentParent == nullptr) {
_root = subL;
subL->_parent = nullptr;
}
else {
if (parent == parentParent->_left) {
parentParent->_left = subL;
}
else {
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
parent->_BF = subL->_BF = 0;
}
图例文字描述
展示的是 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 整棵树的一个局部子树，旋转后不会再影响上一层，插入结束了。
左单旋代码
void RotateL(Node* parent) {
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
Node* parent_Parent = parent->_parent;
parent->_parent = subR;
if (parent_Parent == nullptr) {
_root = subR;
subR->_parent = nullptr;
}
else {
if (parent == parent_Parent->_left)
parent_Parent->_left = subR;
else
parent_Parent->_right = subR;
subR->_parent = parent_Parent;
}
parent->_BF = subR->_BF = 0;
}
图形文字描述
通过下面的图可以看到，左边高时，如果插入位置不是在 a 子树，而是插入在 b 子树，b 子树高度从 h 变 成 h+1，引发旋转，右单旋无法解决问题，右单旋后，我们的树依旧不平衡。右单旋解决的纯粹的左边高，但是插入在 b 子树中，10 为跟的子树不再是单纯的左边高，对于 10 是左边高，但是对于 5 是右边高，需要用两次旋转才能解决，以 5 为旋转点进行一个左单旋，以 10 为旋转点进行一个右单旋，这棵树这棵树就平衡了。
只进行了右旋的错误示范图
下面我们将 a/b/c 子树抽象为高度 h 的 AVL 子树进行分析，另外我们需要把 b 子树的细节进⼀步展开为 8 和左子树高度为 h-1 的 e 和 f 子树，因为我们要对 b 的父亲 5 为旋转点进行左单旋，左单旋需要动 b 树中的左子树。b 子树中新增结点的位置 不同，平衡因子更新的细节也不同，通过观察 8 的平衡因子不同，这里我们要分三个场景讨论。
场景 1：h >= 1 时，新增结点插入在 e 子树，e 子树高度从 h-1 并为 h 并不断更新 8->5->10 平衡因子， 引发旋转，其中 8 的平衡因子为 -1，旋转后 8 和 5 平衡因子为 0，10 平衡因子为 1。
场景 2：h >= 1 时，新增结点插入在 f 子树，f 子树高度从 h-1 变为 h 并不断更新 8->5->10 平衡因子，引发旋转，其中 8 的平衡因子为 1，旋转后 8 和 10 平衡因子为 0，5 平衡因子为 -1。
场景 3：h == 0 时，a/b/c 都是空树，b 自己就是一个新增结点，不断更新 5->10 平衡因子，引发旋转，其中 8 的平衡因子为 0，旋转后 8 和 10 和 5 平衡因子均为 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) {
subLR->_BF = 0;
parent->_BF = 0;
subL->_BF = 0;
}
else if (bf == 1) {
subLR->_BF = 0;
parent->_BF = 0;
subL->_BF = -1;
}
else if (bf == -1) {
subLR->_BF = 0;
parent->_BF = 1;
subL->_BF = 0;
}
else {
assert(false);
}
}
重点是平衡因子的更新
跟左右双旋类似，下面将 a/b/c 子树抽象为高度 h 的 AVL 子树进行分析，另外我们需要把 b 子树的细节进一步展开为 12 和左子树高度为 h-1 的 e 和 f 子树，因为我们要对 b 的父亲 15 为旋转点进行右单旋，右单旋需要动 b 树中的右子树。b 子树中新增结点的位置不同，平衡因子更新的细节也不同，通过观察 12 的平衡因子不同，这里同样要分三个场景讨论。
场景 1：h >= 1 时，新增结点插入在 e 子树，e 子树高度从 h-1 变为 h 并不断更新 12->15->10 平衡因子，引发旋转，其中 12 的平衡因子为 -1，旋转后 10 和 12 平衡因子为 0，15 平衡因子为 1。
场景 2：h >= 1 时，新增结点插入在 f 子树，f 子树高度从 h-1 变为 h 并不断更新 12->15->10 平衡因子， 引发旋转，其中 12 的平衡因子为 1，旋转后 15 和 12 平衡因子为 0，10 平衡因子为 -1。
场景 3：h == 0 时，a/b/c 都是空树，b 自己就是一个新增结点，不断更新 15->10 平衡因子，引发旋转，其中 12 的平衡因子为 0，旋转后 10 和 12 和 15 平衡因子均为 0。
代码展示
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);
}
}
仿照二叉搜索树的逻辑进行查找，效率 O(log n)
Node* Find(const K& key) {
Node* cur = _root;
while (cur) {
if (cur->_kv.first > key)
cur = cur->_left;
else if (cur->_kv.first < key)
cur = cur->_right;
else
return cur;
}
return nullptr;
}
实现的 AVL 树是否合格，我们通过检查左右子树高度差的程序进行反向验证，同时检查一下结点的平衡因子更新是否出现了问题。
bool _IsBalanceTree(Node* root) {
// 空树也是 AVL 树
if (nullptr == root)
return true;
// 计算 pRoot 结点的平衡因子：即 pRoot 左右子树的高度差
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
int diff = rightHeight - leftHeight;
// 如果计算出的平衡因子与 pRoot 的平衡因子不相等，或者
// pRoot 平衡因子的绝对值超过 1，则一定不是 AVL 树
if (abs(diff) >= 2) {
cout << root->_kv.first << "高度差异常" << endl;
return false;
}
if (root->_BF != diff) {
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
// pRoot 的左和右如果都是 AVL 树，则该树一定是 AVL 树
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
我们仿照前面二叉树的学习将高度和大小，中序遍历求解也写下
void _InOrder(Node* root) {
if (root == nullptr) {
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
int _Height(Node* root) {
if (root == nullptr) {
return 0;
}
int Left_height = _Height(root->_left);
int Right_height = _Height(root->_right);
return Left_height > Right_height ? Left_height + 1 : Right_height + 1;
}
int _Size(Node* root) {
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
我们同样按照二叉搜索树一样是将这些函数封装在 private 中，在 public 中在定义函数调用这些函数，不然在外面传根节点有点麻烦。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <assert.h>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
template<class K, class V>
struct AVLTreeNode {
pair<K, V> _kv;
AVLTreeNode<K, V>* _parent;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
int _BF;
AVLTreeNode(const pair<K, V>& kv) : _kv(kv), _parent(nullptr), _left(nullptr), _right(nullptr), _BF(0){}
};
template<class K,class V>
class AVLTree {
using Node = AVLTreeNode<K, V>;
public:
//AVL树的构建和操作
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 (kv.first < parent->_kv.first) {
parent->_left = cur;
}
else
parent->_right = 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)
RotateL(parent);
else if (parent->_BF == -2 && cur->_BF == -1)
RotateR(parent);
else if (parent->_BF == 2 && cur->_BF == -1)
RotateRL(parent);
else if (parent->_BF == -2 && cur->_BF == 1)
RotateLR(parent);
else
assert(false);
break;
}
else
return false;
}
return true;
}
void RotateR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parent_Parent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
//parent 可能是整棵树的根，也可能是局部根
//局部根要向上链接，更新祖父的结点信息
if (parent_Parent == nullptr) {
_root = subL;
subL->_parent = nullptr;
}
else {
if (parent_Parent->_left == parent)
parent_Parent->_left = subL;
else
parent_Parent->_right = subL;
subL->_parent = parent_Parent;
}
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;
subR->_left = parent;
Node* parent_Parent = parent->_parent;
parent->_parent = subR;
// 更新 parent_Parent 的子节点指针
if (parent_Parent == nullptr) {
_root = subR;
subR->_parent = nullptr;
}
else {
if (parent == parent_Parent->_left)
parent_Parent->_left = subR;
else
parent_Parent->_right = subR;
subR->_parent = parent_Parent;
}
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) {
subLR->_BF = 0;
parent->_BF = 0;
subL->_BF = 0;
}
else if (bf == 1) {
subLR->_BF = 0;
parent->_BF = 0;
subL->_BF = -1;
}
else if (bf == -1) {
subLR->_BF = 0;
parent->_BF = 1;
subL->_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->_left;
else if (cur->_kv.first < key)
cur = cur->_right;
else
return cur;
}
return nullptr;
}
void InOrder() {
_InOrder(_root);
cout << endl;
}
int Height() {
return _Height(_root);
}
int Size() {
return _Size(_root);
}
bool IsBalanceTree() {
return _IsBalanceTree(_root);
}
private:
void _InOrder(Node* root) {
if (root == nullptr) {
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
int _Height(Node* root) {
if (root == nullptr) {
return 0;
}
int Left_height = _Height(root->_left);
int Right_height = _Height(root->_right);
return Left_height > Right_height ? Left_height + 1 : Right_height + 1;
}
int _Size(Node* root) {
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
bool _IsBalanceTree(Node* root) {
// 空树也是 AVL 树
if (nullptr == root)
return true;
// 计算 pRoot 结点的平衡因子：即 pRoot 左右子树的高度差
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
int diff = rightHeight - leftHeight;
// 如果计算出的平衡因子与 pRoot 的平衡因子不相等，或者
// pRoot 平衡因子的绝对值超过 1，则一定不是 AVL 树
if (abs(diff) >= 2) {
cout << root->_kv.first << "高度差异常" << endl;
return false;
}
if (root->_BF != diff) {
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
// pRoot 的左和右如果都是 AVL 树，则该树一定是 AVL 树
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
private:
Node* _root = nullptr;
};
void TestAVLTree1() {
AVLTree<int, int> t;
// 常规的测试用例
int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
// 特殊的带有双旋场景的测试用例
//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a) {
t.Insert({ e, e });
}
t.InOrder();
cout << t.IsBalanceTree() << endl;
}
void test2() {
AVLTree<int, int> tree;
const int N = 100000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (int i = 0; i < N; i++) {
v.push_back(rand() + i);
}
for (auto e : v) {
tree.Insert({ e, e });
}
size_t end2 = clock();
cout << tree.IsBalanceTree() << endl;
cout << "Height:" << tree.Height() << endl;
cout << "Size:" << tree.Size() << endl;
size_t begin1 = clock();
// 确定在的值
for (auto e : v) {
tree.Find(e);
}
// 随机值
/*for (size_t i = 0; i < N; i++) {
t.Find((rand() + i));
}*/
}
int main() {
//test2();
TestAVLTree1();
return 0;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online