【数据结构】AVL树(平衡二叉搜索树)

🕗 发布于 2024-07-26 02:28 数据结构

文章目录

1.AVL树

在这里插入图片描述

1.AVL树

在前面，我们已经介绍过了二叉搜索树，也了解到二叉搜索树查找的效率非常的高。但是在数据有序或接近有序时，它就会退化成单边树，那样效率就变得非常低了。所以我们也一直说二叉搜索树的搜索的时间复杂度是O(N)(高度次)，并不是O(log₂N)。
在这里插入图片描述

因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

1.1 AVL树的概念

由于二叉搜索树可能会退化，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

为什么要求左右子树的高度之差不超过1就可以呢？

对于所有形状的子树来说，如果他有2ⁿ-1个节点，那它就可以保持绝对的平衡；如果他有2ⁿ (n >= 1)个节点，就无法做到绝对的平衡，最好的结果就是子树高度相差一。

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

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

在这里插入图片描述

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果他有n个节点，其高度可保持在log₂N，搜索的时间复杂度就是log₂N。

1.2 AVL树节点的定义

为了方便确认一棵树是否是AVL树，我们在节点中定义一个平衡因子，通过它来记录每棵树左右子树的高度。

如果右子树比左子树高一层，那平衡因子就是1；如果左右子树一样高，那平衡因子就是0；如果左子树比右子树高一层，那平衡因子就是-1。此时AVL树的性质都没有被打破。

当左子树比右子树高两层，那平衡因子就是-2；或者右子树比左子树高两层，平衡因子就是2，此时AAVL树的性质就被打破了，需要调整。

在调整失衡的AVL树时，我们需要频繁的访问其父节点，因此我们给每个节点定义一个指向父亲的指针

template<class K, class V>
struct AVLTreeNode
{
pair<K, V> _kv;  //存放数据
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _prev;  //指向当前节点的父亲
int _bf;//平衡因子

AVLTreeNode(const pair<K,V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,prev(nullptr)
,_bf(0)
{}
};

1.3 AVL树的插入

AVL树的插入与普通二叉搜索树的插入基本一致。唯一的区别就是AVL树插入节点后需要判断AVL树是否失衡，存在失衡就需要调整。

我们平衡因子是使用右子树的高度-左子树的高度，因此，如果新节点插入到父节点的右边，那父亲的平衡因子+1；如果新节点插入到父亲节点的左边，那父亲的平衡因子-1。
在这里插入图片描述
对于情况二来说，新节点的插入不会影响其祖先的平衡因子的改变，因为子树的高度没有改变。
对于情况一来说，新节点的插入会影响其祖先的平衡因子的改变，因为子树的高度变高了。

在这里插入图片描述
所以，对于情况一来说，我们新插入节点后，还要观察其祖先的平衡因子是否变化，变化后是否需要调整。

那么下面我们就先将节点插入到树中：

bool insert(const pair<K, V>& kv)
{
//插入前是空树
if (_root == nullptr)
{
//新插入的节点就是根
_root = new Node(kv);
_root->_prev = nullptr;
return true;
}
else
{
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;
cur->_prev = parent;//指向父亲

//判断树是否失衡
//...
}
}

更新父亲/祖先的平衡因子

//判断树是否失衡
while (parent)
{
//更新父亲的平衡因子
if (parent->_left == cur)
parent->_bf--;
else
parent->_bf++;

if (parent->_bf == 0)//属于情况二，不影响祖先
break;
//情况一，影响祖先的平衡因子，需要继续更新
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = cur->_prev;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//旋转处理
break;
}
else
{
assert(false);//平衡因子异常了
}
}

1.4 AVL树的旋转

AVL树的旋转分为四种情况：

左单旋
右单旋
左右双旋
右左双旋

下面，我们对这四种情况具体分析

1.4.1 左单旋

新节点插入到较高右子树的右侧- -左单旋
在这里插入图片描述
在旋转过程中，有以下几种情况需要考虑：

7节点的左孩子可能存在，也可能不存在
6可能是根节点，也可能是子树
- 如果是根节点，旋转完成后，根节点就是7
- 如果是子树，可能是某个节点的左子树，也可能是右子树，需要判断以后连接

void RotateL(Node* parent)
{
Node* subR = parent->_right;//父亲的右孩子

Node* subRL = subR->_left;//右孩子的左孩子
//升高度，连孙子
parent->_right = subRL;
if (subRL)
subRL->_prev = parent;

Node* parentPrev = parent->_prev;
//降高度，变父亲
subR->_left = parent;
parent->_prev = subR;

//连接旋转后的子树
subR->_prev = parentPrev;
if (parentPrev == nullptr)
{
//如果原父亲就是根，旋转后的儿子变根
_root = subR;
}
else
{
//原父亲是子树，判断儿子连接在哪一边
if (parentPrev->_left == parent)
parentPrev->_left = subR;
else
parentPrev->_right = subR;
}
//更新平衡因子
subR->_bf = 0;
parent->_bf = 0;
}

