【C++】 AVL树深度解析：严格平衡二叉搜索树的终极指南

📚 博主的专栏

🐧 Linux   |   🖥️ C++   |   📊 数据结构

下一篇：红黑树

目录

AVL树的概念

AVL树的实现

插入新节点，调整节点平衡因子

AVL树的旋转

1.（左边高） 新节点插入较高左子树的左侧---左左：右单旋

2. 新节点插入较高右子树的右侧---右右：左单旋

3.左右双旋

请注意：这里一共有3种情况

4.右左双旋：

判断AVL树是否平衡？算树的左右高度差是否在范围内：

大型项目调试小技巧：

AVL树的删除--了解

AVL树的性能

---

本文核心内容总结

知识引导

🌟 AVL树的核心概念

AVL树是一种高度平衡的二叉搜索树，由Adelson-Velskii和Landis提出。通过平衡因子（左右子树高度差）的严格限制（绝对值≤1），确保树的高度始终为$O(\log n)$，从而保证搜索、插入、删除操作的高效性。
🔑 核心优势：适用于静态数据或查询密集型场景，如数据库索引、内存管理等。

📜 AVL树的五大性质

1. 二叉搜索树性质：左子树 < 根节点 < 右子树。

2. 平衡因子约束：每个节点的平衡因子为 -1、0、1。⚖️

3. 高度平衡：任意子树高度差不超过1。

4. 动态调整：插入/删除后通过旋转恢复平衡。🔄

5. 时间复杂度：所有操作均保持 $O(\log n)$。⏱️

🛠️ AVL树的插入与平衡调整

插入分为两步：

1. 二叉搜索树插入：按Key值插入新节点。

2. 平衡因子更新与旋转：从插入节点向上回溯，调整平衡因子，必要时旋转子树。

🔍 平衡因子更新规则

• 插入左侧：父节点平衡因子 -1。

• 插入右侧：父节点平衡因子 +1。

• 终止条件：

  • 平衡因子为 0：子树高度不变，停止更新。

  • 平衡因子为 2/-2：触发旋转操作。

void Insert(const pair<K, V>& kv) {// 插入新节点// 向上更新平衡因子，触发旋转
}

⚙️ AVL树的四种旋转操作

1. 右单旋（LL型失衡）

• 场景：新节点插入左子树的左侧。

• 操作：左子节点提升为根，原根节点变为右子树。

• 平衡因子重置：原根和左子节点平衡因子归零。

void RotateR(Node* parent) {// 右单旋代码实现
}

2. 左单旋（RR型失衡）

• 场景：新节点插入右子树的右侧。

• 操作：右子节点提升为根，原根节点变为左子树。

• 平衡因子重置：原根和右子节点平衡因子归零。

void RotateL(Node* parent) {// 左单旋代码实现
}

3. 左右双旋（LR型失衡）

• 场景：新节点插入左子树的右侧。

• 操作：先左旋左子树，再右旋根节点。

• 平衡因子调整：根据子节点位置动态更新。

void RotateLR(Node* parent) {RotateL(parent->left);RotateR(parent);
}

4. 右左双旋（RL型失衡）

• 场景：新节点插入右子树的左侧。

• 操作：先右旋右子树，再左旋根节点。

• 平衡因子调整：根据子节点位置动态更新。

void RotateRL(Node* parent) {RotateR(parent->right);RotateL(parent);
}

🧪 AVL树的验证与调试

1. 高度验证：递归计算左右子树高度差是否≤1。

2. 平衡因子验证：检查每个节点的平衡因子是否与高度差一致。

bool IsBalance() {return _IsBalance(_root); // 递归验证高度与平衡因子
}

调试技巧：

• 使用条件断点定位失衡节点。🔍

• 可视化插入前后的树结构对比。🌳

⚡ AVL树的性能分析

• 优势：严格平衡保证查询效率（$O(\log n)$），适合静态数据场景。

• 劣势：频繁插入/删除时旋转成本高，性能低于红黑树。

• 适用场景：数据库索引、编译器符号表等查询密集型应用。

---

AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度（普通搜索二叉树就会有高度差较大，降低搜索效率）。

 例如：在有2/4个节点的时候，做不到左右高度差相等

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

