【1++的数据结构】之AVL树

👍作者主页：进击的1++
🤩 专栏链接：【1++的数据结构】

文章目录

  • 一，什么是AVL树
  • 二，AVL树的插入
  • 三，AVL树的旋转
    • 3.1 向左旋转
    • 3.2 向右旋转
    • 3.3 左右双旋
    • 3.4 右左双旋
  • 四，验证AVL树是否平衡

一，什么是AVL树

在说AVL树之前我们先来说说为什么会出现AVL树。在前面的文章中我们讲过二叉搜索树，虽然查找，插入效率比较高，但其有个缺陷：在某些情况下其可能会成为一颗单支树或其他高度较高的树，这时我们的效率就比较低了，甚至接近于O(n）。在此背景下，有两位俄罗斯数学家，便发明了AVL树----当插入新的结点后，保证每个结点的左右子树的高度差不大于1。则这颗树就会接近满二叉树，其高度就会降低，那么查找，插入效率也会提高。
在这里插入图片描述

二，AVL树的插入

在说AVL树的插入之前我们先来了解其结点。与二叉搜索树不同，其是三叉链结构和平衡因子，不但有左右指针，还有指向双亲结点的指针。这么设计的好处在于后面更新平衡因子是会比较方便。
我们来看结点结构代码：

template<class K, class V>struct AVLTreeNode{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf;//平衡因子AVLTreeNode(const std::pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}};

了解了结点的结构后，我们就可以进行插入操作的学习。
与二叉搜索树一样，其先要找到要插入的位置，代码如下;

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;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->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;

与以前不同的是，由于是三叉链结构，因此当找到位置后，我们还要与其双亲结点进行链接。
当找到合适的位置进行插入后，便要进行控制平衡，使每个结点的左右子树高度差不超过1。

每个根节点的平衡因子的计算过程为;若插入的结点在其左侧，则根节点的平衡因子-1；若在右侧，则平衡因子+1。
根据平衡因子，我们总结出了三种控制平衡的规律:

  1. 若插入后根节点的平衡因子变为0，则说明在插入前其平衡因子为正负1，插入后被调整为0，满足AVL树的性质，则不做任何操作。
  2. 若插入后根节点的平衡因子变为正负1，则说明在插入前其平衡因子为0，插入后被改变，则向上继续更新，直到根节点。
  3. 若插入后平衡因子变为正负2，则违反了AVL树平衡的性质，需要进行旋转处理。

旋转操作，我们会在后面进行说明。

以下是控制其平衡的代码:

while (parent){if (cur == parent->_right){parent->_bf++;}else{parent->_bf--;}if (parent->_bf == 0){break;}else if (abs(parent->_bf) == 1){parent = parent->_parent;cur = cur->_parent;}else if (abs(parent->_bf) == 2){//左单旋if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}break;}else{assert(false);}}}

三，AVL树的旋转

3.1 向左旋转

以下是向左 旋转的代码：

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

那么在什么情况下才会进行向左旋转呢？
在这里插入图片描述

在这里插入图片描述

如图，当我们的新插入的结点在较高子数的右侧时，此时30这个结点的平衡因子变为了2，满足了旋转的条件（图中h可为任何正整数或0）我们可以从图中清楚的看到，当插入新节点后平衡因子为2的结点的右子数明显高，为了平衡，我们则需要给其右子树将高度，我们将30称为parent,60称为SubR;60的左子树b称为SubRL。从图中我们看到，SubR成为了这颗树或者说是子树的新结点。而SubRL成为了parent的右子树。改变后仍遵循二叉搜索树的规则。此时，我们的左旋转就完成了。旋转后，平衡因子也发生了改变，所以要对平衡因子进行更新。对parent和SubR的平衡因子进行更新，更新后都变为0。

3.2 向右旋转

向右旋转与向左旋转相似
代码如下：

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

向右旋转的情况如下图:
在这里插入图片描述
当新插入的结点在较高左子树的左侧时，进行右旋转。
如图，我们可以看出其左子树高，我们仍将60称为parent,将30称为SubL,将30的右子树称为SubLR。旋转时，将SubL作为了根节点，SubLR给了parent的左侧。旋转完成后要进行平衡因子的更新，parent与SubL都更新为0。

3.3 左右双旋

代码如下：

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

当新结点插入较高左子树的右侧时，则会进行左右双旋，就是先向左旋转，再向右旋转。
在这里插入图片描述
先以30为parent进行左旋转，再以90为parent进行右旋转。
左右旋转我们在上面已经进行了讲述，接下来，我们的重点是平衡 因此的更新，在上图这种情况下，新插入的结点可以为60的左子树，也可以为右子树，或者60本身就为新插入的结点。
因此在不能的情况下，平衡因子的更新也不同。
主要有以下情况：
（SubL为30，parent为90）

			Node* SubL= parent->_left;Node* SubLR = SubL->_right;int bf = SubLR->_bf;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;}

3.4 右左双旋

代码如下:

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){parent->_bf = -1;SubR->_bf = 0;}else if (bf == -1){parent->_bf = 0;SubR->_bf = 1;}else if (bf == 0){parent->_bf = 0;SubR->_bf = 0;}else{assert(false);}}

当新结点插入在较高右子树的左侧时，进行右左双旋（先向右旋转，在向左旋转）。
在这里插入图片描述
与左右双旋相似，其平衡因子的更新也有几种情况:

SubRL->_bf = 0;if (bf == 1){parent->_bf = -1;SubR->_bf = 0;}else if (bf == -1){parent->_bf = 0;SubR->_bf = 1;}else if (bf == 0){parent->_bf = 0;SubR->_bf = 0;}else{assert(false);}

四，验证AVL树是否平衡

AVL树最重要的一个性质就是其每个结点的左右子树之差的绝对值小于2。
并且等于该结点的平衡因子的绝对值。
我们以此来测试我们所写的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 leftHT = Height(root->_left);int rightHT = Height(root->_right);int diff = rightHT - leftHT;if (diff != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return abs(diff) < 2 && _Isbalance(root->_left)&& _Isbalance(root->_right);}

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

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

相关文章

Data truncation: Out of range value for column ‘id‘ at row 1

Data truncation: Out of range value for column ‘id‘ at row 1

错误信息&#xff1a;Data truncation: Out of range value for column id at row 1 数据截断&#xff1a;第1行“id”列的值超出范围 很多人会回复&#xff1a;数据库 类型由int改为 bigInt 我看了表结构 可以放的下的。 是 bigint(20) 没有问题啊。 默认的 bigint 类型…
阅读更多...
C语言面试题值反转字符串

C语言面试题值反转字符串

知识捡漏本 1.C语言优先级 &#xff1a;左高于高于 右 2.定义宏函数product&#xff0c;调用product后&#xff0c;里面的i和i都是加两次1&#xff0c;i就是两个加2后的i相乘&#xff0c;i是开始的i和1后的i相乘。 3.用i (j4,k 8,m 16);这种定义方法&#xff0c;最终i和最后一…
阅读更多...
dji uav建图导航系列（）ROS中创建dji_sdk节点包（一）项目结构

dji uav建图导航系列（）ROS中创建dji_sdk节点包（一）项目结构

文章目录 1、整体项目结构1.1、 目录launch1.2、文件CMakeLists.txt1.3、文件package.xml1.4、目录include1.4、目录srv在ROS框架下创建一个无人机的节点dji_sdk，实现必需的订阅（控制指令）、发布（无人机里程计）、服务（无人机起飞降落、控制权得很）功能，就能实现一个类似…
阅读更多...
全球免费编程教育网站：Code.org

全球免费编程教育网站：Code.org

全球免费编程教育网站&#xff1a;Code.org 官网地址注册使用 你还在为小朋友的编程教育而发愁吗&#xff1f; 你还在为小朋友放假无聊而头疼吗&#xff1f; 他来了他来了&#xff0c;全球免费编程教育网站来了。 2013年成立的Code.org是一个非营利组织。 它致力于为年轻女子、…
阅读更多...
【RISC-V】RISC-V寄存器

【RISC-V】RISC-V寄存器

一、通用寄存器 32位RISC-V体系结构提供32个32位的整型通用寄存器寄存器别名全称说明X0zero零寄存器可做源寄存器(rs)或目标寄存器(rd)X1ra链接寄存器保存函数返回地址X2sp栈指针寄存器指向栈的地址X3gp全局寄存器用于链接器松弛优化X4tp线程寄存器常用于在OS中保存指向进程控…
阅读更多...
Qt/C++编写视频监控系统81-Onvif报警抓图和录像并回放

Qt/C++编写视频监控系统81-Onvif报警抓图和录像并回放

一、前言 视频监控系统中的图文警情模块&#xff0c;是通过Onvif协议的事件订阅拿到的&#xff0c;通过事件订阅后&#xff0c;设备的各种报警事件比如入侵报警/遮挡报警/越界报警/开关量报警等&#xff0c;触发后都会主动往订阅者发送&#xff0c;而且一般都是会发送两次&…
阅读更多...
Node.js crypto模块 加密算法

Node.js crypto模块 加密算法

背景 微信小程序调用飞蛾热敏纸打印机&#xff0c;需要进行参数sig签名校验&#xff0c;使用的是sha1进行加密 // 通过crypto.createHash()函数&#xff0c;创建一个hash实例&#xff0c;但是需要调用md5&#xff0c;sha1&#xff0c;sha256&#xff0c;sha512算法来实现实例的…
阅读更多...
企业架构LNMP学习笔记7

企业架构LNMP学习笔记7

PHP介绍&#xff1a; HTML&#xff1a;超文本标记语言 http: 超文本传输协议 端口80 浏览器将html代码解析成web页面。 PHP&#xff1a;超文本预处理器。后端语言开发&#xff0c;页面上需要动态改变修改的&#xff0c;需要连接数据库查询数据&#xff0c;转为html。 主要…
阅读更多...
流媒体弱网优化之路(BBR应用)——GCC与BBR的算法思想分析

流媒体弱网优化之路(BBR应用)——GCC与BBR的算法思想分析

流媒体弱网优化之路(WebRTC)——GCC与BBR的算法思想分析 —— 我正在的github给大家开发一个用于做实验的项目 —— github.com/qw225967/Bifrost目标&#xff1a;可以让大家熟悉各类Qos能力、带宽估计能力&#xff0c;提供每个环节关键参数调节接口并实现一个json全配置&…
阅读更多...
WebSocket（一）

WebSocket（一）

一.什么是WebSocket 【1】WebSocket是一种协议&#xff0c;设计用于提供低延迟&#xff0c;全双工和长期运行的连接。 全双工&#xff1a;通信的两个参与方可以同时发送和接收数据&#xff0c;不需要等待对方的响应或传输完成。 【2】比较 传统通信&#xff08;http协议&am…
阅读更多...
Docker 的快速使用

Docker 的快速使用

ubuntu安装 centos安装 安装完毕之后执行一下这条命令&#xff0c;可以避免每次使用docker命令都需要sudo权限 sudo usermod -aG docker $USER阿里云docker镜像加速 DockerHub 遇到不懂或者不会使用的命令可以使用docker --help查看文档 docker --help 如&#xff1a; dock…
阅读更多...
JavaWeb 文件上传和下载

JavaWeb 文件上传和下载

目录 一、文件上传 1.文件上传和下载的使用说明 : 2.文件上传基本原理 : 3.文件上传经典案例 : 3.1 页面实现: 3.2 servlet实现 : 3.3 工具类实现 : 3.4 运行测试 : 3.5 注意事项 : 二、文件下载 1.文件下载基本原理 : 2.文件下载经典案例 : 2.1 准备工作 2.2 页面…
阅读更多...
关于C语言参数传递的

关于C语言参数传递的

一、C语言参数传递是整体带入 #include <stdio.h> #define DF(a,b) (a2*b) int main() { int s5; int k DF((s1),(s-3)); printf("%d",k); }输出结果 原因&#xff1a; #define DF(a,b) (a2*b) int k DF((s1),(s-3)); //等效 int k DF((s1)2 * (s-3)); …
阅读更多...
useEffect 不可忽视的 cleanup 函数

useEffect 不可忽视的 cleanup 函数

在 react 开发中&#xff0c; useEffect 是我们经常会使用到的钩子&#xff0c;一个基础的例子如下&#xff1a; useEffect(() > {// some code here// cleanup 函数return () > {doSomething()} }, [dependencies])上述代码中&#xff0c; cleanup 函数的执行时机有如下…
阅读更多...
代码随想录笔记--栈与队列篇

代码随想录笔记--栈与队列篇

目录 1--用栈实现队列 2--用队列实现栈 3--有效的括号 4--删除字符串中的所有相邻重复项 5--逆波兰表达式求值 6--滑动窗口的最大值 7--前k个高频元素 1--用栈实现队列 利用两个栈&#xff0c;一个是输入栈&#xff0c;另一个是输出栈&#xff1b; #include <iostrea…
阅读更多...
Windows 重新映射 CapsLock 大写锁定到 Ctrl

Windows 重新映射 CapsLock 大写锁定到 Ctrl

Windows 重新映射 CapsLock 大写锁定到 Ctrl 本要点中的这些方法适用于我的美国键盘布局。我不确定其他布局。如果出现问题&#xff0c;请恢复您的更改&#xff1b;删除您创建的注册表项&#xff08;并重新启动&#xff09;。 强烈推荐 方法5 ctrl2cap&#xff0c;因为不会影…
阅读更多...
Modbus通信协议

Modbus通信协议

Modbus通信协议 一、概述 Modbus通信协议是一种工业现场总线协议标准&#xff0c;常用的Modbus协议有以下三种类型&#xff1a;Modbus TCP、Modbus RTU、Modbus ASCll。 Modbus通信协议解决了通过串行线路在电子设备之间发送信息的问题。该协议在遵循该协议的体系结构中实现主…
阅读更多...
Elasticsearch 7.6 - API高阶操作篇

Elasticsearch 7.6 - API高阶操作篇

ES 7.6 - API高阶操作篇 分片和副本索引别名添加别名查询所有别名删除别名使用别名代替索引操作代替插入代替查询 场景实操 滚动索引索引模板创建索引模板查看模板删除模板 场景实操一把索引的生命周期数据迁移APIGEO(地理)API索引准备矩形查询圆形查询多边形查询 自定义分词器…
阅读更多...
小白学Go基础01-Go 语言的介绍

小白学Go基础01-Go 语言的介绍

Go 语言对传统的面向对象开发进行了重新思考&#xff0c;并且提供了更高效的复用代码的手段。Go 语言还让用户能更高效地利用昂贵服务器上的所有核心&#xff0c;而且它编译大型项目的速度也很快。 用 Go 解决现代编程难题 Go 语言开发团队花了很长时间来解决当今软件开发人员…
阅读更多...
ThinkPHP 文件上传 fileSystem 扩展的使用

ThinkPHP 文件上传 fileSystem 扩展的使用

ThinkPHP 文件上传 ThinkPHP 文件上传 扩展 filesystem一、安装 FileSystem 扩展二、认识 filesystem 配置文件 config/filesystem.php三、上传验证&#xff08;涉及到验证器的知识点&#xff09;四、文件上传demo ThinkPHP 文件上传 扩展 filesystem ThinkPHP 为我们 提供了 …
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023