【C++干货铺】会旋转的二叉树——AVLTree

=========================================================================

个人主页点击直达：小白不是程序媛

C++系列专栏：C++干货铺

代码仓库：Gitee

=========================================================================

目录

前言

AVL树

AVL树的概念

AVL树结点的定义

AVL树的插入

寻找插入结点的位置

修改平衡因子

 AVL树的旋转

右单旋

左单旋

先右旋再左旋 

先左旋再右旋

 AVL树的验证

AVL树的删除（了解）

AVL树的性能

前言

前面对map/multimap/set/multiset进行了简单的介绍，在其文档介绍中发现，这几个容器有个
共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中
插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此
map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

AVL树

AVL树的概念

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

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

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

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 pair<k, v>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};

AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么
AVL树的插入过程可以分为三步： 

1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子                                                                                                              3. 将插入后不符合的子树进行旋转调整

寻找插入结点的位置

AVL树是基于搜索二叉树的，搜索二叉树的原则是左小右大。根据这个规则可以找到插入结点的位置。

注：搜索二叉树是没有两个相同的结点的。

//根节点是否为空，如果为空开辟新的结点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{//AVL树是基于搜索二叉树的不会存在相等的情况return false;}}//找到要插入的位置进行插入//创建新的结点cur = new Node(kv);if (parent->_kv.first < kv.first){//大于放右边parent -> _right = cur;cur->_parent = parent;}else{//小于放左边parent->_left = cur;cur->_parent = parent;}

修改平衡因子

无论是在哪里插入结点二叉树的高度一定会发生变化高度发生变化平衡因子也会发生变化，因此要对平衡因子进行修改。

		while (parent){//当新增结点为左子树时相当于左子树高度加1//减数不变，被减数增加，结果减小if (cur == parent->_left){parent->_bf--;}else{//当新增结点为右子树时相当于右子树高度加1//减数增加，被减数不变，结果增大parent->_bf++;}//添加后左右子树高度相等//对父节点往上的结点的平衡因子都没有影响if (parent->_bf == 0){break;}//添加节点后对树的高度发生变化//继续向上修改平衡//对新增结点的父节点的父节点的平衡因子进行修改else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}}

 AVL树的旋转

结点的插入必然会影响父代及以上结点的平衡因子，从插入结点的父节点往上修改平衡因子，一定会出现平衡因子异常（超过1/0/-1），这时候就要进行旋转操作了。根据插入节点的位置不同，AVL树的旋转分为四种。

            else if (parent->_bf == 2 || 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){//先右旋在左璇RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){//先左璇在右璇RotateLR(parent);}

右单旋

新节点插入较高左子树的左侧

抽象图 

 

	//右单璇void RotateR(Node* parent){//拿到旋转结点Node* subL = parent->_left;//旋转结点的右孩子Node* subLR = subL->_right;//将父亲结点的左孩子更新为旋转结点的右孩子parent->_left = subLR;//判断旋转结点的右孩子是否为空if (subLR){//不为空更新旋转结点右孩子的父亲subLR->_parent = parent;}//找到父亲节点的父亲结点，准备更新父亲结点未旋转结点Node* parentParent = parent->_parent;//更新旋转结点的右孩子未父亲结点subL->_right = parent;//将父亲节点的父节点设置为旋转结点parent->_parent = subL;//父亲节点有可能未空结点if (parent == _root){_root = subL;subL->_parent = nullptr;}else{//更新父亲节点为旋转结点if (parent == parentParent->_left){parentParent->_left = subL;}else {parentParent->_right = subL;}//更新旋转结点的父亲结点，此时选装结点彻底为父亲结点subL->_parent = parentParent;}//更新平衡因子subL->_bf = parent->_bf = 0;}

左单旋

新节点插入较高右子树的右侧

void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;if (subRL){subRL->_parent == nullptr;}if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else if (parent == parentParent->_right){parentParent->_right = subR;}subR->_parent = parentParent;}parent->_bf = subR->_bf = 0;}

先右旋再左旋 

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

抽象图 

 

	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 = subR->_bf = subRL->_bf = 0;}else if (bf == -1){// subRL的左子树新增parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){// subRL的右子树新增parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else{assert(false);}}

先左旋再右旋

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

 

void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(cur);RotateR(parent);if (bf == 0){parent->_bf = cur->_bf = curright->_bf = 0;}else if (bf == 1){parent->_bf = 0;cur->_bf = -1;curright->_bf = 0;}else if (bf == -1){parent->_bf = 1;cur->_bf = 0;curright->_bf = 0;}}

AVL树的验证

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

1. 验证其为二叉搜索树

如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

	void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}


2. 验证其为平衡树

  • 每个节点子树高度差的绝对值不超过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 _IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return abs(rightHeight - leftHeight) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}

