AVL树如何维持平衡

1.AVL树的特性

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

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

-它的左右子树都是AVL树

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

用右子树减左子树高度表示左右子树高度之差（平衡因子），下图用蓝色表示节点的平衡因子，如图为一棵AVL树

 因为要控制平衡因子，AVL树节点相比于普通二叉树节点增加了：平衡因子、父节点指针（便于找到父节点控制平衡因子），模拟AVL树节点的定义如下

template<class T>
struct AVLTreeNode
{AVLTreeNode(const T& val): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _val(val), _bf(0){}AVLTreeNode<T>* _pLeft;// 该节点的左孩子AVLTreeNode<T>* _pRight; // 该节点的右孩子AVLTreeNode<T>* _pParent; // 该节点的双亲T _val; // 该节点储存的数据  int _bf; // 该节点的平衡因子
};

 

2.AVL插入时如何维持平衡

AVL树插入时首先要遵循二叉搜索树的规则，找到对应插入位置，注意节点_pParent的链接

2.1找到插入位置插入并链接 

Node* newnode = new Node(x);
Node* cur = _root;
Node* parent = nullptr;if (_root == nullptr)
{_root = newnode;return true;
}
//使用cur找到插入位置
while (cur)
{if (cur->_val == x){return false;}else if (cur->_val < x){parent = cur;cur = cur->_pRight;}else if (cur->_val > x){parent = cur;cur = cur->_pLeft;}
}//链接节点
if (x < parent->_val)
{parent->_pLeft = newnode;
}
else
{parent->_pRight = newnode;
}
newnode->_pParent = parent;
cur = newnode;

 在插入前，这棵树就是一块AVL树遵循AVL树的规则，在插入后可能会破坏规则，就要继续向祖先更新、查看平衡因子。

2.2更新平衡因子

在插入后parent节点平衡因子存在3种情况，有的情况发现此子树的高度不变就不必向上继续更新

若parent的平衡因子，用一个循环实现向上更新

更新后平衡因子存在以下几种情况

1.平衡因子 == 0

说明parent插入前不平衡，插入在短的那边，插入后平衡了，插入后高度不变不需要往上更新

2.平衡因子 == 1或-1

说明parent插入前平衡，插入后不左右子树高度差改变的，那parent所在树高度更新，需继续往上更新

3.parent的平衡因子 == 2或-2

说明parent插入前平衡因子 == 1 或 -1，插入在长的那边了，加剧了parent的不平衡，此时已经违反规则，需要旋转处理调整

