目录
一、AVL树的概念
1. 二叉搜索树的局限性
二叉搜索树（BST）在理想情况下具有O(log₂N)的查询效率，但当插入数据有序或接近有序时，树会退化为链表结构，查询效率骤降至O(N)。为了解决这一问题，AVL树应运而生。
2. AVL树的定义
AVL树是由俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明的一种自平衡二叉搜索树：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树。
- 左右子树高度之差（简称平衡因子）的绝对值不超过1，即平衡因子只能是-1、0或1。
- 通过旋转操作维护平衡，保证树高始终为O(log₂N)。
二、AVL树节点结构
在实现 AVL 树时，我们采用 KV 模型的 AVL 树节点定义，采用三叉链结构为每个节点配备左孩子、右孩子以及父节点指针。此外，每个节点引入平衡因子，以便高效地维护树的平衡性。在构造新节点时，由于其左右子树均为空树，所以初始平衡因子设置为 0，这样可以准确反映节点的初始状态。
需要注意的是，给每个节点增加平衡因子虽然不是必须的，但这是一种非常便捷的实现方式。如果不引入平衡因子，虽然也可以实现 AVL 树，但实现过程会复杂得多，需要通过递归计算每个节点的左右子树高度来判断是否平衡。而引入平衡因子后，我们可以在节点插入和删除操作时直接更新和利用平衡因子，从而高效地维护树的平衡性，确保 AVL 树的性能优势得以充分发挥。
template<class K, class V>
struct AVLTreeNode
{
// 三叉链结构
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
// 存储键值对
pair<K, V> _kv;
// 平衡因子（右子树高度 - 左子树高度）
int _bf;
// 构造函数
AVLTreeNode(const pair<K, V>& kv)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};平衡因子计算：_bf = rightHeight - leftHeight
三、AVL树的插入操作
1. 插入流程
AVL树插入结点的操作分为如下三个步骤：
找到待插入位置：按照二叉搜索树的规则，若待插入结点的key值比当前结点小，则插入到左子树；若大于，则插入到右子树；若相等，则插入失败。
将结点插入树中：找到合适的位置后，将新结点插入到树中。
更新平衡因子并旋转调整：插入新结点后，从新结点的父结点开始，向上更新平衡因子。若父结点的平衡因子变为-1或1，则需继续向上更新；若变为0，则停止更新；若变为-2或2，则需进行旋转操作以恢复平衡。
更新平衡因子：新增结点在parent的右边，parent的平衡因子加1；新增结点在parent的左边，parent的平衡因子减1。
旋转操作：当parent的平衡因子为-2且cur的平衡因子为-1时，进行右单旋；当parent的平衡因子为-2且cur的平衡因子为1时，进行左右双旋；当parent的平衡因子为2且cur的平衡因子为-1时，进行右左双旋；当parent的平衡因子为2且cur的平衡因子为1时，进行左单旋。
注意，当parent的平衡因子为-2或2时，cur的平衡因子必定是-1或1而不会是0，因为若cur的平衡因子是0，那么cur一定是新增结点，而新增结点最终会插入到一个空树中。在新增结点插入前，其父结点的平衡因子要么是0（左右子树均为空），新增结点插入后其平衡因子变为-1或1；要么是-1或1（左右子树其一不为空），新增结点插入到其父结点的空子树中，插入后其父结点的平衡因子变为0。
旋转操作后，树的高度变为插入之前的高度，因此不会影响其父结点的平衡因子，所以无需继续往上更新平衡因子。
2. 代码实现片段
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr) // 若AVL树为空树，则插入结点直接作为根结点
{
_root = new Node(kv);
return true;
}
// 1、按照二叉搜索树的插入方法，找到待插入位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kv.first < cur->_kv.first) // 待插入结点的key值小于当前结点的key值
{
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first) // 待插入结点的key值大于当前结点的key值
{
parent = cur;
cur = cur->_right;
}
else // 待插入结点的key值等于当前结点的key值
{
return false; // 插入失败（不允许key值冗余）
}
}
// 2、将待插入结点插入到树中
cur = new Node(kv); // 根据所给值构造一个新结点
if (kv.first < parent->_kv.first) // 新结点的key值小于parent的key值
{
parent->_left = cur;
cur->_parent = parent;
}
else // 新结点的key值大于parent的key值
{
parent->_right = cur;
cur->_parent = parent;
}
// 3、更新平衡因子，如果出现不平衡，则需要进行旋转
while (cur != _root) // 最坏一路更新到根结点
{
if (cur == parent->_left) // parent的左子树增高
{
parent->_bf--;
}
else if (cur == parent->_right) // parent的右子树增高
{
parent->_bf++;
}
// 判断是否更新结束或需要进行旋转
if (parent->_bf == 0) // 更新结束（新增结点把parent左右子树矮的那一边增高了，此时左右高度一致）
{
break; // parent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子
}
else if (parent->_bf == -1 || parent->_bf == 1) // 需要继续往上更新平衡因子
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == -2 || parent->_bf == 2) // 需要进行旋转（此时parent树已经不平衡了）
{
if (parent->_bf == -2)
{
if (cur->_bf == -1)
{
RotateR(parent); // 右单旋
}
else // cur->_bf == 1
{
RotateLR(parent); // 左右双旋
}
}
else // parent->_bf == 2
{
if (cur->_bf == -1)
{
RotateRL(parent); // 右左双旋
}
else // cur->_bf == 1
{
RotateL(parent); // 左单旋
}
}
break; // 旋转后就一定平衡了，无需继续往上更新平衡因子（旋转后树高度变为插入之前了）
}
else
{
assert(false); // 在插入前树的平衡因子就有问题
}
}
return true; // 插入成功
}四、AVL树的旋转调整
1. 左单旋（RR型）
🌴左单旋触发条件
当新节点插入到父节点的右子树的右侧，导致父节点的平衡因子变为2时，需要进行左单旋。
🌴旋转示意图
🌴左单旋步骤
记录相关节点 ：将父节点的右子节点设为subR，subR的左子节点设为subRL，父节点的父节点设为parentParent。
建立subR和parent之间的关系 ：将parent的父节点指向subR，subR的左子节点指向parent。
建立parent和subRL之间的关系 ：将parent的右子节点指向subRL，若subRL存在，则subRL的父节点指向parent。
建立parentParent和subR之间的关系 ：若parentParent为空，说明父节点是根节点，此时将subR设为新的根节点，并将subR的父节点设为nullptr；否则，根据父节点是其父节点的左孩子还是右孩子，将subR设为对应的孩子，并更新subR的父节点为parentParent。
更新平衡因子 ：将subR和parent的平衡因子都设为0。
🌴代码示例
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;
//1、建立subR和parent之间的关系
parent->_parent = subR;
subR->_left = parent;
//2、建立parent和subRL之间的关系
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
//3、建立parentParent和subR之间的关系
if (parentParent == nullptr)
{
_root = subR;
subR->_parent = nullptr; //subR的_parent指向需改变
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subR;
}
else //parent == parentParent->_right
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
//4、更新平衡因子
subR->_bf = parent->_bf = 0;
}2. 右单旋（LL型）
🌵右单旋触发条件
当新节点插入到父节点的左子树的左侧，导致父节点的平衡因子变为-2时，需要进行右单旋。
🌵旋转示意图
🌵右单旋步骤
记录相关节点 ：记录父节点的左子节点为subL，subL的右子节点为subLR，父节点的父节点为parentParent。
调整子节点关系 ：将父节点的左子节点指针指向subLR，若subLR不为空，则将subLR的父节点指针指向父节点。
调整父节点与subL的关系 ：将subL的右子节点指针指向父节点，父节点的父节点指针指向subL。
调整父节点的父节点与subL的关系 ：若父节点原本是根节点，则将树的根节点指针指向subL，并将subL的父节点指针设为nullptr；否则，根据父节点是其父节点的左孩子还是右孩子，将subL设为对应的孩子，并更新subL的父节点为parentParent。
更新平衡因子 ：将父节点和subL的平衡因子都设为0。
🌵代码示例
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;
//1、建立subL和parent之间的关系
subL->_right = parent;
parent->_parent = subL;
//2、建立parent和subLR之间的关系
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
//3、建立parentParent和subL之间的关系
if (parentParent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
//4、更新平衡因子
subL->_bf = parent->_bf = 0;
}3. 左右双旋（LR型）
🍒左右双旋触发条件
当新节点插入较高左子树的右侧---左右：先左单旋再右单旋
🍒旋转步骤
左单旋：以父节点的左子节点为旋转点进行左单旋。
右单旋：以父节点为旋转点进行右单旋。
更新平衡因子：根据旋转点节点的原始平衡因子，更新相关节点的平衡因子。
🍒旋转示意图
🍒平衡因子更新
左右双旋后，平衡因子的更新取决于旋转点节点（subLR）的原始平衡因子：
当subLR原始平衡因子是-1时：
parent的平衡因子更新为1。
subL的平衡因子更新为0。
subLR的平衡因子更新为0。
当subLR原始平衡因子是1时：
parent的平衡因子更新为0。
subL的平衡因子更新为-1。
subLR的平衡因子更新为0。
当subLR原始平衡因子是0时：
parent、subL和subLR的平衡因子都更新为0。
🍒代码实现
//左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf; //subLR不可能为nullptr，因为subL的平衡因子是1
//1、以subL为旋转点进行左单旋
RotateL(subL);
//2、以parent为旋转点进行右单旋
RotateR(parent);
//3、更新平衡因子
if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false); //在旋转前树的平衡因子就有问题
}
}4. 右左双旋（RL型）
🌻右左双旋触发条件
当新节点插入较高右子树的左侧---右左：先右单旋再左单旋
🌻旋转步骤
右左双旋的操作分为以下步骤：
右单旋：以父节点的右子节点为旋转点进行右单旋。
左单旋：以父节点为旋转点进行左单旋。
更新平衡因子：根据旋转点节点（subRL）的原始平衡因子更新相关节点的平衡因子。
🌻旋转示意图
🌻平衡因子更新
右左双旋后，平衡因子的更新取决于旋转点节点（subRL）的原始平衡因子：
当subRL原始平衡因子是1时：
parent的平衡因子更新为-1。
subR的平衡因子更新为0。
subRL的平衡因子更新为0。
当subRL原始平衡因子是-1时：
parent的平衡因子更新为0。
subR的平衡因子更新为1。
subRL的平衡因子更新为0。
当subRL原始平衡因子是0时：
parent、subR和subRL的平衡因子都更新为0。
🌻代码实现
//右左双旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
//1、以subR为旋转点进行右单旋
RotateR(subR);
//2、以parent为旋转点进行左单旋
RotateL(parent);
//3、更新平衡因子
if (bf == 1)
{
subRL->_bf = 0;
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == -1)
{
subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 1;
}
else if (bf == 0)
{
subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 0;
}
else
{
assert(false); //在旋转前树的平衡因子就有问题
}
}五、AVL树的性能
1. 时间复杂度
AVL树的插入、查找和删除操作的时间复杂度均为O(log N)，其中N表示树中节点的数量。这是由于AVL树通过旋转操作保持了树的平衡性，使得树的高度始终保持在对数级别。相比于普通二叉搜索树在最坏情况下退化为链表（时间复杂度为O(N)），AVL树的性能更加稳定可靠。
2. 空间复杂度
AVL树每个节点需要存储左子树指针、右子树指针、父节点指针以及平衡因子，因此其空间复杂度为O(N)，需要额外的存储空间来维护这些信息。
3. 性能优势
高效的数据检索 ：AVL树的平衡性保证了树的高度较小，使得查找操作非常高效，适用于需要频繁进行数据查询的场景，如数据库中的索引结构。
动态数据管理 ：在需要动态插入和删除数据的场景中，AVL树能够保持高效的插入和删除操作，同时保证数据的有序性。
避免最坏情况 ：相比于普通二叉搜索树，AVL树通过平衡因子和旋转操作，避免了树的退化，确保了操作的最坏时间复杂度为O(log N)。
4. 性能不足
旋转操作开销 ：插入和删除操作可能导致树的不平衡，需要进行旋转调整，这会增加一定的操作开销。在某些对实时性要求极高的场景中，可能会影响性能。
空间浪费 ：为了维护平衡因子和指针信息，AVL树需要额外的存储空间，相比一些简单的数据结构（如数组、链表）来说，存在一定的空间浪费。
5. 与红黑树的对比
| 特性 | AVL树 | 红黑树 |
|---|---|---|
| 平衡性 | 严格平衡（高度差 ≤1） | 弱平衡（最长路径 ≤ 2倍最短路径） |
| 查询效率 | 更高（树高更低） | 稍低 |
| 插入/删除 | 调整频率高，适合低频写操作场景 | 调整频率低，适合高频写操作场景 |
| 典型应用 | 数据库索引、字典库 | C++ STL map、Linux 内核调度 |
性能权衡：
AVL树：适合读密集型场景（如搜索引擎索引、频繁查询的数据库）
红黑树：适合写密集型场景（如实时系统、频繁更新的数据结构）
六、AVL树的验证
#include <iostream> #include <vector> #include <cstdlib> #include <ctime> using namespace std; // 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) {} }; // AVL树类定义 template<class K, class V> class AVLTree { public: // 构造函数 AVLTree() : _root(nullptr) {} // 析构函数，销毁树中所有节点 ~AVLTree() { Destroy(_root); } // 插入操作 bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { // 如果树为空，直接创建根节点 _root = new AVLTreeNode<K, V>(kv); return true; } AVLTreeNode<K, V>* cur = _root; AVLTreeNode<K, V>* 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 AVLTreeNode<K, V>(kv); if (kv.first < parent->_kv.first) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; // 更新平衡因子并处理可能的旋转 while (cur != _root) { if (cur == parent->_left) { parent->_bf++; } else { parent->_bf--; } if (parent->_bf == 0) { // 平衡因子为0，无需进一步更新 break; } else if (parent->_bf == 1 || parent->_bf == -1) { // 平衡因子为1或-1，继续向上更新 cur = parent; parent = cur->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { // 平衡因子为2或-2，需要进行旋转 if (parent->_bf == 2) { if (cur->_bf == 1) { RotateR(parent); // 右单旋 } else { RotateLR(parent); // 左右双旋 } } else { if (cur->_bf == -1) { RotateL(parent); // 左单旋 } else { RotateRL(parent); // 右左双旋 } } break; } } return true; } // 查找操作 AVLTreeNode<K, V>* Find(const K& key) { AVLTreeNode<K, V>* 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; } // 验证AVL树是否平衡 bool IsBalanceTree() { return _IsBalanceTree(_root); } private: AVLTreeNode<K, V>* _root; // 根节点指针 // 递归销毁树节点 void Destroy(AVLTreeNode<K, V>* node) { if (node) { Destroy(node->_left); Destroy(node->_right); delete node; } } // 计算节点高度 int _Height(AVLTreeNode<K, V>* node) { if (node == nullptr) return 0; return max(_Height(node->_left), _Height(node->_right)) + 1; } // 递归验证树是否平衡 bool _IsBalanceTree(AVLTreeNode<K, V>* root) { if (root == nullptr) return true; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); int diff = rightHeight - leftHeight; // 检查平衡因子是否正确且是否满足 AVL 树平衡条件 if (diff != root->_bf || abs(diff) > 1) { return false; } return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right); } // 右单旋操作 void RotateR(AVLTreeNode<K, V>* parent) { AVLTreeNode<K, V>* subL = parent->_left; AVLTreeNode<K, V>* subLR = subL->_right; AVLTreeNode<K, V>* parentParent = parent->_parent; // 更新节点关系 subL->_right = parent; parent->_parent = subL; parent->_left = subLR; if (subLR) { subLR->_parent = parent; } // 更新根节点或父节点的子节点关系 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; } // 左单旋操作 void RotateL(AVLTreeNode<K, V>* parent) { AVLTreeNode<K, V>* subR = parent->_right; AVLTreeNode<K, V>* subRL = subR->_left; AVLTreeNode<K, V>* parentParent = parent->_parent; // 更新节点关系 subR->_left = parent; parent->_parent = subR; parent->_right = subRL; if (subRL) { subRL->_parent = parent; } // 更新根节点或父节点的子节点关系 if (parentParent == nullptr) { _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(AVLTreeNode<K, V>* parent) { RotateL(parent->_left); RotateR(parent); } // 右左双旋操作 void RotateRL(AVLTreeNode<K, V>* parent) { RotateR(parent->_right); RotateL(parent); } }; // 测试函数 void TestAVLTree() { AVLTree<int, int> t; // 手动插入特定数据验证平衡性 vector<int> keys = { 5, 3, 7, 2, 4, 6, 8 }; for (auto key : keys) { t.Insert(make_pair(key, key)); } cout << "Manual Insert Is Balance Tree: " << t.IsBalanceTree() << endl; // 测试随机数据插入和查找性能 const int N = 1000000; vector<int> v; v.reserve(N); srand((unsigned int)time(0)); for (int i = 0; i < N; i++) { v.push_back(rand() % N); } size_t beginInsert = clock(); for (auto e : v) { t.Insert(make_pair(e, e)); } size_t endInsert = clock(); cout << "Random Insert Time: " << (endInsert - beginInsert) << "ms" << endl; size_t beginFind = clock(); for (auto e : v) { t.Find(e); } size_t endFind = clock(); cout << "Random Find Time: " << (endFind - beginFind) << "ms" << endl; cout << "Final Is Balance Tree: " << t.IsBalanceTree() << endl; } int main() { TestAVLTree(); return 0; }
输出结果解释：
Manual Insert Is Balance Tree: 1
- 这表示在手动插入特定键值对（5, 3, 7, 2, 4, 6, 8）后，AVL 树仍然保持平衡。AVL 树通过旋转操作确保每个节点的左右子树高度差的绝对值不超过 1。在这个测试中，插入的键值对会触发 AVL 树的旋转机制，验证了旋转逻辑的正确性。
Random Insert Time: 276ms
- 这表示插入 100 万个随机整数到 AVL 树中所花费的时间约为 276毫秒。这个时间展示了 AVL 树在处理大量数据插入操作时的性能表现。由于 AVL 树的自平衡特性，插入操作的时间复杂度为 O(log N)，因此即使数据量很大，插入时间也相对较短。
Random Find Time: 164ms
- 这表示对 AVL 树中的 100 万个随机整数进行查找操作所花费的时间约为 164毫秒。这个时间反映了 AVL 树在查找操作中的高效性。由于 AVL 树保持了树的高度平衡，查找操作的时间复杂度为 O(log N)，因此查找速度非常快。
Final Is Balance Tree: 1
- 这表示在插入和查找所有随机数据后，AVL 树仍然保持平衡。这验证了 AVL 树在动态数据操作（插入和查找）后的自平衡能力。无论数据是如何插入的，AVL 树都能通过旋转操作维持其平衡性，确保后续操作的高效性。