• 它的左右子树都是AVL树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在$O(log_2 n)$，搜索时间复杂度O($log_2 n$)

平衡因子 = 右子树高度 - 左子树高度

1.按照搜索树规则插入

2.更新插入节点的祖先节点的平衡因子

• a、插入父亲的左边，父亲平衡因子--
• b、插入父亲的右边，父亲平衡因子++

是否需要更新祖先的平衡因子？

• c、需要更新：父亲的平衡因子 == 1 or -1，父亲所在的子树高度改变，需要向上更新，因为对于祖先来说，父亲所在子树的高度变化，插入结束。
• d、不需要更新：父亲的平衡因子 == 0，父亲所在的子树高度不变，不需要向上更新，插入结束        
• e、父亲平衡因子 == 2 or -2，父亲所在的子树已经不平衡了，需要旋转处理

如图：

AVL树的实现

这里是将之前所讲过的搜索二叉树KV版本直接拿过来修改，这是修改过后：未旋转版

插入新节点，调整节点平衡因子

1. 按照二叉搜索树的方式插入新节点

2. 调整节点的平衡因子

#include<assert.h>
#include<iostream>
#include<string>
using namespace std;
namespace AVL
{template<class K, class V>struct AVLTreeNode{//在K_V添加了parentAVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf = 0; //balance factorpair<K, V> _kv;AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv){}};template<class K, class V>class 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; //往右节点走之前，先存下parentcur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else//默认定义（90%的情况下），搜索树不允许冗余，因此若值相等就不插入 {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) {// 需要旋转（未实现）break;}else {assert(false); // 平衡因子异常}}return true;}Node* Find(const pair<K, V>& kv){Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){cur = cur->_left;}else if (cur->_kv.first < kv.first){cur = cur->_right;}else{return cur;}}return nullptr;}void InOrder(){_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << " ";_InOrder(root->_right);}Node* _root = nullptr;};inline void TestAVLTree1(){int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };AVLTree<int, int> t1;for (auto e : a){t1.Insert({e, e});}t1.InOrder();}
}

AVL树的旋转

假设 h == 0，插入一个新节点

h == 1

h == 2 的 AVL树有三种    a一定是z（注意是需要旋转）

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

1.（左边高） 新节点插入较高左子树的左侧---左左：右单旋

让b为60的左边，60为30的右边

首先左子树小于根节点小于右子树，右子树大于根节点大于左子树。

b > 30，b < 60，c > 60，60 > 30，因此让b去做60的左子树，60去做30的右子树不违和

代码编写：

		void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;//还需要更改subLR父亲,但是有可能subLR为空if(subLR) subLR->_parent = parent;subL -> _right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;//有可能parent就是这棵树的根节点;或者是这棵树的子树,就需要找到ppNodeif (parent == _root){_root = subL;_root->_parent = nullptr;}else{//先判断parent是父节点的左子树还是右if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}//再更改parent的平衡因子parent->_bf = subL->_bf = 0;}

2. 新节点插入较高右子树的右侧---右右：左单旋

30<b<60<c 仍然遵循搜索树

同理 

    	void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;//还需要更改subRL父亲,但是有可能subLR为空if (subRL) subRL->_parent = parent;subR -> _left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;//有可能parent就是这棵树的根节点;或者是这棵树的子树,就需要找到ppNodeif (parent == _root){_root = subR;_root->_parent = nullptr;}else{//先判断parent是父节点的左子树还是右if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}//再更改parent的平衡因子parent->_bf = subR ->_bf = 0;}

如何调用右旋，左旋，修改insert,根据平衡因子

                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);}break;
}

注意：旋转完了就不用向上再更新了，因为此时这个子树已经平衡了，对于整个二叉树来说，高度没有变化

---

3.左右双旋

新节点插入较高左子树的右侧---左右：先左单旋再右单旋

h = 0        这里的60是插入的节点

h = 1        可以在60的左右分别插入节点

如图先以30为旋转点，进行左单旋，60成为30的父节点，对于90来说，整棵树变成单纯的左边高

再以90为旋转点，进行右单旋，让60成为90的父节点。（30 < b < 60 < c < 90）

请注意：这里一共有3种情况

1.60自己新增，它的初始是0，旋转后平衡因子都为0，也就是这种情况：