1.4.2 右单旋

新节点插入到较高左子树的左侧- - 右旋

在这里插入图片描述
在旋转过程中，有以下几种情况需要考虑：

5节点的右孩子可能存在，也可能不存在
6可能是根节点，也可能是子树
- 如果是根节点，旋转完成后，根节点就是5
- 如果是子树，可能是某个节点的左子树，也可能是右子树，需要判断以后连接

void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
//升高度，连孙子
parent->_left = subLR;
if (subLR)
subLR->_prev = parent;

Node* parentPrev = parent->_prev;
//降高度，变父亲
subL->_right = parent;
parent->_prev = subL;

//新父亲指向前
subL->_prev = parentPrev;

if (nullptr == parentPrev)
{
//如果原父亲就是根，旋转后的儿子变根
_root = subL;
}
else
{
//原父亲是子树，判断儿子连接在哪一边
if (parentPrev->_left == parent)
parentPrev->_left = subL;
else
parentPrev->_right = subL;
}

subL->_bf = 0;
parent->_bf = 0;
}

1.4.3 右左双旋

新节点插入到较高右子树的左侧- -右左双旋
在这里插入图片描述
所以，为了解决这种情况，我们可以将这种歪脖树先变成一棵单边树，然后再进行单旋即可。

为了满足所有情况，我们下面使用抽象图再画一遍
在这里插入图片描述

在这里插入图片描述

观察上图我们可以发现，双旋就是一种抛弃自己的孩子，独自登基的感觉，因此对于旋转后平衡因子的改变，取决于新节点插入到哪一边，最后又到哪里去。

void RotateRL(Node* parent)
{
//由于单旋会改变节点的位置以及平衡因子，所以提前记录

Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;

RotateR(parent->_right);
RotateL(parent);

//修改平衡因子
if (bf == 0)//subRL插入前是空
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == 1)//subRL之前是一棵树，新节点插入其  右侧
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else //subRL之前是一棵树，新节点插入其  左侧
{
parent->_bf = 0;
subR->_bf = -1;
subRL->_bf = 0;
}
}

在这里插入图片描述

1.4.4 左右双旋

新节点插入到较高左子树的右侧–左右双旋

最简单的情况，2的右子树插入前为空
在这里插入图片描述

抽象图
在这里插入图片描述
跟右左双旋基本一样，这里就不赘述了，咱们直接开旋。

平衡因子的改变也需要小心。

void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;

RotateL(parent->_left);
RotateR(parent);

if (bf == 0) // subLR插入前为空
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1) //subLR是一棵树，新节点插入到树的  右侧
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else              //subLR是一棵树，新节点插入到树的  左侧
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
}

在这里插入图片描述

下面就是更新平衡因子的整体思路：

//判断树是否失衡
while (parent)
{
//更新父亲的平衡因子
if (parent->_left == cur)
parent->_bf--;
else
parent->_bf++;

if (parent->_bf == 0)//属于情况二，不影响祖先
break;
//情况一，影响祖先的平衡因子，需要继续更新
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = cur->_prev;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//旋转处理
//左单旋
//    p                     cur
//      cur      --->    p      new
//         new
if (parent->_bf == 2 && cur->_bf == 1)
RotateL(parent);
//右单旋
//p               cur
//cur      --->   new     p
//new
else if (parent->_bf == -2 && cur->_bf == -1)
RotateR(parent);
//右左双旋
//     p            p                  cur
//        cur  -->    cur      -->   p     new
//     new                new
else if (parent->_bf == 2 && cur->_bf == -1)
RotateRL(parent);
//左右双旋
//      p             p            cur
//  cur      -->    cur      --> new   p     
//     new        new
else if (parent->_bf == -2 && cur->_bf == 1)
RotateLR(parent);
else
assert(false);

break;//旋转后，以parent为根的树已经平衡，无需继续向上更新
}
else
{
assert(false);//平衡因子异常了
}

总结：
假如以Parent为根的子树不平衡，即Parent的平衡因子为2或者-2，分以下情况考虑

Parent的平衡因子为2，说明Parent的右子树高，设Parent的右子树的根为SubR
- 当SubR的平衡因子为1时，执行左单旋
- 当SubR的平衡因子为-1时，执行右左双旋
Parent的平衡因子为-2，说明Parent的左子树高，设Parent的左子树的根为SubL
- 当SubL的平衡因子为-1是，执行右单旋
- 当SubL的平衡因子为1时，执行左右双旋

