网硕互联帮助中心 
🏆浮世尘弦：个人主页
⭐个人专栏：《C语言》、《数据结构与算法》、《C++》
💎：非淡薄无以明志，非宁静无以致远
前言
普通二叉搜索树在数据接近有序时容易退化成链表，查找效率会从 O(log n) 降到 O(n)。而AVL树通过控制每个节点左右子树的高度差，让树在插入后始终保持相对平衡。
本文先用 C++ 认识 AVL 树及其节点结构，再完整模拟一次插入：寻找位置、插入节点、更新平衡因子。随后依次分析右单旋、左单旋、左右双旋和右左双旋四种调整方式，并实现查找操作与 AVL 树判定。
整个过程沿着“插入、失衡、旋转、恢复平衡”的路径展开，不急于堆砌代码，而是弄清每一步为何发生、为什么选择这种调整。
让我们开始今天的学习吧！
目录
前言
一，介绍AVL树
二，模拟实现AVL树
1，AVL树节点
2，AVL树的插入
1，寻找插入位置并插入
2，更新平衡因子
3，旋转
1，右单旋
2，左单旋
3，左右双旋
4，右左双旋
4，AVL树的查找
5，判断是否是AVL树
结尾
一，介绍AVL树
AVL树是最先被发明的自平衡二叉搜索树，AVL树要么是一个空树，要么具有以下特点：
左右子树都是AVL树，且每个节点的左右子树高度差都不超过1
核心概念：平衡因子（bf）
每个节点都有一个平衡因子，用来记录左右子树的高度差。
高度差合理取值：-1,0,1 如果平衡因子的值为2，-2，表明这棵树不平衡需要进行调整（旋转）
AVL树的结构和完全二叉树类似，高度大约在logN,相较于二叉搜索树增删查改平均为O(N),最好O(logN).AVL增删查改的效率严格为O(logN)，效率较高。
二，模拟实现AVL树
1，AVL树节点
AVL树的节点由五部分构成：1，关键字key，也可以为pair类型。2，指向左子树的指针：left
3,指向右子树的指针：right 4，指向父亲节点的指针 5，平衡因子bf
template <class K,class V>
//AVL数节点
struct AVLTreeNode
{
//struct默认为公有
pair<K, V> kv;
AVLTreeNode* left;
AVLTreeNode* right;
AVLTreeNode* parent;
int bf;//平衡因子
AVLTreeNode(const pair<K, V>& p)
:kv(p)
, left(nullptr)
, right(nullptr)
,parent(nullptr)
,bf(0)
{}
};
2，AVL树的插入
插入步骤：
1，寻找插入位置并插入
寻找位置和插入的规则和平衡二叉树插入值的过程一样。
从根节点位置开始，比较节点值的大小。走向左子树或者右子树。知道找到插入位置。
注意:要提前设计一个父亲节点，提前记录位置，方便插入。
template <class K,class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
//插入
bool Insert(pair<K, V> p1)
{
//根节点为空
if (root == nullptr)
{
root = new Node(p1);
return true;
}
//根节点不为空，找到要插入的位置
Node* cur = root;
Node* parent = nullptr;
while (cur)
{
if (p1.first > cur->kv.first)
{
parent = cur;
cur = cur->right;
}
else if (p1.first < cur->kv.first)
{
parent = cur;
cur = cur->left;
}
else //不能存在相同节点
{
return false;
}
}
//进行插入
cur = new Node(p1);
if (p1.first > parent->kv.first)
{
parent->right = cur;
}
else
{
parent->left = cur;
}
cur->parent = parent;
2，更新平衡因子 ⭐
平衡因子的更新规则：
平衡因子= 右子树高度- 左子树高度
只有子树高度变化才会影响当前节点的平衡因子。
插入节点会影响当前节点parent的平衡因子，插入在右边当前平衡因子++，插入在左边当前平衡因子–。
parent节点位置的平衡因子是否发生变化会影响是否需要向上进行更新平衡因子。
更新平衡因子的三种情况：
1，更新后parent的平衡因子值为0，说明更新前parent的平衡因子是-1/1。
表明插入前子树一边高一边低，而新插入的节点位于较低的一侧。故该节点子树高度没有进行变化，不影响上层的平衡节点。故不需要向上进行更新。
2，更新后parent的平衡因子值为-1/1，说明更新前parent的平衡因子是0。
表明插入前子树是平衡的，而新插入一个节点导致子树一边高一边低。子树的高度变化了，影响了上层的平衡因子，需要向上进行更新。
3，更新后parent的平衡因子值为-2/2，说明更新前parent的平衡因子是-1/1。
表明插入前子树就是一边高一边低，而新插入的节点在较高的那一侧。导致高的更高。破坏了AVL树的平衡。需要进行旋转调整。旋转需要实现两个目标：1，把parent子树旋转平衡。2，降低parent子树的高度，恢复到插入节点前的高度。完成后不需要向上更新平衡因子，应为子树的高度没有变化。
4，最坏需要更新到根节点。
插入中更新平衡因子部分：
//处理平衡因子
while (parent)
{
if (cur == parent->left)
{
parent->bf–;
}
else
{
parent->bf++;
}
if (parent->bf == 0)
{
return true;
}
else if (parent->bf == 1 || parent->bf == -1)//向上跟新
{
cur = parent;
parent = parent->parent;
}
else if (parent->bf == 2 || parent->bf == -2)//需要旋转
{
//右旋
if (cur->bf == -1 && parent->bf == -2)
{
RotateR(parent);
}
//左旋
else if (cur->bf == 1 && parent->bf == 2)
{
RotateL(parent);
}
//左右旋
else if (cur->bf == 1 && parent->bf == -2)
{
RotateLR(parent);
}
//右左旋
else if (cur->bf == -1 && parent->bf == 2)
{
RotateRL(parent);
}
else
{
assert(false);
}
break; //旋转完后跳出
}
else
{
assert(false);
}
}
return true;
}
3，旋转 ⭐
旋转的目的：
1，让旋转的树由不平衡转向平衡，同时降低旋转树的高度，不影响上层节点的平衡因子。
1，右单旋
右单旋抽象图：
上图中的10可能是整棵树的根，也可能是一颗局部子树的根。a,b,c是抽象成高度为h（h>=0）的子树，抽象的好处在于：不需要考虑a/b/c内部是什么结构。
旋转的步骤：
那边高就需要将根节点朝着相反的方向按下去。
1，将parent插入到subL的右子树。
2，subLR作为parent的右子树
3，如果parent之前只是局部子树的根节点，需要更新更上层节点的链接subL
下面是h不同值的实际图：
当h= 0时：
当h = 1时：
当h = 2时：
旋转代码实现：
//右旋
void RotateR(Node* p)
{
Node* subL = p->left;
Node* subLR = subL->right;
p->left = subLR;
if (subLR != nullptr)//可能为空处理一下
subLR->parent = p;
subL->right = p;
if (p == root)
{
root = subL;
subL->parent = nullptr;
}
else
{
Node* pparent = p->parent;
//parent原来不是根
if (pparent->left == p)
{
pparent->left = subL;
}
else
{
pparent->right = subL;
}
subL->parent = pparent;
}
p->parent = subL;
p->bf = 0;
subL->bf = 0;
}
2，左单旋
左单旋就相当于右旋的反面，十分类似，下面简单解释一下：
左单旋抽象图：
旋转的步骤：
1，将parent部分（蓝色）插入到subR的左子树处
2，subRL插入到parent的右子树处
3，如果parent之前只是局部子树的根节点，需要更新更上层节点的链接subR
代码实现：
//左旋
void RotateL(Node* p)
{
Node* subR = p->right;
Node* subRL = subR->left;
p->right = subRL;
if (subRL)
subRL->parent = p;
subR->left = p;
if (p == root)
{
root = subR;
subR->parent = nullptr;
}
else //p不是根节点
{
Node* pparent = p->parent;
if (pparent->left == p)
{
pparent->left = subR;
}
else
{
pparent->right = subR;
}
subR->parent = pparent;
}
p->parent = subR;
p->bf = subR->bf = 0;
}
3，左右双旋
先看这样两组案例：
左边高，但是新插入的节点在b位置，仅仅进行右单旋是不行的，旋转后的还是不平衡。
此时将上面的场景抽象成下面的结构图：
根据插入的位置可以分成三种情景：
这种情况插入节点后，parent和subL，subLR的平衡因子是异号的。这是和只单独旋转的一个较大的区别。
插入后需要先对subL进行左单旋，然后对整体parent进行右单旋。就可以达成平衡。
左右双旋代码:
//双旋-先左后右
void RotateLR(Node* p)
{
Node* subL = p->left;
Node* subLR = subL->right;
int _bf = subLR->bf;
RotateL(subL);
RotateR(p);
if (_bf == -1)
{
subL->bf = 0;
subLR->bf = 0;
p->bf = 1;
}
else if (_bf == 1)
{
subL->bf = -1;
subLR->bf = 0;
p->bf = 0;
}
else if (_bf == 0)
{
subL->bf = 0;
subLR->bf = 0;
p->bf = 0;
}
else//防御性编程，可以不写
{
assert(false);
}
}
4，右左双旋
右左双旋的情况和左右双旋的情况类似，下面简单解释一下
直接看抽象结构图：
根据插入的不同位置可以分成三种场景：
parent和subR以及subRL的平衡因子依旧是异号的。
插入后先对subR进行右单旋，再对parent进行左单旋，就可以达到平衡。
右左双旋代码：
//双旋-先右后左
void RotateRL(Node* p)
{
Node* subR = p->right;
Node* subRL = subR->left;
int _bf = subRL->bf;
RotateR(subR);
RotateL(p);
if (_bf == -1)
{
subR->bf = 1;
subRL->bf = 0;
p->bf = 0;
}
else if (_bf == 1)
{
subR->bf = 0;
subRL->bf = 0;
p->bf = -1;
}
else if (_bf == 0)
{
subR->bf = 0;
subRL->bf = 0;
p->bf = 0;
}
else//防御性编程
{
assert(false);
}
}
4，AVL树的查找
直接从根节点根据AVL树的规则向下进行查找。
AVL树查找代码：
//查找
Node* Find(const K& k)
{
Node* cur = root;
while (cur)
{
if (k > cur->kv.first)
{
cur = cur->right;
}
else if (k < cur->kv.first)
{
cur = cur->left;
}
else //找到了
{
return cur;
}
}
return nullptr;
}
5，判断是否是AVL树
1，左右高度差不超过1，同时左右都是AVL树
//判断是否是一颗AVL树
bool _IsAVLTree(Node* root)
{
//空树也是一个AVL树
if (root == nullptr)
return true;
int leftHeight = _Height(root->left);
int rightHeight = _Height(root->right);
int d = rightHeight – leftHeight;
if (abs(d) >= 2)
{
cout << "高度差异常" << endl;
return false;
}
if (d != root->bf)//平衡因子和高度差对不上
{
cout << "平衡因子异常" << endl;
return false;
}
//保证左右子树都是AVL树
return _IsAVLTree(root->left) && _IsAVLTree(root->right);
}
测试结构排序代码：
测试性能：
// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等
void TestAVLTree2()
{
const int N = 1000000;
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 << "Insert:" << end2 – begin2 << endl;
cout << t.IsAVLTree() << endl;
cout << "Height:" << t.Height() << endl;
cout << "Size:" << t.Size() << endl;
size_t begin1 = clock();
// 确定在的值
for (auto e : v)
{
t.Find(e);
}
size_t end1 = clock();
cout << "Find:" << end1 – begin1 << endl;
}
int main()
{
TestAVLTree2();
return 0;
}
测试结果：
结尾
本篇文章中所涉及到的代码：
gitee链接：AVL树的实现
以上就是本文的全部内容了，如果对你有所帮助的话，请大佬不妨给博主来个“一键三连”，这对我是大大的支持，也能让博主产出更优质的内容。
往期回顾：
【C++】《手撕二叉搜索树：删除才是真正的分水岭》
【C++】map 与 set 的关联式容器实践
总结：本文系统讲解了AVL树的原理与模拟实现，涵盖节点结构、插入操作、平衡因子更新及四种旋转机制（右单旋、左单旋、左右双旋、右左双旋），确保树始终保持平衡。通过插入后自上而下的平衡因子调整与旋转，保障增删查效率稳定在O(logN)。文章还实现了查找、判断是否为AVL树等功能，并通过性能测试验证其高效性，适合深入理解自平衡二叉搜索树的实现逻辑。
⚡把上面的内容吃透就休息一下吧⚡
评论前必须登录！
注册