2.60的平衡因子是-1，就代表b插入

3.60的平衡因子是1，就代表c插入

场景一：抽象图在b插入     

场景二：抽象图在c插入

 如图我们以h == 1的示例具体图来模拟这个旋转

void RotateLR(Node* parent)  //左右双旋 --parent的平衡因子是-2，代表左边高，parent->_left是1，//因此先左旋parent->_left，再右旋parent
{//先对cur进行左单旋,也就是parent的leftRotateL(parent->_left);RotateR(parent);
}

但是在单旋函数内部会将父节点以及父节点的left或者right的平衡都改为0

因此需要提前记录节点，并在双旋函数中再对次进行修改，根据以上的三种情况根据subLR的平衡因子，看是在subLR的左插入还是右

Node* subL = parent->_left;
Node* subLR = subL->_right;int bf = subLR->_bf;  //用于区分三种情况，自己是新增，在subLR左边新增or右边新增

再由subLR的平衡因子来分情况讨论

 			if (bf == -1)//在subLR的左边插入，最终情况就是，subLR的左给SubL，parent缺左{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if(bf == 1)//在subLR的右边插入，最终情况，subLR的右给parent的左,subL缺右。{subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == 0)//subLR自己是新增，他的左右为空因此，旋转过后，高度不变{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}

4.右左双旋：

可以发现只靠左单旋右单旋，无法让整个子树变成AVL树，并且循环仿佛，也不符合单旋的要求

如何判断？可观察单旋的平衡因此的符号都相同，而双旋的的平衡因子是相反数，高的方向出现了折现就是双旋，高的方向是一个直线就是单旋，也可以观察图的区别 

经过这个单旋，变成单纯的右边高，因此再使用一个左单旋，就可以平衡

与左右双旋同理：

void RotateRL(Node* parent)  //右左双旋 --parent的平衡因子是2，代表右子树更高，(parent->_right是-1//，代表左边高，因此先右旋(parent->_right，再左旋parent
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);//..if (bf == 1)  //在subRL的右边插入，最终情况，subRL的右给subR,subRL的左给parent的右。parent右还缺一个{subRL->_bf = 0;subR->_bf = 0;parent->_bf = -1;}else if(bf == -1){subRL->_bf = 0;subR->_bf = 1;parent->_bf = 0;}else if (bf == 0){subRL->_bf = 0;subR->_bf = 0;parent->_bf = 0;}else{assert(false);}}

判断AVL树是否平衡？算树的左右高度差是否在范围内：

并且还要判断平衡因子是否正确

		int _Height(Node* root){if (root == nullptr)return 0;return max(_Height(root->_left), _Height(root->_right)) + 1;}bool _IsBalance(Node* root){//判断当前树if (root == nullptr)	return true;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);//不平衡if (abs(leftHeight - rightHeight) >= 2){return false;}//顺带检查平衡因子是否正确if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left) && _IsBalance(root->_right);}

大型项目调试小技巧：

1.先看是插入谁导致出现的问题

2.打条件断点，画出插入前的树

3.单步跟踪，对比图———分析细节原因

如果所遇到的代码量大，此时可通过条件断点的方式，通过打印的办法，判断出谁出错，想在他这里停止下来。

AVL树的删除--了解

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不错与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置

AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即$log_2 (N)$。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

结语：

       随着这篇关于题目解析的博客接近尾声，我衷心希望我所分享的内容能为你带来一些启发和帮助。学习和理解的过程往往充满挑战，但正是这些挑战让我们不断成长和进步。我在准备这篇文章时，也深刻体会到了学习与分享的乐趣。

   

         在此，我要特别感谢每一位阅读到这里的你。是你的关注和支持，给予了我持续写作和分享的动力。我深知，无论我在某个领域有多少见解，都离不开大家的鼓励与指正。因此，如果你在阅读过程中有任何疑问、建议或是发现了文章中的不足之处，都欢迎你慷慨赐教。               

        你的每一条反馈都是我前进路上的宝贵财富。同时，我也非常期待能够得到你的点赞、收藏，关注这将是对我莫大的支持和鼓励。当然，我更期待的是能够持续为你带来有价值的内容，让我们在知识的道路上共同前行。