AVL树的删除（了解）

 因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不
错与删除不同的时，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。
具体实现大家可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。

AVL树的性能

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

今天的对数据结构中基于二叉搜索树的AVL树的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，个人主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是我前进的动力！

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

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

相关文章

SpringBoot多环境配置Maven Profile组

SpringBoot多环境配置Maven Profile组

Maven profile组 注意切换配置时 mvn clean下 或者 clean 加install 或者compile 编译 clean之后 install下 或者compile 编译 nohup java -Xms256m -Xmx512m -Dfile.encodingUTF-8 -jar demo.jar --spring.profiles.activeprod > system.log 2>&1 &
阅读更多...
数据交付变革：研发到产运自助化的转型之路

数据交付变革：研发到产运自助化的转型之路

作者 | Chris 导读 本文讲述为了提升产运侧数据观察、分析、决策的效率&#xff0c;支持业务的快速迭代&#xff0c;移动生态数据研发部对数仓建模与BI工具完成升级&#xff0c;采用宽表建模与TDA平台相结合的方案&#xff0c;一站式自助解决数据应用需求。在此过程中&#xff…
阅读更多...
软件测试|如何使用selenium操作窗口滚动条

软件测试|如何使用selenium操作窗口滚动条

简介 我们在进行自动化测试工作的时候&#xff0c;如果页面内容过多&#xff0c;一次性加载耗时太长的话&#xff0c;会使用分段加载来加载页面内容&#xff0c;比如开始只加载页面顶端的内容&#xff0c;而如果要加载更多的数据&#xff0c;就需要我们向下滑动&#xff0c;让…
阅读更多...
跳跃游戏，经典算法实战。

跳跃游戏，经典算法实战。

&#x1f3c6;作者简介&#xff0c;普修罗双战士&#xff0c;一直追求不断学习和成长&#xff0c;在技术的道路上持续探索和实践。 &#x1f3c6;多年互联网行业从业经验&#xff0c;历任核心研发工程师&#xff0c;项目技术负责人。 &#x1f389;欢迎 &#x1f44d;点赞✍评论…
阅读更多...
Go 优雅判断 interface 是否为 nil

Go 优雅判断 interface 是否为 nil

关注公众号【爱发白日梦的后端】分享技术干货、读书笔记、开源项目、实战经验、高效开发工具等&#xff0c;您的关注将是我的更新动力&#xff01; 背景 很久之前发过一篇文章&#xff1a;《10个令人惊叹的Go语言技巧&#xff0c;让你的代码更加优雅》&#xff0c;这篇文章中第…
阅读更多...
Dockerfile: CMD与ENTRYPOINT区别

Dockerfile: CMD与ENTRYPOINT区别

CMD和ENTRYPOINT的作用 CMD和ENTRYPOINT这两个命令&#xff0c;我接触到的是用在了Dockerfile中用于构建容器。 CMD&#xff1a;The main purpose of a CMD is to provide defaults for an executing container. CMD的主要用途是为正在执行的容器提供默认值。也就是指定这个容…
阅读更多...
如何用ArcGIS制作城市用地适应性评价

如何用ArcGIS制作城市用地适应性评价

01概述 “城市用地适宜性评价是城市总体规划的一项重要前期工作&#xff0c;它首先对工程地质、社会经济和生态环境等要素进行单项用地适宜性评价&#xff0c;然后用地图叠加技术根据每个因子所占权重生成综合的用地适宜性评价结果&#xff0c;俗称“千层饼模式”。 做用地适…
阅读更多...
外包干了4年，废了···

外包干了4年，废了···

有一说一&#xff0c;外包没有给很高的薪资&#xff0c;是真不能干呀&#xff01; 先说一下自己的情况&#xff0c;大专生&#xff0c;19年通过校招进入湖南某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0…
阅读更多...
tensorflow报错: DNN library is no found

tensorflow报错: DNN library is no found

错误描述 如上图在执行程序的时候&#xff0c;会出现 DNN library is no found 的报错 解决办法 这个错误基本上说明你安装的 cudnn有问题&#xff0c;或者没有安装这个工具。 首先检测一下你是否安装了 cudnn 进入CUDA_HOME下&#xff0c;也就是进入你的cuda的驱动的安装目…
阅读更多...
rime中州韵小狼毫 联想词组 滤镜

rime中州韵小狼毫 联想词组 滤镜

教程目录&#xff1a;rime中州韵小狼毫须鼠管安装配置教程 保姆级教程 100增强功能配置教程 在 rime中州韵小狼毫 自定义词典 一文中&#xff0c;我们分享了如何在rime中州韵小狼毫须鼠管输入法中定义用户自定义词典&#xff1b;通过自定义词典&#xff0c;我们可以很方便的在…
阅读更多...
ppt怎么录屏录音并且导出？好用录屏软件推荐

