map和set的底层结构——AVL树

前面对map和set做了简单的介绍,这几个的个共同特点就是其底层都是用二叉搜索树来写的,但是二叉搜索树有自身的缺陷,如果树中插入的元素有序或接近有序,二叉搜索树就会退化成单支树,时间复杂度变成O(N),所以map和set等关联式容器的底层结构是对二叉树做了平衡处理,采用AVL树实现

AVL树的概念

当向二叉搜索树插入新的节点后,如果能保证每个节点的左右子树高度差的绝对值不超过一,即是AVL树,如果超过一,就要进行调整,使其变成AVL树

AVL树节点的定义

template<calss T>
struct AVLTreeNode
{
AVLTreeNode(const T& data): _Left(nullptr), _Right(nullptr), _Parent(nullptr), _data(data), _bf(0){}AVLTreeNode<T>* _Left;   // 该节点的左孩子AVLTreeNode<T>* _Right;  // 该节点的右孩子AVLTreeNode<T>* _Parent; // 该节点的双亲T _data;int _bf;                  // 该节点的平衡因子
}

AVL树的插入

AVL树引入了平衡因子的概念,就是右子树高度-左子树高度

插入:

1.按照搜索树规则插入

2.更新祖先节点的平衡因子

a.插入父亲节点的右边,平衡因子++

b.插入父亲节点的左边,平衡因子--

c.父亲平衡因子==0,父亲所在子树高度不变,停止更新,插入结束

d.父亲平衡因子==1or-1,父亲所在子树高度变了,继续往上更新

e.父亲平衡因子==2or-2,父亲所在子树不平衡了,需要旋转处理

AVL树的旋转

当AVL树不平衡时,我们会进行旋转,一共有四种旋转方式:右单旋,左单旋,左右旋,右左旋

右单旋

右单旋对应的parent的平衡因子是-2,cur对应的平衡因子是-1

void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}parent->_bf = subL->_bf = 0;
}

左单旋

左单旋对应的parent的平衡因子是2,cur对应的平衡因子是1

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

左右旋

左右旋的第一种情况:新增节点在60的左子树,先进行左旋,然后右旋,最后更新平衡因子

左右旋的第二种情况:新增节点在60的右子树,先进行左旋,然后右旋,最后更新平衡因子

左右旋的第三种情况:60作为新增节点,先进行左旋,然后右旋,最后更新平衡因子

左右旋的条件是parent的平衡因子是-2,cur的平衡因子是1

void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;//左旋RotateL(parent->_left);//右旋Rotate(parent);//更新平衡因子if (bf == -1){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}}

右左旋和左右选差不多,也有三种情况,这里不再画图

右左旋的条件是parent的平衡因子是2,cur的平衡因子是-1

void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == 1){subRL->_bf = 0;subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 1;}else{subRL->_bf = 0;parent->_bf = 0;subR->_bf = 0;}
}

判断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 LeftHeight = _Height(root->_left);int RightHeight = _Height(root->_right);//不平衡if (abs(LeftHeight - RightHeight) >= 2){cout << root->_kv.first << "\n";return false;}//检查平衡因子if (RightHeight - LeftHeight != root->_bf){cout << root->_kv.first << "\n";return false;}return _IsBalance(root->_left) && _IsBalance(root->_right);
}

AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这样可以保证查询时高效的时间复杂度,即O(logN)但是如果要对AVL树做一些结构修改的操

作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时, 有可能一直要让旋转持续到根的位置。因此:如果需要一种查询高效且有序的数据结构,而且数

据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合。

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

全球“微软蓝屏”事件:IT基础设施韧性与安全性的考验

人不走空 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌赋&#xff1a;斯是陋室&#xff0c;惟吾德馨 目录 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌…

postman请求响应加解密

