💓博主CSDN主页:杭电码农-NEO💓
⏩专栏分类:C++从入门到精通⏪
🚚代码仓库:NEO的学习日记🚚
🌹关注我🫵带你学习C++
🔝🔝
1. 前言
如果你不知道什么是二叉搜索树
请一定先阅读这篇文章:
二叉搜索树深度剖析
二叉搜索树如果插入顺序是有序的
那么这棵树的查找效率将会是O(N)
所以说在实际情况下,二叉搜索很少被使用
为了解决二叉搜索树不稳定的问题
于是乎有人提出了AVL树结构,也就是
高度平衡二叉搜索树!
本章重点:
本篇文章着重讲解AVL树的概念以及
定义,并且在模拟实现AVL树前,将AVL
树的插入的情况做系统分析,最后模拟
实现AVL树的插入操作,进一步理解它!
2. AVL树的概念以及特性
AVL树通过一个特性来保证二叉
搜索的平衡性问题: 那就是任一节点两边的子树高度差不超过1!
高度差一般是右子树高度减左子树高度
由于AVL树的这种特殊性质,使得它的
查找效率是百分百的O(logn),可以说
这是天才的发明,当插入或删除节点时,
高度差不符合要求后,可以通过旋转的
方式来重新让这棵树变成AVL树!
下面,我们一般尝试理解AVL树
一边来模拟实现它!
3. AVL树模拟实现基本框架
首先我们应该想到一点,当高度差
大一1时我们需要做处理,但是我们
怎么知道哪个节点高度差大于1呢?因此应该在节点中多定义一个整数来记录当前节点的左右高度差!
AVL树的节点结构体:
template<class K, class V>
struct AVLTreeNode //高度平衡二叉搜索树
{
AVLTreeNode(const pair<K,V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_bf(0)
{}
//用三叉链,方便更新祖先的平衡因子
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
pair<K, V> _kv; //存储的数据
int _bf; //balance factor平衡因子
};
有了节点的结构体后,定义一下
AVL树的基本结构吧:
template<class K,class V>
struct AVLTree
{
typedef AVLTreeNode<K, V> Node;
private:
Node* _root;//定义一个根节点
};
4. AVL树插入函数深度剖析
AVL数的插入有三个步骤:
- 按照二叉搜索树规则插入节点
- 插入完成后更新平衡因子
- 若平衡因子不正确需要采取措施
所以当前目标就是把这三步搞清楚
更新平衡因子规则:
-
新增在右,父亲的bf加一
新增在左,父亲的bf减一 -
更新完成后,父亲的bf==1/-1,说明
父亲插入前的bf一定是0,并且插入后
一边高一边低,需要继续向上更新
- 更新完成后,父亲的bf==0,说明父亲
在插入前的bf是1/-1,并且插入后两边高度
一致,就不需要继续往上更新了!
- 更新完成后,父亲的bf==2/-2,打破
了平衡,父亲所在的子树要旋转处理
由于旋转处理的过程比较复杂
所以先将除了旋转的所有代码写出来
后再去讨论旋转的话题!
5. AVL树插入代码剖析(无旋转)
话不多说,直接上手!
bool insert(const pair<K, V>& kv)//第一步:按照二叉搜索树的方式插入值,第二步:调整平衡因子后旋转
{
if (_root == nullptr)//插入第一个节点时
{
_root = new Node(kv);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)//找到要插入节点的位置和它的父亲
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else return false;
}
//走到这一步后,已经找到了位置,开空间后插入
cur = new Node(kv);
if (parent->_kv.first < kv.first)
parent->_right = cur;
else
parent->_left = cur;
//此时new出来的节点的parent还指向空
cur->_parent = parent;
//插入完成后,此时需要查看平衡因子来控制平衡
//沿着插入的位置往上更新平衡因子
while (parent)//由于parent需要不断向上更新,所以要使用循环!
{
if (cur == parent->_right)
parent->_bf++;
else
parent->_bf--;
if (parent->_bf == 0)//不用向上更新了
break;
else if (parent->_bf == 1 || parent->_bf == -1)//若高度出现变化,需要往上更新
{
parent = parent->_parent;
cur = cur->_parent;
}
else if (abs(parent->_bf) == 2)//说明parent所在的子树不平衡了,需要旋转处理
{
//后面再处理这个过程......
}
}
}
关于代码的解释都在注释中,请耐心查看!
6. AVL树的旋转操作深度剖析(一)
首先,旋转一共由四种情况,不管是
哪一种情况,我们的目的都是将原本
不平衡的树变成符合规则的AVL树!
先看两个最简单的例子:
左单选和右单旋:
大概了解了它的规则后,再来看泛型的:
-
右单旋
-
左单旋:
7. AVL树的旋转操作深度剖析(二)
当你了解了前两种最简单的情况后
就可以来看看"双旋"操作了!
还是先看看最简单的例子:
先左旋再右旋先右旋再左旋
了解了最简单了例子后,直接上手!
8. AVL树旋转的代码实现
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
ppNode->_left = subR;
else
ppNode->_right = subR;
subR->_parent = ppNode;
}
subR->_bf = parent->_bf = 0;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
ppNode->_left = subL;
else
ppNode->_right = subL;
subL->_parent = ppNode;
}
subL->_bf = parent->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
subLR->_bf = 0;
if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
}
else assert(false);
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
subRL->_bf = 0;
if (bf == 1)
{
subR->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)
{
subR->_bf = 1;
parent->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
}
else assert(false);
}
你问我我怎么写出代码的?那是一段痛苦的回忆,代码的验证就交给你们了代码中对于平衡因子的更新有细节!
9. 总结以及所有代码
AVL树的模拟实现属于了解的内容
并不需要完全掌握,所以同学了只需
理解了AVL树的旋转即可,不要求手撕代码!
(当然前几年有学长面试时被要求手撕了doge)
AVL树模拟实现全部代码:文章来源：https://www.toymoban.com/news/detail-752841.html
我的gitee仓库文章来源地址https://www.toymoban.com/news/detail-752841.html
到了这里，关于【C++高阶(三)】AVL树深度剖析&模拟实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![【C++入门到精通】智能指针 shared_ptr 简介及C++模拟实现 [ C++入门 ]](https://imgs.yssmx.com/Uploads/2024/01/813307-1.png)