旋转完成后，原Parent为根的子树个高度降低，已经平衡，不需要再向上更新。

1.5 AVL树的平衡验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

验证其为二叉搜索树
- 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
验证其为平衡树
- 每个节点子树高度差的绝对值不能超过1
- 节点的平衡因子是否计算正确

int Height(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);

return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

bool _isBalanceTree()
{
return isBalanceTree(_root);
}

bool isBalanceTree(Node* root)
{
if (root == nullptr)//空树也是平衡二叉搜索树
return true;

int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);

int gap = rightHeight - leftHeight;  //计算root的平衡因子
// 如果计算出的平衡因子与root的平衡因子不相等，或者
//root平衡因子的绝对值超过1，则一定不是AVL树
if (gap != root->_bf || (gap > 1 || gap < -1))
{
return false;
}
return isBalanceTree(root->_left) && isBalanceTree(root->_right);
}

在这里插入图片描述

1.6 AVL树的删除

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除
(分析有无左右孩子，若仅有一个孩子，则直接将删除节点连接孩子；若有两个孩子，将删除节点替换为删除节点的左子树的最大或右子树的最小)
然后再更新平衡因子，只不过与插入不同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。

1.7 AVL树的性能

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

在这里插入图片描述

原文地址：https://blog.csdn.net/weixin_69380220/article/details/140620087

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：通信原理-实验六：实验测验
下一篇：python写一个可以深度学习的程序

info 命令：查看命令手册
在 Linux 系统中，可以使用man 查看普通的帮助手册。还可以使用info 命令阅读 Info 格式的文档。info 文档的特点：大量使用超链接，通过方向键将光标移动到链接的文字，按下回车
阅读更多2024-09-20
【内网渗透】最保姆级的春秋云镜Privilege打靶笔记
在xradmin/ruoyi-admin/src/main/resources/application-druid.yml找到Oracle的账密。internal-secret/credentials
阅读更多2024-09-20
【PyTorch】深入浅出PyTorch
Why learn PyTorchPyTorch日益增长的发展速度与深度学习时代的迫切需求构建知识体系熟悉知识分布对应查缺补漏
阅读更多2024-09-20
uniapp快速入门教程，内容来源于官方文档，仅仅记录快速入门需要了解到的知识点
官方文档：https://uniapp.dcloud.net.cn/必需技术：uniapp、vuejs 3、ES6及以上常用语法、pinia、css、scss‌‌ES6（‌ECMAScript 6）是
阅读更多2024-09-20
卷积和add、sub、mean等的转换
1的卷积，那么结果的大小为500。
阅读更多2024-09-20
搜维尔科技：OptiTrack采集到的平衡数据，并对人形机器人进行编程，可以确保机器人的动作精度和准确性
2.反馈与调整：将实时跟踪得到的机器人运动数据与预设的运动轨迹或目标动作进行对比，发现偏差后及时反馈给机器人的控制系统。2.路径规划：基于OptiTrack提供的环境信息和机器人的当前位置、目标位置等
阅读更多2024-09-20
Vue2+vue-office/excel 实现在线加载Excel文件预览
Vue2+vue-office/excel 实现在线加载Excel文件预览
阅读更多2024-09-20
第十一章【后端】商品分类管理微服务（11.5）——增强响应
这样，理论上已经实现了我们所想要的统一后端响应格式了，但是我们每写一个接口都要调用。结构，造成不一致，因此我们需要将响应格式统一起来，定义一个统一的标准响应格式。在前后端分离的开发模式下，我们一般会统
阅读更多2024-09-20
大文件编辑器(QT)
大文件编辑器， QSciscintilla, QsciLexerCPP
阅读更多2024-09-20
服务监控插件全览：提升微服务可观测性的利器
通过以上介绍，我们可以看到 New Relic 是一个功能全面、性能优异的监控工具，适用于各种分布式系统的监控需求。通过以上介绍，我们可以看到 Wavefront 是一个功能全面、性能优异的监控工具，
阅读更多2024-09-20

【数据结构】AVL树(平衡二叉搜索树)

文章目录

1.AVL树

1.1 AVL树的概念

1.2 AVL树节点的定义

1.3 AVL树的插入

1.4 AVL树的旋转

1.4.1 左单旋

1.4.2 右单旋

1.4.3 右左双旋

1.4.4 左右双旋

1.5 AVL树的平衡验证

1.6 AVL树的删除

1.7 AVL树的性能

相关文章