一、前言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树节点的定义如下这里简单介绍一下pairpair可以将两个数据组成一组元素因此对于key/value模型这种需要用到两个数据为一组的元素时就可以使用内部的成员变量为first和second其主要使用方法为pairT1, 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树的结构定义 templateclass K, class V class AVLtree { typedef AVLnodeK, V Node; // 定义节点类型别名 public: // 插入函数向AVL树中插入一个键值对 bool insert(const pairK, 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为nullptrparent是待插入位置的父节点 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的平衡因子更新成090的平衡因子更新成1如果在c下面插入新节点则是60和90的平衡因子更新成030的平衡因子更新成-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) // 情况1subLR本身就是新插入的节点 { 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) // 情况1subRL本身就是新插入的节点 { 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树是否正确我们需要编写一个平衡检测函数。这个函数有两个主要作用检查每个节点的左右子树高度差是否不超过1AVL树的基本性质验证每个节点的平衡因子是否正确更新首先我们需要一个计算树高度的辅助函数// 计算树的高度递归实现 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() { AVLTreeint, 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; // 测试数据量 vectorint v; v.reserve(N); // 预分配空间 // 生成随机数 srand(time(0)); for (size_t i 0; i N; i) { v.push_back(rand() i); // 避免重复 } // 测试插入性能 size_t begin2 clock(); AVLTreeint, 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树作为平衡二叉搜索树的经典实现理解其原理对于学习更复杂的数据结构非常有帮助。