一、前言：
AVL树，又称为平衡二叉树，它基于二叉搜索树并通过平衡而得到。
在前面的学习中我们提到，二叉搜索树可以提高搜索数据的效率，但在数据有序的情况下会退化为单支树，此时在树中查找元素就得遍历一整个分支，时间复杂度也会退化至O(N)。
如果有一种算法，可以使二叉搜索树时刻保持左右子树的平衡，就可以避免这种最坏情况。
二、AVL树的性质
当我们向二叉搜索树中插入新节点时，如果能用某种方法时刻保证树中每个节点的左右子树高度之差不超过1，就可以降低整棵树的高度，保证每条分支的平衡
AVL树的性质如下：
- AVL树可以是空树
- 一颗AVL树的左右子树都是AVL树
- 一颗AVL树的左右子树高度差不超过1
三、AVL树节点的定义
AVL树的左右子树高度差不能超过1，但是如何便捷的去检测该性质是否被打破呢？
我们可以在节点中定义一个平衡因子，如果左子树比右子树高一层，那么平衡因子就为-1；如果左右子树一样高，平衡因子就为0；如果右子树比左子树高一层，那么平衡因子就为1，这三种情况下AVL树的性质都没有被打破。
按照这个规则，如果平衡因子为-2、2或其他值，则说明左右子树已经失衡，性质被打破。
在调整失衡的AVL树时，我们需要频繁的访问父节点，所以在AVL树中我们需要使用三叉链，因此AVL树的节点除了包含左右子节点的指针，还需要一个指向父节点的指针
另外需要说明一下，本文中，我们使用key/value模型的AVL树
AVL树节点的定义如下：
这里简单介绍一下pair
pair可以将两个数据组成一组元素，因此对于key/value模型这种需要用到两个数据为一组的元素时就可以使用，内部的成员变量为first和second，其主要使用方法为：
pair<T1, T2> p1(v1, v2); //输入两个数据创建pair类型变量 make_pair(v1, v2); //输入两个数据通过函数创建pair类型变量 p1.first //访问p1的第一个数据 p1.second //访问p1的第二个数据四、AVL树的插入及更新平衡因子
向AVL树中插入节点与向二叉搜索树中插入节点的过程基本相同，唯一的区别就是AVL树在插入节点后可能存在失衡的情况，需要调整。我们先按照二叉搜索树的规则将节点插入到AVL树中，并判断插入的节点在父节点的左边还是右边.按照平衡因子的规则，如果新节点插入到了父节点的左侧，那么父节点的平衡因子-1
如果新节点插入到了父节点的右侧，那么父节点的平衡因子+1
以上，便是新增节点的父节点平衡因子可能的变化情况。
但是！插入一个节点不但会影响父节点，还可能会影响到祖先节点。
我们观察上面的四种可能，其中左边的两种情况下，插入节点后以父节点为根的子树高度发生了变化；在右边的两种情况下，插入节点后以父节点为根的子树高度没有发生变化。
观察过后可以发现，当父节点的平衡因子从0变为1/-1后，子树高度发生变化；当父节点的平衡因子从1/-1变为0后，子树高度不发生变化
如果以父节点为根的子树高度没有发生变化，那么就不会影响到祖先节点的平衡因子；如果高度变了就会继续向上影响到祖先节点的平衡因子
因此，我们可以通过判断节点的插入位置来计算父节点的平衡因子，进而判断子树高度是否发生变化，再进一步计算对祖先节点平衡因子的影响，来判断AVL树是否失衡。
至此，我们已经可以开始写插入新节点和更新平衡因子的代码了：
// AVL树的结构定义 template<class K, class V> class AVLtree { typedef AVLnode<K, V> Node; // 定义节点类型别名 public: // 插入函数：向AVL树中插入一个键值对 bool insert(const pair<K, V>& kv) { // 情况1：空树，直接创建根节点 if (_root == nullptr) { _root = new Node(kv); // 创建新节点作为根节点 return true; // 插入成功 } // 初始化指针：parent用于记录当前节点的父节点，cur用于遍历树 Node* parent = nullptr; Node* cur = _root; // 步骤1：按照二叉搜索树的规则找到插入位置 while (cur) { if (cur->_kv.first < kv.first) // 当前节点的key小于插入key，向右子树查找 { parent = cur; // 更新父节点 cur = cur->_right; // 移动到右子树 } else if (cur->_kv.first > kv.first) // 当前节点的key大于插入key，向左子树查找 { parent = cur; // 更新父节点 cur = cur->_left; // 移动到左子树 } else // 找到相同key，插入失败（不允许重复key） { return false; } } // 步骤2：创建新节点并插入到正确位置 // 此时cur为nullptr，parent是待插入位置的父节点 cur = new Node(kv); // 创建新节点 // 判断新节点应该插入到父节点的左侧还是右侧 if (parent->_kv.first < cur->_kv.first) // 父节点的key小于新节点的key parent->_right = cur; // 插入到右子树 else parent->_left = cur; // 插入到左子树 // 设置新节点的父指针 cur->_parent = parent; // 步骤3：更新平衡因子并检查是否需要旋转 // 从插入点的父节点开始向上更新平衡因子，直到根节点或平衡因子变为0 while (parent) { // 根据新节点插入的位置更新父节点的平衡因子 if (parent->_left == cur) // 新节点插入在父节点的左侧 parent->ph--; // 左子树高度增加，平衡因子减1 else // 新节点插入在父节点的右侧 parent->ph++; // 右子树高度增加，平衡因子加1 // 检查更新后的平衡因子 if (parent->ph == 0) // 平衡因子变为0，说明以parent为根的子树高度不变 { // 子树高度没有变化，不会影响更上层的平衡因子，更新结束 break; } else if (parent->ph == 1 || parent->ph == -1) // 平衡因子为1或-1，子树高度发生变化 { // 子树高度变化，需要继续向上更新祖先节点的平衡因子 cur = parent; // 当前节点上移 parent = parent->_parent; // 父节点上移 } // 当平衡因子是-2或2时，说明以parent为根的子树已经失衡，需要进行旋转调整 else if (parent->ph == 2 || parent->ph == -2) { // 根据cur和parent的平衡因子判断失衡类型，选择相应的旋转方式 // 情况1：右单旋 - 新节点插入在较高左子树的左侧 if (cur->ph == -1 && parent->ph == -2) rotateR(parent); // 调用右单旋函数 // 情况2：左单旋 - 新节点插入在较高右子树的右侧 else if (cur->ph == 1 && parent->ph == 2) rotateL(parent); // 调用左单旋函数 // 情况3：左右双旋 - 新节点插入在较高左子树的右侧 else if (cur->ph == 1 && parent->ph == -2) rotateLR(parent); // 调用左右双旋函数 // 情况4：右左双旋 - 新节点插入在较高右子树的左侧 else if (cur->ph == -1 && parent->ph == 2) rotateRL(parent); // 调用右左双旋函数 else assert(false); // 不应该出现其他情况，如果出现则程序终止 // 旋转完成后，以parent为根的子树已经重新平衡，更新结束 break; } else { // 平衡因子出现异常值（既不是0、±1、±2），程序终止 assert(false); } } return true; // 插入成功 } Node* _root = nullptr; // AVL树的根节点指针 };五、AVL树的平衡调整（附动图）
如果在一颗原本平衡的AVL树中插入一个新节点，可能会造成失衡，此时需要调整树的结构使之重新平衡，这种调整方法称为旋转。
根据树的原本结构和节点插入位置的不同分为四种情况和四种旋转方式：
（1）新节点插入较高左子树的左侧：右单旋
问题来了：如何判断插入的新节点的方位呢？
很简单，以上面的情况为例，插入新节点后60的平衡因子变成-2，说明左子树更高，而30的平衡因子变成-1，说明新节点插入到了30的左子树。后面左单旋以及双旋中都同理，我们使用平衡因子就可以判断新节点插入的位置
右单旋代码如下：
//右旋 void rotateR(Node* parent) { // 1. 保存相关节点指针 Node* subL = parent->_left; // parent的左子树（较高左子树） Node* subLR = subL->_right; // subL的右子树 Node* Pparent = parent->_parent; // parent的父节点（用于连接旋转后的新子树） // 2. 处理subLR的重新连接 parent->_left = subLR; // 将subLR作为parent的新左孩子 if (subLR) // 如果subLR存在，更新其父指针 { subLR->_parent = parent; } // 3. 旋转核心：subL成为新的根，parent成为subL的右子树 subL->_right = parent; // parent成为subL的右孩子 parent->_parent = subL; // 更新parent的父指针指向subL // 4. 处理旋转后新子树与上层树的连接 if (parent == _root) // 如果parent是整棵树的根节点 { _root = subL; // 更新根节点为subL subL->_parent = nullptr; // 根节点的父指针置空 } else // parent不是根节点 { // 判断parent原来是其父节点的左孩子还是右孩子 if (Pparent->_left == parent) { Pparent->_left = subL; // 将subL连接到原parent的位置 } else { Pparent->_right = subL; } subL->_parent = Pparent; // 更新subL的父指针 } // 5. 更新平衡因子：旋转后parent和subL的高度都变为平衡 parent->ph = 0; // parent现在左右子树高度相同 subL->ph = 0; // subL现在左右子树高度相同 }（2）新节点插入较高右子树的右侧：左单旋
因为左单旋的原理和右单旋是类似的，只要理解了右单旋，加上动图的配合，左单旋和后面的双旋都是很好理解的
左单旋代码如下：
//左旋 void rotateL(Node* parent) { // 1. 保存相关节点指针 Node* subR = parent->_right; // parent的右子树（较高右子树） Node* subRL = subR->_left; // subR的左子树 Node* Pparent = parent->_parent; // parent的父节点（用于连接旋转后的新子树） // 2. 处理subRL的重新连接 parent->_right = subRL; // 将subRL作为parent的新右孩子 if (subRL) // 如果subRL存在，更新其父指针 { subRL->_parent = parent; } // 3. 旋转核心：subR成为新的根，parent成为subR的左子树 subR->_left = parent; // parent成为subR的左孩子 parent->_parent = subR; // 更新parent的父指针指向subR // 4. 处理旋转后新子树与上层树的连接 if (parent == _root) // 如果parent是整棵树的根节点 { _root = subR; // 更新根节点为subR subR->_parent = nullptr; // 根节点的父指针置空 } else // parent不是根节点 { // 判断parent原来是其父节点的左孩子还是右孩子 if (Pparent->_left == parent) { Pparent->_left = subR; // 将subR连接到原parent的位置 } else { Pparent->_right = subR; } subR->_parent = Pparent; // 更新subR的父指针 } // 5. 更新平衡因子：旋转后parent和subR的高度都变为平衡 parent->ph = 0; // parent现在左右子树高度相同 subR->ph = 0; // subR现在左右子树高度相同 }（3）新节点插入较高左子树的右侧：先左单旋再右单旋（左右双旋）
这种情况又可以分为两种情况：
不过这两种情况都属于在较高左子树的右侧插入，处理方式都是相同的，唯一的区别在于最后旋转完成后，更新平衡因子时的值不同。
接下来我们以上面的那个情况为例展示左右双旋的过程：
而下面的情况和上面的情况唯一的区别在于，最后更新的平衡因子不同
如何去决定每个节点更新后的平衡因子呢？可以看到这两种情况中，如果在b下面插入新节点，那么旋转过后30和60的平衡因子更新成0，90的平衡因子更新成1；如果在c下面插入新节点，则是60和90的平衡因子更新成0，30的平衡因子更新成-1
而新节点究竟插入到了b下面还是在c下面，我们可以通过插入节点后60的平衡因子来判断
左右双旋代码如下：
//左右旋转 void rotateLR(Node* parent) { // 1. 记录相关节点指针 Node* subL = parent->_left; // parent的左子树 Node* subLR = subL->_right; // subL的右子树（新节点插入的位置） // 2. 记录subLR的平衡因子，用于判断新节点插入的具体位置 int p = subLR->ph; // 保存旋转前的平衡因子 // 3. 双旋操作：先对subL进行左旋，再对parent进行右旋 rotateL(parent->_left); // 对parent的左子树进行左单旋 rotateR(parent); // 对parent进行右单旋 // 4. 根据subLR原来的平衡因子更新旋转后的平衡因子 if (p == 0) // 情况1：subLR本身就是新插入的节点 { subL->ph = 0; // subL平衡 subLR->ph = 0; // subLR平衡 parent->ph = 0; // parent平衡 } else if (p == 1) // 情况2：新节点插入在subLR的右子树 { subLR->ph = 0; // subLR平衡 subL->ph = -1; // subL左子树比右子树高1层 parent->ph = 0; // parent平衡 } else if (p == -1) // 情况3：新节点插入在subLR的左子树 { subLR->ph = 0; // subLR平衡 subL->ph = 0; // subL平衡 parent->ph = 1; // parent右子树比左子树高1层 } else { assert(false); // 平衡因子异常，程序终止 } }（4）新节点插入较高右子树的左侧：先右单旋再左单旋（右左双旋）
这种情况和左右双旋的情况原理一样，我们直接上动图和代码
右左双旋的代码如下：
//右左旋转 void rotateRL(Node* parent) { // 1. 记录相关节点指针 Node* subR = parent->_right; // parent的右子树 Node* subRL = subR->_left; // subR的左子树（新节点插入的位置） // 2. 记录subRL的平衡因子，用于判断新节点插入的具体位置 int p = subRL->ph; // 保存旋转前的平衡因子 // 3. 双旋操作：先对subR进行右旋，再对parent进行左旋 rotateR(parent->_right); // 对parent的右子树进行右单旋 rotateL(parent); // 对parent进行左单旋 // 4. 根据subRL原来的平衡因子更新旋转后的平衡因子 if (p == 0) // 情况1：subRL本身就是新插入的节点 { subRL->ph = 0; // subRL平衡 subR->ph = 0; // subR平衡 parent->ph = 0; // parent平衡 } else if (p == -1) // 情况2：新节点插入在subRL的左子树 { subRL->ph = 0; // subRL平衡 subR->ph = 0; // subR平衡 parent->ph = -1; // parent左子树比右子树高1层 } else if (p == 1) // 情况3：新节点插入在subRL的右子树 { subRL->ph = 0; // subRL平衡 subR->ph = 1; // subR右子树比左子树高1层 parent->ph = 0; // parent平衡 } else { assert(false); // 平衡因子异常，程序终止 } }六、AVL树的查找实现
AVL树的查找操作与普通二叉搜索树完全相同，因为AVL树本质上是一棵平衡的二叉搜索树，保持了二叉搜索树的性质。查找的时间复杂度为 O(log N)，其中N是树中节点的数量。
查找操作的实现如下：
// AVL树的查找函数 Node* Find(const K& key) { Node* cur = _root; // 从根节点开始查找 while (cur) { if (cur->_kv.first < key) // 当前节点的key小于目标key，向右子树查找 { cur = cur->_right; } else if (cur->_kv.first > key) // 当前节点的key大于目标key，向左子树查找 { cur = cur->_left; } else // 找到目标节点 { return cur; } } return nullptr; // 未找到目标节点 }查找操作的原理很简单：从根节点开始，比较目标key与当前节点的key：
- 如果目标key更大，则向右子树继续查找
- 如果目标key更小，则向左子树继续查找
- 如果相等，则找到目标节点
- 如果遍历到空节点仍未找到，则返回nullptr
由于AVL树保持了平衡，查找操作的最坏时间复杂度为 O(log N)，这比普通二叉搜索树在最坏情况下的 O(N) 要好得多。
七、AVL树的平衡检测
为了验证我们实现的AVL树是否正确，我们需要编写一个平衡检测函数。这个函数有两个主要作用：
- 检查每个节点的左右子树高度差是否不超过1（AVL树的基本性质）
- 验证每个节点的平衡因子是否正确更新
首先，我们需要一个计算树高度的辅助函数：
// 计算树的高度（递归实现） int _Height(Node* root) { if (root == nullptr) // 空树高度为0 return 0; // 递归计算左右子树的高度 int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); // 返回较高的子树高度加1（当前节点自身的高度） return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; }接下来是平衡检测的核心函数：
// 检查AVL树是否平衡（递归实现） bool _IsBalanceTree(Node* root) { // 空树也是AVL树 if (nullptr == root) return true; // 计算当前节点左右子树的高度差 int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); int diff = rightHeight - leftHeight; // 实际计算的高度差 // 检查高度差是否超过1（绝对值大于等于2） if (abs(diff) >= 2) { cout << root->_kv.first << "节点高度差异常" << endl; return false; } // 检查平衡因子是否正确（存储的平衡因子应与实际高度差一致） if (root->_bf != diff) { cout << root->_kv.first << "节点平衡因子异常" << endl; return false; } // 递归检查左右子树是否都是AVL树 return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right); } // 提供给外部的平衡检测接口 bool IsBalanceTree() { return _IsBalanceTree(_root); }这个检测函数的工作原理：
- 对于每个节点，计算其左右子树的实际高度差
- 检查高度差的绝对值是否超过1（如果超过，说明不平衡）
- 检查节点存储的平衡因子是否与实际高度差一致（如果不一致，说明平衡因子更新有误）
- 递归检查所有子树
八、AVL树的测试
为了验证AVL树的正确性和性能，我们可以编写测试代码。以下是两个常用的测试用例：
8.1 基础功能测试
// 测试AVL树的基本功能 void TestAVLTree1() { AVLTree<int, int> t; // 测试用例1：常规测试数据 // int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; // 测试用例2：包含双旋场景的特殊数据 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; }8.2 性能和大数据量测试
// 测试AVL树的性能和大量数据插入 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 << "插入" << N << "个节点耗时：" << end2 - begin2 << "ms" << endl; // 验证平衡性 cout << "树是否平衡：" << t.IsBalanceTree() << endl; cout << "树的高度：" << t.Height() << endl; cout << "树的大小：" << t.Size() << endl; // 测试查找性能 size_t begin1 = clock(); // 查找所有存在的值 for (auto e : v) { t.Find(e); } size_t end1 = clock(); cout << "查找" << N << "个节点耗时：" << end1 - begin1 << "ms" << endl; }性能测试的意义：
- 插入性能测试：验证在大数据量下AVL树仍能保持 O(log N) 的插入时间复杂度
- 平衡性验证：确保插入大量随机数据后树仍然保持平衡
- 高度验证：验证树的高度确实在 O(log N) 范围内
- 查找性能测试：验证查找操作的时间复杂度为 O(log N)
九、总结
AVL树是一种严格平衡的二叉搜索树，通过引入平衡因子和四种旋转操作（右单旋、左单旋、左右双旋、右左双旋）来保持树的平衡。其主要特点包括：
- 平衡性保证：任何节点的左右子树高度差不超过1
- 时间复杂度：增删查改操作的时间复杂度均为 O(log N)
- 适用场景：适合查找频繁、插入删除相对较少的场景
- 实现复杂度：实现相对复杂，需要维护平衡因子和进行旋转操作
AVL树的优缺点：
- 优点：
- 严格的平衡保证了最坏情况下的性能
- 查找效率稳定在 O(log N)
- 适合内存中的有序数据存储
- 缺点：
- 插入和删除操作可能需要多次旋转
- 实现相对复杂
- 平衡因子的维护增加了开销
在实际应用中，如果需要更简单的实现，可以考虑红黑树（Red-Black Tree），它在保持较好平衡性的同时，旋转操作更少，实现相对简单。但AVL树作为平衡二叉搜索树的经典实现，理解其原理对于学习更复杂的数据结构非常有帮助。