部分接口&#xff0c;需要请求加密后&#xff0c;在发动到后端。同时后端返回的响应内容&#xff0c;也是经过了加密。此时&#xff0c;我们先和开发获取到对应的【密钥】&#xff0c;然后在postman的预执行、后执行加入js脚本对明文请求进行加密&#xff0c;然后在发送请求&am…

Sentinel 入门与实战

一、Sentinel概念 1.1 什么是Sentinel Spring Cloud Alibaba Sentinel 是一个开源的流量控制和熔断框架&#xff0c;它是 Alibaba 开源的微服务框架 Spring Cloud Alibaba 中的一个组件。Sentinel 旨在解决分布式系统中的流量控制和熔断问题&#xff0c;帮助开发人员保护微服…

Power App学习笔记以及基础项目管理demo

Power App学习笔记以及基础项目管理demo 最近学习了一点Power App&#xff0c;感觉挺有意思。配置式组件开发。浅浅记录一下自己实现的项目管理系统&#xff08;即Excel数据的增删改查&#xff09;关于函数的一点皮毛认识。 效果图 筛选数据 编辑 详情 数据源 PowerApp 网…

流量录制与回放:jvm-sandbox-repeater工具详解

在软件开发和测试过程中&#xff0c;流量录制与回放是一个非常重要的环节&#xff0c;它可以帮助开发者验证系统在特定条件下的行为是否符合预期。本文将详细介绍一款强大的流量录制回放工具——jvm-sandbox-repeater&#xff0c;以及如何利用它来提高软件测试的效率和质量。 …

如何在Selenium Webdriver中点击SVG元素?

我们将在URL上单击下面突出显示的SVG元素&#xff1a;https&#xff1a;//testkru.com/Elements/SVGelemnts。 有几种方法可以点击SVG元素&#xff0c;我们将在这篇文章中讨论它们&#xff0c;并讨论它们之间应该首选哪一种。 使用 WebElement Click() 通过使用Action Click() …

vue3 Router 点击index中的按钮,查看相应的详情信息,并且传递id,及其路由的定义方法。

1、路由的定义 结构如下: 2、路由定义代码&#xff1a; {path: tabs,name: TabsDemo,component: () > import(/views/demo/feat/tabs/index.vue),meta: {title: t(routes.demo.feat.tabs),hideChildrenInMenu: true,},children: [{path: detail/:id,name: TabDetail,compon…

maven介绍 搭建Nexus3(maven私服搭建)

Maven是一个强大的项目管理工具&#xff0c;它基于项目对象模型&#xff08;POM&#xff1a;Project Object Model&#xff09;的概念&#xff0c;通过XML格式的配置文件&#xff08;pom.xml&#xff09;来管理项目的构建 Maven确实可以被视为一种工程管理工具或项目自动化构…

SpringcloudAlibaba详解---超详细

简介 Spring Cloud Alibaba是阿里巴巴结合自身的微服务实践开源的微服务全家桶&#xff0c;我个人觉得其组件比Spring Cloud 中的组件更加好用和强大。并且对的Spring Cloud组件做了很好的兼容。比如在Spirng Cloud Alibaba中依然可以使用Feign作为服务调用方式&#xff0c;使…

Mac如何在某个目录下快速打开iTerm2

最近喜欢上用Mac了&#xff0c;为了让自己用的更顺手和快速&#xff0c;设置了一堆快捷键&#xff0c;这里主要记录一下如何在某个文件夹下快速打开某一个软件。 然后你要快速再某一个文件夹路径下打开iTerm2这个软件&#xff0c;就鼠标选中文件夹&#xff0c;然后直接按快捷键…

一文带你搞懂C++运算符重载

7. C运算符重载 C运算符重载 什么是运算符重载 运算符重载赋予运算能够操作自定义类型。 运算符重载前提条件&#xff1a; 必定存在一个自定义类型 运算符重载实质: 就是函数调用 友元重载 类重载 在同一自定义类型中&#xff0c;一个运算符只能被重载一次 C重载只能重载…