while (parent)
{//使用循环向上更新//更新平衡因子if (cur == parent->_pLeft){parent->_bf--;}else if (cur == parent->_pRight){parent->_bf++;}//继续向上更新//若已经更新到根，停止if (parent == nullptr){break;}//1.若此时parent已经平衡(==0)，说明插入节点使子树平衡，并没有增加子树高度，不用往上更新if (parent->_bf == 0){break;}//2.若此时parent为弱平衡(_bf == -1/1),说明插入节点使原本平衡的树高度更新，需继续往上更新else if (parent->_bf == -1 || parent->_bf == 1){}//3.若此时parent已经失衡(_bf == -2/2),说明插入节点使原本弱平衡的树加剧失衡，需要旋转处理、调整else if (parent->_bf == -2 || parent->_bf == 2){//单独的一边高（subLL、subRR高），单旋if (parent->_bf == -2 && parent->_pLeft->_bf == -1){RotatoR(parent);}else if (parent->_bf == 2 && parent->_pRight->_bf == 1){RotatoL(parent);}//subRL、subLR高，双旋。例：先将subR子树旋转为subRR高的情况，再使用单次左旋else if (parent->_bf == -2 && parent->_pLeft->_bf == 1){RotatoLR(parent); }else if (parent->_bf == 2 && parent->_pRight->_bf == -1){RotatoRL(parent);}//旋转后这棵子树高度并没有增加，不向上继续更新break;}else{assert(false);}//迭代，继续向上更新cur = parent;parent = parent->_pParent;}

旋转最后得到的结果：

1.遵循搜索树的规则

2.控制平衡，降低高度

而旋转时分为以下几种情况

2.3旋转调整

2.1.1.subRR/subLL长的时候树的旋转调整

如图，若插入在subRR处，parent节点的平衡因子违反了规则，需要调整此子树使之符合规则。

若插入在subLL处，与插入在subRR处类似

下图中a、b、c为抽象的树，h为抽象的树的高度，h = 0时表示空

思想：将parent及其左子树链接到subR的左边使parent子树高度与subRL一样高

具体操作为将parent链接到subR的左边，将subRL链接到parent的右边

代码实现如下，记得要更新平衡因子

	//单次左旋，适用于subRR长的情况//思想：将原来根放到subR的左边使parent子树高度与subRL一样高void RotatoL(Node* parent){Node* subR = parent->_pRight;Node* subRL = subR->_pLeft;Node* parentParent = parent->_pParent;//先链接节点if (subRL != nullptr)subRL->_pParent = parent;parent->_pRight = subRL;parent->_pParent = subR;subR->_pLeft = parent;subR->_pParent = parentParent;if (parentParent == nullptr){//若parentParent为空则原Parent为整个树的根_root = subR;}else{if (subR->_val < parentParent->_val){parentParent->_pLeft = subR;}else if (subR->_val > parentParent->_val){parentParent->_pRight = subR;}}//再更新平衡因子parent->_bf = subR->_bf = 0;}

 

2.1.2.subRL/subLR长的时候的调整

如图，插入节点后subRL长，此时无法像上面那样使用左旋使subRR与subRL链接到parent右边树一样高

若插入在subLR处，调整方法类似

图1.subRL长时的插入

这时我们可以想办法旋转使subRR变长，我们将subRL再具体细分，h为抽象树的高度，h == 0 时表示40为新插入节点

这时我们可以先调整 subR为根的子树使用一次旋转使得subR所在子树较长，变为subRR长的情况可以单次旋转调整，最后再单次右旋

整体旋转方法如下图

记得更新平衡因子，若初始为b长，parent最后平衡因子为0，subR最后平衡因子为1；若初始为c长parent最后平衡因子为-1，subR最后平衡因子为0；若subRL为新插入节点，则h == 0则a、b、c、d都为空，parent和subR最后平衡因子都为0

 代码如下

//先右旋再左旋，适用于subRL高的情况
//思想：先将subR子树旋转为subRR高的情况，再使用单次左旋
void RotatoRL(Node* parent)
{Node* subR = parent->_pRight;Node* subRL = subR->_pLeft;//可能subRLL长或subRLR长，通过记录subRL原来的bf调整最后bfint bf = subRL->_bf;//两次旋转，旋转后平衡因子有误RotatoR(subR);RotatoL(parent);//再更新平衡因子subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;parent->_bf = 0;}else{subR->_bf = 0;parent->_bf = 0;}
}

3.插入的整体代码

 

bool Insert(T& x)
{Node* newnode = new Node(x);Node* cur = _root;Node* parent = nullptr;if (_root == nullptr){_root = newnode;return true;}//使用cur找到插入位置while (cur){if (cur->_val == x){return false;}else if (cur->_val < x){parent = cur;cur = cur->_pRight;}else if (cur->_val > x){parent = cur;cur = cur->_pLeft;}}//链接节点if (x < parent->_val){parent->_pLeft = newnode;}else{parent->_pRight = newnode;}newnode->_pParent = parent;cur = newnode;while (parent){//使用循环向上更新//更新平衡因子if (cur == parent->_pLeft){parent->_bf--;}else if (cur == parent->_pRight){parent->_bf++;}//继续向上更新//若已经更新到根，停止if (parent == nullptr){break;}//1.若此时parent已经平衡(==0)，说明插入节点使子树平衡，并没有增加子树高度，不用往上更新if (parent->_bf == 0){break;}//2.若此时parent为弱平衡(_bf == -1/1),说明插入节点使原本平衡的树高度更新，需继续往上更新else if (parent->_bf == -1 || parent->_bf == 1){}//3.若此时parent已经失衡(_bf == -2/2),说明插入节点使原本弱平衡的树加剧失衡，需要旋转处理、调整else if (parent->_bf == -2 || parent->_bf == 2){//单独的一边高（subLL、subRR高），单旋if (parent->_bf == -2 && parent->_pLeft->_bf == -1){RotatoR(parent);}else if (parent->_bf == 2 && parent->_pRight->_bf == 1){RotatoL(parent);}//subRL、subLR高，双旋。例：先将subR子树旋转为subRR高的情况，再使用单次左旋else if (parent->_bf == -2 && parent->_pLeft->_bf == 1){RotatoLR(parent); }else if (parent->_bf == 2 && parent->_pRight->_bf == -1){RotatoRL(parent);}//旋转后这棵子树高度并没有增加，不向上继续更新break;}else{assert(false);}//迭代，继续向上更新cur = parent;parent = parent->_pParent;}return true;
}//单次左旋，适用于subRR长的情况
//思想：将原来根放到subR的左边使parent子树高度与subRL一样高
void RotatoL(Node* parent)
{Node* subR = parent->_pRight;Node* subRL = subR->_pLeft;Node* parentParent = parent->_pParent;//先链接节点if (subRL != nullptr)subRL->_pParent = parent;parent->_pRight = subRL;parent->_pParent = subR;subR->_pLeft = parent;subR->_pParent = parentParent;if (parentParent == nullptr){//若parentParent为空则原Parent为整个树的根_root = subR;}else{if (subR->_val < parentParent->_val){parentParent->_pLeft = subR;}else if (subR->_val > parentParent->_val){parentParent->_pRight = subR;}}//再更新平衡因子parent->_bf = subR->_bf = 0;}//单次右旋，与左旋思想类似
void RotatoR(Node* parent)
{Node* subL = parent->_pLeft;Node* subLR = subL->_pRight;Node* parentParent = parent->_pParent;if (subLR != nullptr)subLR->_pParent = parent;parent->_pLeft = subLR;parent->_pParent = subL;subL->_pRight = parent;subL->_pParent = parentParent;if (parentParent == nullptr){_root = subL;}else{if (parent == parentParent->_pLeft){parentParent->_pLeft = subL;}else if (parent == parentParent->_pRight){parentParent->_pRight = subL;}}//再更新平衡因子parent->_bf = subL->_bf = 0;
}//先右旋再左旋，适用于subRL高的情况
//思想：先将subR子树旋转为subRR高的情况，再使用单次左旋
void RotatoRL(Node* parent)
{Node* subR = parent->_pRight;Node* subRL = subR->_pLeft;//可能subRLL长或subRLR长，通过记录subRL原来的bf调整最后bfint bf = subRL->_bf;//两次旋转，旋转后平衡因子有误RotatoR(subR);RotatoL(parent);//再更新平衡因子subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;parent->_bf = 0;}else{subR->_bf = 0;parent->_bf = 0;}
}//先左旋再右旋
void RotatoLR(Node* parent)
{Node* subL = parent->_pLeft;Node* subLR = subL->_pRight;int bf = subLR->_bf;//两次旋转，旋转后平衡因子有误RotatoL(subL);RotatoR(parent);//再更新平衡因子subLR->_bf = 0;if (bf == 1){subL->_bf = -1;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;parent->_bf = 1;}else{subL->_bf = 0;parent->_bf = 0;}
}

 在实现后可以中序遍历整棵树，检查是否为二叉搜索树。并且检查其平衡因子是否符合规则，确定其为平衡树。

//获取高度
int Height()
{return _Height(_root);
}
//判断是否为平衡树
bool IsBalanceTree()
{return _IsBalanceTree(_root);
}//判断是否为平衡树
bool _IsBalanceTree(Node* root)
{// 空树也是AVL树if (root == nullptr){return true;}int leftTreeHeight = _Height(root->_pLeft);int rightTreeHeight = _Height(root->_pRight);int diff = rightTreeHeight - leftTreeHeight;//验证root是不是平衡树if (root->_bf == diff && diff >= -1 && diff <= 1){//验证其左右子树是不是平衡树return _IsBalanceTree(root->_pLeft) && _IsBalanceTree(root->_pRight);}else{return false;}}	//获取高度
int _Height(Node* root)
{if (root == nullptr){return 0;}int leftTreeHeight = _Height(root->_pLeft);int rightTreeHeight = _Height(root->_pRight);return (leftTreeHeight > rightTreeHeight) ? leftTreeHeight + 1 : rightTreeHeight + 1;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/444110.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【万字长文】Word2Vec计算详解（一）CBOW模型

【万字长文】Word2Vec计算详解（一）CBOW模型

【万字长文】Word2Vec计算详解&#xff08;一&#xff09;CBOW模型 写在前面 本文用于记录本人学习NLP过程中&#xff0c;学习Word2Vec部分时的详细过程&#xff0c;本文与本人写的其他文章一样&#xff0c;旨在给出Word2Vec模型中的详细计算过程&#xff0c;包括每个模块的计…
阅读更多...
【redis-06】redis的stream流实现消息中间件

【redis-06】redis的stream流实现消息中间件

redis系列整体栏目 内容链接地址【一】redis基本数据类型和使用场景https://zhenghuisheng.blog.csdn.net/article/details/142406325【二】redis的持久化机制和原理https://zhenghuisheng.blog.csdn.net/article/details/142441756【三】redis缓存穿透、缓存击穿、缓存雪崩htt…
阅读更多...
Auto-Animate：是一款零配置、即插即用的动画工具，可以为您的 Web 应用添加流畅的过渡效果

Auto-Animate：是一款零配置、即插即用的动画工具，可以为您的 Web 应用添加流畅的过渡效果

嗨&#xff0c;大家好&#xff0c;我是小华同学&#xff0c;关注我们获得“最新、最全、最优质”开源项目和高效工作学习方法 用户体验成为了检验产品成功与否的关键因素。而动画效果&#xff0c;作为提升用户体验的重要手段&#xff0c;在网页和应用开发中扮演着举足轻重的角色…
阅读更多...
同望OA tooneAssistantAttachement.jsp 任意文件读取漏洞复现

同望OA tooneAssistantAttachement.jsp 任意文件读取漏洞复现

0x01 产品简介 同望OA，即同望科技打造的智企云协同管理系统，是一款高效的企业协同移动办公系统。秉承“互联网++企业管理”理念，定位于以移动互联办公为基础的企业协同管理软件平台。它旨在通过内置常用标准模块与专项管理模块应用，安全快速地打通管理与业务通道，实现管理…
阅读更多...
QT 实现QMessageBox::about()信息自定义显示

QT 实现QMessageBox::about()信息自定义显示

这是我记录Qt学习过程的第四篇心得文章&#xff0c;主要是方便自己编写的应用程序显示“关于信息”&#xff0c;对QMessageBox::about()输入信息进行规范&#xff0c;可以设置应用程序名称&#xff0c;通过定义宏从pro文件获取应用程序版本号&#xff0c;以及编译程序的QT版本、…
阅读更多...
写一个代码：打印100~200之间的素数

写一个代码：打印100~200之间的素数

我们要输出100-200之间的素数&#xff0c;首先我们先得输出100-200之间的数字&#xff0c;一般用于遍历循环的数字要用到for循环&#xff0c;同时在输出的100~200之间的数字进行判断是不是素数&#xff0c;我们知道素数的判断条件在于当一个数字从1开始到自己本身的时候&#x…
阅读更多...
2024年最新（AI绘画）Stable Diffusion4.9下载及安装教程.

2024年最新（AI绘画）Stable Diffusion4.9下载及安装教程.

软件介绍 Stable Diffusion 是一款在图像生成领域具有重大影响力的软件。 从工作原理上看&#xff0c;它利用深度学习的先进算法&#xff0c;构建起复杂且强大的神经网络架构。其核心在于能够解读用户输入的文本信息&#xff0c;并将这些信息转化为图像的特征与细节。 在使用…
阅读更多...
【C++网络编程】（一）Linux平台下TCP客户/服务端程序

【C++网络编程】（一）Linux平台下TCP客户/服务端程序

文章目录 Linux平台下TCP客户/服务端程序服务端客户端相关头文件介绍 Linux平台下TCP客户/服务端程序 图片来源&#xff1a;https://subingwen.cn/linux/socket/ 下面实现一个Linux平台下TCP客户/服务端程序&#xff1a;客户端向服务器发送&#xff1a;“你好&#xff0c;服务…
阅读更多...
攻防世界(CTF)~Reverse-easyRE1

攻防世界(CTF)~Reverse-easyRE1

题目介绍 下载附件后一个32位一个64位 64位的放到ExeinfoPE查看一下有无壳子&#xff08;无壳&#xff09; 放IDA看一下伪代码&#xff0c;习惯性看一下main函数&#xff0c;直接发现了flag flag{db2f62a36a018bce28e46d976e3f9864}
阅读更多...
手撕数据结构 —— 单链表（C语言讲解）

手撕数据结构 —— 单链表（C语言讲解）

目录 1.为什么要有链表 2.什么是链表 3.链表的分类 4.无头单向非循环链表的实现 SList.h中接口总览 具体实现 链表节点的定义 打印链表 申请结点 尾插 头插 尾删 头删 查找 在pos位置之前插入 在pos位置之后插入 删除pos位置 删除pos位置之后的值 5.完整代码…
阅读更多...
理解Web3的互操作性：不同区块链的连接

理解Web3的互操作性：不同区块链的连接

随着Web3的迅速发展&#xff0c;互操作性成为区块链技术中的一个核心概念。互操作性指的是不同区块链之间能够无缝地交流和共享数据&#xff0c;从而实现更加高效和灵活的生态系统。本文将探讨Web3中互操作性的意义、面临的挑战以及未来的发展趋势。 1. 互操作性的意义 在Web…
阅读更多...
如何用深度神经网络预测潜在消费者

如何用深度神经网络预测潜在消费者

1. 模型架构 本项目采用的是DeepFM模型&#xff0c;其结构结合了FM&#xff08;因子分解机&#xff09;与深度神经网络&#xff08;DNN&#xff09;&#xff0c;实现了低阶与高阶特征交互的有效建模。模型分为以下几层&#xff1a; 1.1 FM部分&#xff08;因子分解机层&#…
阅读更多...
MinIO分片上传超大文件（纯服务端）

MinIO分片上传超大文件（纯服务端）

目录 一、MinIO快速搭建1.1、拉取docker镜像1.2、启动docker容器 二、分片上传大文件到MinIO2.1、添加依赖2.2、实现MinioClient2.3、实现分片上传2.3.0、初始化MinioClient2.3.1、准备分片上传2.3.2、分片并上传2.3.2.1、设置分片大小2.3.2.2、分片 2.3.3、分片合并 三、测试3…
阅读更多...
Vscode+Pycharm+Vue.js+WEUI+django火锅(三）理解Vue

Vscode+Pycharm+Vue.js+WEUI+django火锅(三）理解Vue

新创建的Vue项目里面很多文件&#xff0c;对于新手&#xff0c;老老实实做一下了解。 1.框架逻辑 框架的逻辑都是相通的&#xff0c;花点时间理一下就清晰了。 2.文件目录及文件 创建好的vue项目下&#xff0c;主要的文件和文件夹要先认识一下&#xff0c;并与框架逻辑对应起…
阅读更多...
计算机网络803-（4）网络层

计算机网络803-（4）网络层

目录 1.虚电路服务 虚电路是逻辑连接 2.数据报服务 3.虚电路服务与数据报服务的对比 二.虚拟互连网络-IP网 1.网络通信问题 2.中间设备 3.网络互连使用路由器 三.分类的 IP 地址 1. IP 地址及其表示方法 2.IP 地址的编址方法 3.分类 IP 地址 &#xff08;1&#x…
阅读更多...
使用 Go 和 Gin 框架构建简单的用户和物品管理 Web 服务

使用 Go 和 Gin 框架构建简单的用户和物品管理 Web 服务

使用 Go 和 Gin 框架构建简单的用户和物品管理 Web 服务 在本项目中&#xff0c;我们使用 Go 语言和 Gin 框架构建了一个简单的 Web 服务&#xff0c;能够管理用户和物品的信息。该服务实现了两个主要接口&#xff1a;根据用户 ID 获取用户名称&#xff0c;以及根据物品 ID 获…
阅读更多...
蓝桥杯【物联网】零基础到国奖之路:十七. 扩展模块之单路ADC和NE555

蓝桥杯【物联网】零基础到国奖之路:十七. 扩展模块之单路ADC和NE555

蓝桥杯【物联网】零基础到国奖之路:十七. 扩展模块之单路ADC和NE555 第一节 硬件解读第二节 CubeMx配置第三节 代码1&#xff0c;脉冲部分代码2&#xff0c;ADC部分代码![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/57531a4ee76d46daa227ae0a52993191.png) 第一节 …
阅读更多...
EasyExcel读入数字类型数据时出现小数位丢失精度问题

EasyExcel读入数字类型数据时出现小数位丢失精度问题

这里写自定义目录标题 问题现象解决方案 问题现象 目前使用easyExcel读取导入文档时发现文档中的小数值4076204076.65会被读取为4076204076.6500001 尝试去查看了excel解压后的文件&#xff0c;发现这条数据在xml里存储的值就是4076204076.6500001&#xff0c;即是excel存储小…
阅读更多...
利用 Python 爬虫采集 1688商品详情

利用 Python 爬虫采集 1688商品详情

1688是中国的一个大型B2B电子商务平台&#xff0c;主要用于批发和采购各种商品。对于需要从1688上获取商品详情数据、工程数据或店铺数据的用户来说&#xff0c;可以采用以下几种常见的方法&#xff1a; 官方API接口&#xff1a;如果1688提供了官方的API接口&#xff0c;那么可…
阅读更多...
喜讯！迈威通信TSN产品通过“时间敏感网络（TSN）产业链名录计划”评测，各项指标名列前茅

喜讯！迈威通信TSN产品通过“时间敏感网络（TSN）产业链名录计划”评测，各项指标名列前茅

TSN技术&#xff0c;作为推动企业网络化与智能化转型的关键力量&#xff0c;已成为工业网络迈向下一代演进的共识方向&#xff0c;正加速重构工业网络的技术架构与产业生态。为响应这一趋势&#xff0c;工业互联网产业联盟携手中国信息通信研究院及50余家产学研用单位&#xff…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023