当前位置: 首页 > news >正文

保姆级认识AVL树【C++】(精讲:AVL Insert)

目录

前言

一,概念

二,定义

三,insert

1. 插入情况

情况一:

情况二:

情况三:

2. 旋转方法

法一:左单旋法

法二:右单旋法

法三:先左后右双旋法

法四:先右后左双旋法

测试(判断一棵树是否是AVL树)

代码如下:

3. 随机值案例

四,删除


前言

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

搜索二叉树请查看本篇博文:【C++】搜索二叉树底层实现_花果山~程序猿的博客-CSDN博客

一,概念

二叉搜索树虽可以缩短查找的效率,但 如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法: 当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:
1. 它的左右子树都是AVL树
2. 左右子树高度之差(简称平衡因子)的绝对值不超过 1  (-1/0/1) (AVL树不一定用平衡因子进行实现)
如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在 O(log_2 n),搜索时间复杂度O(log_2 n)

二,定义

为方便循序渐进的学习,这里只放最出初始的树结点定义。

template <class K, class V>
class AVL_Data
{
public:pair<K, V> _kv;AVL_Data<K, V>* left = nullptr;AVL_Data<K, V>* right = nullptr;AVL_Data<K, V>* parent = nullptr;int _bf = 0; // ballance factorAVL_Data(const pair<K, V>& p):_kv(p){}};

上面定义在后面会进行完善修改。

三,insert

根据前面搜索二叉树的经验我们能快速写完插入函数,但AVL树是特殊的搜索二叉树,我们需要对树的高度进行调整。那么我们插入时就会遇到三种情况:

1. 插入情况

情况一:

情况二:

情况三:

代码实现如下:

template <class K, class V>
class AVL_Tree
{typedef AVL_Data<K, V>  AVL_Data;AVL_Data* root = nullptr;public:bool insert(const pair<K, V>& p){AVL_Data* new_a_d = new AVL_Data(p);if (!root){root = new_a_d;}else{AVL_Data* cur = root;AVL_Data* parent = nullptr;while (cur){if (p.first < cur->_kv.first){parent = cur;cur = cur->left;}else if (p.first > cur->_kv.first){parent = cur;cur = cur->right;}else{delete(new_a_d); // 插入失败,删除新建结点return false;}}if (p.first < parent->_kv.first){parent->left = new_a_d;}else{parent->right = new_a_d;}new_a_d->parent = parent;cur = new_a_d;//完成插入,进行平衡while (parent){   // 插入,修改parent平衡因子if (cur == parent->right){parent->_bf++;}else{parent->_bf--;}// 判断parent平衡因子是否是0,如果非0则需要向祖先更新平衡因子if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->parent;}else if (parent->_bf == 0){break;}else if(parent->_bf == 2 || parent->_bf == -2){ // 处理绝对值大于1,下面代码目的是记录未修改的平衡因子。// 需要旋转处理,这个我们下面再讲cur = parent;parent = parent->parent;}else{// 出现其他情况,在插入时这棵AVL树本身就是异常AVL树assert(false);}}return true;}}
};

2. 旋转方法

法一:左单旋法

我们以下面图为讲解例子,a,b,c表示的是子树。

h 表示子树的高度。

 请看下面场景:

h = 3, 4...组合方式会更多,这里画出图没什么意义,问题是失去平衡我们如何解决?? 

通过下面方法解决:

总结:

1. 右边高,则向左旋转。

2. C树发生插入,平衡因子发生改变,进而发生旋转。

void RotateL(AVL_Data* parent){assert(parent->right);AVL_Data* par = parent;AVL_Data* par_R = par->right;AVL_Data* par_RL = par->right->left;AVL_Data* ppnode = par->parent;par->right = par_RL;if (par_RL)par_RL->parent = par;par_R->left = par;par->parent = par_R;par_R->parent = ppnode;if (!ppnode){root = par_R;}else if (ppnode->left == par){ppnode->left = par_R;}else{ppnode->right = par_R;}par->_bf = 0;par_R->_bf = 0;}// 实验例子AVL_Tree<int, string> tree;tree.insert(make_pair(30 , "李四"));tree.insert(make_pair(20, "二麻子"));tree.insert(make_pair(60, "张三"));tree.insert(make_pair(45, "王五"));tree.insert(make_pair(75, "王五"));tree.insert(make_pair(65, "王五"));

法二:右单旋法

思路跟左旋法差不多,图像是相反,这里就只给场景解法模板:

h = 0, 1, 2的发生场景:

学会了法一自然会了法二:

void RotateR(AVL_Data* parent){assert(parent->left);AVL_Data* par = parent;AVL_Data* par_L = par->left;AVL_Data* par_LR = par->left->right;AVL_Data* ppnode = par->parent;par->left = par_LR;if (par_LR)par_LR->parent = par;par_L->right = par;par->parent = par_L;par_L->parent = ppnode;if (!ppnode){root = par_L;}else if (ppnode->left == par){ppnode->left = par_L;}else{ppnode->right = par_L;}par->_bf = 0;par_L->_bf = 0;}

法三:先左后右双旋法

跟单旋一样,我们首先展示,当h = 0,1,2时需要左右双旋处理的场景。

双旋法步骤变化流程,如下:

从结果来看,就是将60这个位置推上去置于“根”。

代码如下:

void RotateLR(AVL_Data* parent){assert(parent->left);AVL_Data* par = parent;AVL_Data* par_L = par->left;AVL_Data* par_LR = par->left->right;AVL_Data* ppnode = par->parent;int par_LR_bf = par_LR->_bf;RotateL(par_L);RotateR(par);if (par_LR_bf == -1){par->_bf = 1;par_L->_bf = 0;}else if (par_LR_bf == 1){par->_bf = 0;par_L->_bf = -1;}else if (par_LR_bf == 0){par->_bf = 0;par_L->_bf = 0;}else{assert(false);}par_LR->_bf = 0;}// 测试案例
void Test_insert_L()
{AVL_Tree<int, string> tree;tree.insert(make_pair(90, "李四"));tree.insert(make_pair(30, "二麻子"));tree.insert(make_pair(100, "张三"));tree.insert(make_pair(25, "王五"));tree.insert(make_pair(60, "王五"));tree.insert(make_pair(50, "王五"));
}

法四:先右后左双旋法

我们学会法三后,照葫芦画瓢即可。

各场景: 

代码:

void RotateRL(AVL_Data* parent){assert(parent->right);AVL_Data* par = parent;AVL_Data* par_R = par->right;AVL_Data* par_RL = par->right->left;AVL_Data* ppnode = par->parent;int par_RL_bf = par_RL->_bf;RotateR(par_R);RotateL(par);if (par_RL_bf == -1){par->_bf = 0;par_R->_bf = 1;}else if (par_RL_bf == 1){par->_bf = -1;par_R->_bf = 0;}else if (par_RL_bf == 0){par->_bf = 0;par_R->_bf = 0;}else{assert(false);}par_RL->_bf = 0;}// 测试案例
void Test_insert_L()
{AVL_Tree<int, string> tree;tree.insert(make_pair(30, "李四"));tree.insert(make_pair(20, "二麻子"));tree.insert(make_pair(90, "张三"));tree.insert(make_pair(15, "王五"));tree.insert(make_pair(60, "王五"));tree.insert(make_pair(100, "王五"));tree.insert(make_pair(55, "王五"));tree.insert(make_pair(67, "王五"));tree.insert(make_pair(95, "王五"));tree.insert(make_pair(50, "王五"));
}

测试(判断一棵树是否是AVL树)

思路:

1.  检查高度(AVL中每棵子树都是AVL树)。

2.  检查平衡因子是否正确。

代码如下:
int Hight(const AVL_Data* root){if (root == nullptr)return 0;int left_H = Hight(root->left);int left_R = Hight(root->right);return left_H >= left_R ? left_H + 1 : left_R + 1;}bool B_balance(){return _B_balance(root);}bool _B_balance(const AVL_Data* root){if (root == nullptr)return true;int left_root = Hight(root->left);int right_root = Hight(root->right);if ((right_root - left_root) != root->_bf) // 利用Hight,进行平衡因子判断return false; return abs(left_root - right_root) < 2 && _B_balance(root->left) && _B_balance(root->right);}

3. 随机值案例

用这个代码多跑几次,差不多能遍历所有环境。

void Random_Test()
{srand(time(0));const size_t N = 10000000;AVL_Tree<int, int> t;for (size_t i = 0; i < N; i++){size_t x = rand();t.insert(make_pair(x, x));}cout << t.B_balance() << endl;
}

快来测试自己的代码吧

insert全代码

bool insert(const pair<K, V>& p){AVL_Data* new_a_d = new AVL_Data(p);if (!root){root = new_a_d;}else{AVL_Data* cur = root;AVL_Data* parent = nullptr;while (cur){if (p.first < cur->_kv.first){parent = cur;cur = cur->left;}else if (p.first > cur->_kv.first){parent = cur;cur = cur->right;}else{delete(new_a_d); // 插入失败,删除新建结点return false;}}if (p.first < parent->_kv.first){parent->left = new_a_d;}else{parent->right = new_a_d;}new_a_d->parent = parent;cur = new_a_d;//完成插入,进行平衡while (parent){   // 插入,修改parent平衡因子if (cur == parent->right){parent->_bf++;}else{parent->_bf--;}// 判断parent平衡因子是否是0,如果非0则需要向祖先更新平衡因子if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->parent;	}else if (parent->_bf == 0){break;}else if (parent->_bf == -2 || parent->_bf == 2){if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);// cout << "RotateL" << endl;}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);// cout << "RotateR" << endl;}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);// cout << "RotateLR" << endl;}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);// cout << "RotateRL" << endl;}else{// 出现其他情况,在插入时这棵AVL树本身就是异常AVL树// 问题出现在旋转方法assert(false);}break;}else{assert(false);}}return true;}}

四,删除

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

下期预告: 红!!!

结语

   本小节就到这里了,感谢小伙伴的浏览,如果有什么建议,欢迎在评论区评论,如果给小伙伴带来一些收获请留下你的小赞,你的点赞和关注将会成为博主创作的动力

相关文章:

保姆级认识AVL树【C++】(精讲:AVL Insert)

目录 前言 一&#xff0c;概念 二&#xff0c;定义 三&#xff0c;insert 1. 插入情况 情况一&#xff1a; 情况二&#xff1a; 情况三&#xff1a; 2. 旋转方法 法一&#xff1a;左单旋法 法二&#xff1a;右单旋法 法三&#xff1a;先左后右双旋法 法四&#xf…...

pinia中使用reactive声明变量,子页面使用时,值未改变,即不是响应式的(解决方法)

reactive赋值无效&#xff01;reactive 不要直接data赋值&#xff01;&#xff01;&#xff01;会丢失响应式的&#xff0c;只能通过obj.属性 属性值赋值 方法一. pinia中直接使用ref定义变量即可 export const useUserStoredefineStore(user,()>{let loginUserreactive({…...

基于springboot零食商城管理系统

功能如图所示 摘要 这基于Spring Boot的零食商城管理系统提供了强大的购物车和订单管理功能。用户可以在系统中浏览零食产品&#xff0c;并将它们添加到购物车中。购物车可以保存用户的选购商品&#xff0c;允许随时查看已选择的商品和它们的数量。一旦用户满意&#xff0c;他们…...

C++程序练习

定义一个类CheckPath&#xff0c;它由两个public方法组成&#xff1a; 1&#xff09; checkPath&#xff1a;检查传入的字符串指定的路径是否存在&#xff0c;存在返回true&#xff0c;否则返回false。 2&#xff09; createFilePath&#xff1a;根据传入的字符串指定的路径&…...

Golang 继承

在面向对象的编程语言中&#xff0c;继承是一种重要的机制&#xff0c;它允许子类继承父类的属性和方法。然而&#xff0c;Go语言在设计时没有直接支持传统意义上的继承&#xff0c;而是提供了一种更为灵活和简洁的方式来实现类似的功能。本文将探讨Golang中实现继承的方法和最…...

棋盘格测距-单目相机(OpenCV/C++)

一、文章内容简述&#xff1a; 1’ 通过cv::findChessboardCorners寻找棋盘格角点 2‘ 用cv::solvePnP计算旋转向量rvec和平移向量tvec 3’ 通过公式计算相机到棋盘格的距离 float distance sqrt(tvec.at<double>(0,0) * tvec.at<double>(0,0) tvec.at<do…...

031-从零搭建微服务-监控中心(一)

写在最前 如果这个项目让你有所收获&#xff0c;记得 Star 关注哦&#xff0c;这对我是非常不错的鼓励与支持。 源码地址&#xff08;后端&#xff09;&#xff1a;mingyue: &#x1f389; 基于 Spring Boot、Spring Cloud & Alibaba 的分布式微服务架构基础服务中心 源…...

vue中使用xlsx插件导出多sheet excel实现方法

安装xlsx&#xff0c;一定要注意版本&#xff1a; npm i xlsx0.17.0 -S package.json&#xff1a; {"name": "hello-world","version": "0.1.0","private": true,"scripts": {"serve": "vue-c…...

Linux - 进程的优先级 和 如何使用优先级调度进程

理解linux 当中如何做到 把一个PCB 放到多个 数据结构当中 在Linux 当中&#xff0c;一个进程的 PCB 不会仅仅值存在一个 数据结构当中&#xff0c;他既可以在 某一个队列当中&#xff0c;又可以在 一个 多叉树当中。 队列比如 cpu 的 运行队列&#xff0c;键盘的阻塞队列等等…...

支持控件drag和click

在 MouseDown 事件触发 DoDragDrop 拖拽操作时&#xff0c;Click 事件通常无效&#xff0c;因为 DoDragDrop 方法会捕获鼠标事件并等待拖拽操作完成。 有一个简单地思路解决这个问题 当MouseDow时&#xff0c;触发定时器&#xff0c;延迟100s定时器到时后&#xff0c;进入dra…...

AIR101 LuatOS LVGL 显示多个标签例程

屏幕资料 AIR101与屏幕连接 PC端仿真环境合宙官方PC端版本环境搭建教程 PC电脑仿真 -- sys库是标配 _G.sys require("sys") sys.taskInit(function()local cnt0lvgl.init(480,320)--lvgl初始化local cont lvgl.cont_create(nil, nil);-- lvgl.cont_set_fit(cont, …...

Istio实战(七)- Bookinfo 部署

1. Istio Bookinfo示例 1.1 部署Bookinfo # kubectl apply -f /apps/istio/samples/bookinfo/platform/kube/bookinfo.yaml -n hr1.2 确认Bookinfo已经部署正常 先确认以下pod和service已经被正确创建 # kubectl get pods -n hr NAME READY …...

出差学小白知识No5:|Ubuntu上关联GitLab账号并下载项目(ssh key配置)

1 注冊自己的gitlab账户 有手就行 2 ubuntu安装git &#xff0c;并查看版本 sudo apt-get install git git --version 3 vim ~/.ssh/config Host gitlab.example.com User your_username Port 22 IdentityFile ~/.ssh/id_rsa PreferredAuthentications publickey 替换gitl…...

FL Studio21.2中文版多少钱?值得下载吗

水果&#xff0c;全称Fruity Loop Studio&#xff0c;简称FL Studio。是一款全能的音乐制作软件&#xff0c;经过二十多年的演化更迭&#xff0c;其各项功能非常的先进。其开创性的Pat\song模式&#xff0c;也为初学者的学习提供了便利。那么水果音乐制作软件需要多少钱呢&…...

软考系统架构师知识点集锦三:软件架构设计

一、考情分析 二、考点精讲 2.1软件架构的概念 2.1.1什么是架构(暂无定论) 架构设计就是需求分配&#xff0c;即将满足需求的职责分配到组件上。 软件架构风格是描述某-特定应用领域中系统组织方式的惯用模式。架构风格定义-个系统家族,即一个体系结构定义一个词汇表和一组约…...

docker - window Docker Desktop升级

文章目录 前言docker - window Docker Desktop升级 前言 如果您觉得有用的话&#xff0c;记得给博主点个赞&#xff0c;评论&#xff0c;收藏一键三连啊&#xff0c;写作不易啊^ _ ^。   而且听说点赞的人每天的运气都不会太差&#xff0c;实在白嫖的话&#xff0c;那欢迎常来…...

Element UI + Vue 新增和编辑共用表单校验无法清除问题(已解决)

问题描述 在新增和编辑过程中大部分情况下 两个表单是一致的&#xff0c;而且编辑也有回显需要&#xff0c;所有绝大多数情况下 都是一个表单两个用处&#xff0c;但是随之而来出现了一个无法清除校验的问题&#xff0c;在先点击编辑后再点击新增会出现校验红字&#xff1a; …...

FL Studio21最新中文汉化解锁版,2024怎么激活FL Studio

FL Studio2024最新中文汉化解锁版是一款功能强大的数字音频工作站&#xff08;DAW&#xff09;&#xff0c;它广泛应用于音乐创作和音乐制作领域。在使用FL Studio时&#xff0c;购买正版软件是否有必要呢&#xff1f;本文将详细探讨FL Studio的功能特点以及正版软件的重要性。…...

Mac怎么清理磁盘空间?释放Mac磁盘空间有效方法

相信很多使用macOS系统的小伙伴都收到过提示“磁盘空间已满”消息&#xff0c;尤其是采用SSD固态硬盘的MacBook系列&#xff0c;120G的硬盘空间本就捉襟见肘&#xff0c;使用一段时间后&#xff0c;即使自己没有存放很多大文件&#xff0c; Mac的磁盘很快就满了。那么&#xff…...

论文阅读(一)城市干道分段绿波协调控制模型研究

[1]酆磊,赵欣,李林等.城市干道分段绿波协调控制模型研究[J].武汉理工大学学报(交通科学与工程版),2021,45(06):1034-1038. 主要内容:该文介绍了基于绿波带宽和关联度的城市干道分段绿波协调控制模型。通过将主干道划分为不同子区域,并根据路段特点进行精准化控制,实现了分段…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...

Python实现简单音频数据压缩与解压算法

Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中&#xff0c;压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言&#xff0c;提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...

拟合问题处理

在机器学习中&#xff0c;核心任务通常围绕模型训练和性能提升展开&#xff0c;但你提到的 “优化训练数据解决过拟合” 和 “提升泛化性能解决欠拟合” 需要结合更准确的概念进行梳理。以下是对机器学习核心任务的系统复习和修正&#xff1a; 一、机器学习的核心任务框架 机…...