2024年国际高校数学建模竞赛问题B:空间迁移计划和战略 成品文章分享

2024年国际高校数学建模竞赛问题B&#xff1a;空间迁移计划和战略&#xff08;2024 International Mathematics Molding Contest for Higher Education (IMMCHE)Problem B: Space Migration Program and Strategy&#xff09; 星际迁移计划中的资源分配与风险管理策略研究 摘…

【计算机网络】数据链路层实验

一&#xff1a;实验目的 1&#xff1a;学习WireShark软件的抓包操作&#xff0c;分析捕获的以太网的MAC帧结构。 2&#xff1a;学习网络中交换机互相连接、交换机连接计算机的拓扑结构&#xff0c;理解虚拟局域网&#xff08;WLAN&#xff09;的通信机制。 3&#xff1a;学习…

什么材质的挖耳勺好用?硬核上佳产品分享!

耳道健康随着生活品质的提高&#xff0c;逐渐被大家重视。因为它会直接影响我们的听力和卫生健康&#xff0c;如果长时间不清理&#xff0c;很容易堵塞在耳膜里导致耳鸣头晕等状况。挖耳勺的材质非常多&#xff0c;有铁质、不锈钢、软硅胶等等&#xff0c;那么什么材质的挖耳勺…

2024年国际高校数学建模竞赛问题B:空间迁移计划和战略完整思路 模型 代码 结果分享(仅供学习)

2024年国际高校数学建模竞赛问题B&#xff1a;空间迁移计划和战略&#xff08;2024 International Mathematics Molding Contest for Higher Education (IMMCHE)Problem B: Space Migration Program and Strategy&#xff09; 我们的未来有两种可能性:第一&#xff0c;我们将留…

国科大作业考试资料《人工智能原理与算法》2024新编-第十三次作业整理

1、假设我们从决策树生成了一个训练集&#xff0c;然后将决策树学习应用于该训练集。当训练集的大小趋于无穷时&#xff0c;学习算法将最终返回正确的决策树吗&#xff1f;为什么是或不是&#xff1f; 本次有两个参考&#xff1a; 参考一&#xff1a; 当训练集的大小趋于无穷…

飞牛爬虫FlyBullSpider 一款简单方便强大的爬虫,限时免费 特别适合小白!用它爬下Boss的2024年7月底Java岗位,分析一下程序员就业市场行情

一、下载安装FlyBullSpider 暂时支持Window,现在只在Win11上做过测试 1 百度 点击百度网盘 下载 链接&#xff1a;https://pan.baidu.com/s/1gSLKYuezaZgd8iqrXhk8Kg 提取码&#xff1a;Fly6 2 csdn https://download.csdn.net/download/fencer911/89584687 二、体验初…

C++(入门1)

C参考文档 Reference - C Reference C 参考手册 - cppreference.com cppreference.com 第一个C程序 #include<stdio.h> int main() {printf("Hello C\n");return 0; }由上述代码可知C是兼容C语言 第一个C标准程序 #include<iostream> using names…

Python教程(一):环境搭建及PyCharm安装

目录 引言1. Python简介1.1 编译型语言 VS 解释型语言 2. Python的独特之处3. Python应用全览4. Python版本及区别5. 环境搭建5.1 安装Python&#xff1a; 6. 开发工具&#xff08;IDE&#xff09;6.1 PyCharm安装教程6.2 永久使用教程 7. 编写第一个Hello World结语 引言 在当…

NO.1 Hadoop概述

目录 1.1 Hadoop是什么​编辑 1.2 Hadoop优势​编辑​编辑 1.3 Hadoop组成​编辑 1.3.1 HDFS架构概述 ​编辑 1.3.2 YARN架构概述 ​编辑 1.3.3 MapReduce架构概述​编辑 1.3.4 HDFS、YARN、MapReduce三者关系 1.4 大数据技术生态体系 1.5 推荐系统框架图 1.1 Hadoop…