ppt怎么录屏录音并且导出？好用录屏软件推荐

ppt已经成为了日常工作与学习中必不可少的工具&#xff0c;而ppt屏幕录制功能&#xff0c;可以方便用户将他人的演讲或视频中的内容记录下来&#xff0c;以便进一步学习与研究。录制ppt演示并将其导出为视频文件&#xff0c;可以帮助我们进行分享&#xff0c;但是很多人不知道p…
阅读更多...
Qt QGraphicsItem获取鼠标位置对应图像坐标

Qt QGraphicsItem获取鼠标位置对应图像坐标

本次使用了QGraphicsView来加载图像&#xff0c;然后给其设置了一个QGraphicsScene场景&#xff0c;再给场景添加了一个自定义的QGraphicsItem&#xff0c;在其中重写了paint事件&#xff0c;用来重绘图像。 正常情况时&#xff0c;QGraphicsItem上图像的有效区域QRect大小和QG…
阅读更多...
深入探讨：开发连锁餐饮APP的关键技术要点

深入探讨：开发连锁餐饮APP的关键技术要点

时下&#xff0c;开发一款功能强大、用户友好的连锁餐饮APP成为许多餐饮企业的当务之急。在本文中&#xff0c;我们将深入探讨开发连锁餐饮APP的关键技术要点&#xff0c;涵盖了前端、后端以及数据库等方面。 一、前端开发 前端是用户与APP交互的入口&#xff0c;因此设计良好…
阅读更多...
低频信号发生器

低频信号发生器

前言 最近我快期末考试了&#xff0c;有点忙着复习。没时间写文章&#xff0c;不过学会了焊接 挺开心的所以买几套。 焊得怎么样这就是我们今天故事的主角“低频信号发生器”&#xff08;由于要用到所以这是购买链接&#xff09; 好&#xff0c;故事开始&#xff1a; 如何将…
阅读更多...
基于WebRTC技术的EasyRTC视频云服务系统在线视频客服解决方案

基于WebRTC技术的EasyRTC视频云服务系统在线视频客服解决方案

一、需求分析 随着互联网技术的发展&#xff0c;视频客服也成为服务行业的标配体验&#xff0c;基于WebRTC实时通信技术&#xff0c;客服人员与用户可以建立实时双向的视频交互与沟通。借助视频客服功能可以更加直观地了解用户的需求&#xff0c;提高沟通效率&#xff0c;并帮…
阅读更多...
手写一个starter来理解SpringBoot的自动装配

手写一个starter来理解SpringBoot的自动装配

自动装配以及简单的解析源码 自动装配是指SpringBoot在启动的时候会自动的将系统中所需要的依赖注入进Spring容器中 我们可以点开SpringBootApplication这个注解来一探究竟 点开这个注解可以发现这些 我们点开SpringBootConfiguration这个注解 可以发现实际上SpringBootApp…
阅读更多...
What is `@Repository` does?

What is `@Repository` does?

Repository 是Spring注解&#xff0c;标识数据访问层组件&#xff08;DAO, Data Access Object&#xff09; 当一个类被标记为 Repository 时&#xff1a; 1、组件扫描与自动代理&#xff1a; Spring通过组件扫描&#xff08;Component Scan&#xff09;机制发现带有 Reposit…
阅读更多...
@FunctionalSpringBootTest 和@SpringBootTest注解的区别

@FunctionalSpringBootTest 和@SpringBootTest注解的区别

FunctionalSpringBootTest 和 SpringBootTest 是Spring框架中用于测试的两个不同注解。下面是它们之间的主要区别&#xff1a; 用途和范围&#xff1a; SpringBootTest&#xff1a;这个注解用于需要测试Spring应用程序上下文的场合。它会加载完整的应用程序上下文&#xff0c;适…
阅读更多...
LitJson-Json字符串转对像时:整型与字符串或字符串转:整型进的类型不一致的处理

LitJson-Json字符串转对像时:整型与字符串或字符串转:整型进的类型不一致的处理

目录 问题描述上代码测试代码各位看官&#xff0c;打赏个1元吧 Json数据格式是大家在游戏开中常量用的一种数据格式&#xff0c;某种程度上可以说是必备的。对unity开发来说&#xff0c;LitJson这个json库应该是被使用最多的json库了。 问题描述 今天说要的其中的这个api: Jso…
阅读更多...
Linux知识（未完成）

Linux知识（未完成）

一、Linux 1.1 Linux 的应用领域 1.1.1 个人桌面领域的应用 此领域是 Linux 比较薄弱的环节但是随着发展&#xff0c;近几年 linux 在个人桌面领域的占有率在逐渐提高 1.1.2 服务器领域 linux 在服务器领域的应用是最高的 linux 免费、稳定、高效等特点在这里得到了很好的…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023