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

AVL树解析

目录

一. AVL的概念

二 AVL树的插入

2.1先按二叉搜索树的规则插入

2.2 AVL的重点:平衡因子更新

3.1 更新后parent的平衡因子等于0。

        3.2 更新后parent的平衡因子等于1 或 -1,需要继续往上更新。

 3.3 更新后parent的平衡因子等于2 或 -2,需要使用旋转处理。

三.旋转 和 平衡因子等于2 或 -2 的处理

1.右单旋(把左孩子变成爸爸) 

2.左单旋(把右孩子变成爸爸) 

3.左右双旋(把LR_Child 变为爸爸)

4.左右双旋(把RL_Child 变为爸爸)

总代码:


一. AVL的概念

1.AVL树是最先发明的自平衡二叉查找树,AVL是一颗空树,或者具备下列性质的二叉搜索树:它的
左右子树都是AV树,且 左右子树的高度差的绝对值不超过1AVL树是一颗高度平衡搜索二叉树,通过控制高度差去控制平衡!!!

2.AVL树实现这里我们引入一个平衡因子(balance factor)的概念,每个结点都有一个平衡因子,任何结点的平衡因子等于右子树的高度减去左子树的高度,也就是说任何结点的平衡因子等于0/1/-1
AVL树并不是必须要平衡因子,但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡
就像一个风向标一样。


二 AVL树的插入

AVL节点 的大概结构                                                  AVL树 的大概结构

  


2.1先按二叉搜索树的规则插入

具体可以看这篇

二叉搜索树-CSDN博客

这里是二叉搜索树的,简单的代码总结


2.2 AVL的重点:平衡因子更新

 因为:左右子树的高度差的绝对值不超过1 。

这里我们可以规定

1. 平衡因子 = 右子树高度 - 左子树高度 。

2. 插入结点时,会增加高度,如果新增结点 在parent的右子树,parent的平衡因子++,新增结点在parent的左子树,parent平衡因子--,parent的平衡因子初始化为 0.

3. parent的停止更新条件分为3种:



3.1 更新后parent的平衡因子等于0。


        3.2 更新后parent的平衡因子等于1 或 -1,需要继续往上更新。


上面的总代码:


 3.3 更新后parent的平衡因子等于2 或 -2,需要使用旋转处理。

下面为具体的分析:


三.旋转 和 平衡因子等于2 或 -2 的处理

旋转总共分为四种,左单旋/右单旋/左右双旋/右左双旋。

这里我们规定:

1. 在parent的左边 插入孩子,parent的平衡因子 -  1

2 .在parent的右边 插入孩子,parent的平衡因子 + 1


1.右单旋(把左孩子变成爸爸) 

需要 单纯的左边高!!! 才可以使用

比如 if(parent->_bf == -2 && SubR->_bf == -1)

如图:

分析:

因为 左右子树的高度差的绝对值不超过1 

我们需要把 a 往上提,把parent往下压 ,让SubL变成爸爸 才可以解决。

总的来说就是,左边高就把左边提上来,把右边压下去。

在这种情况下 他们的平衡因子就会为0.

代码为:

RotateR:


2.左单旋(把右孩子变成爸爸) 

需要 单纯的右边高!!! 才可以使用

比如 if(parent->_bf == 2 && SubR->_bf == 1)

如图:

分析:

因为 左右子树的高度差的绝对值不超过1 

我们需要把 a 往上提,把parent往下压 ,让SubR变成爸爸 才可以解决。

总的来说就是,右边高就把右边提上来,把左边压下去。

在这种情况下 他们的平衡因子就会为0.

代码为:

RotateL:


3.左右双旋(把LR_Child 变为爸爸)

需要 左边的右边高!!! 才可以使用

如图所示:

当没插入节点时:

在LR_Child 的左边插入节点:

具体过程

1. 让节点5 左旋转:

2.让节点8 右旋转

平衡因子:

在LR_Child 为空时

平衡因子 都为0.

在LR_Child 的左边插入节点:

LR_Child  平衡因子 为 0

L_Child 平衡因子 为 0

parent 平衡因子为 1

在LR_Child 的右边插入节点:

LR_Child  平衡因子 为 0

L_Child 平衡因子 为 -1

parent 平衡因子为 0

代码:


4.左右双旋(把RL_Child 变为爸爸)

太长了,随便写点了,脑子坏了!!!

在LR_Child 为空时

平衡因子 都为0.

在LR_Child 的右边插入节点:

RL_Child  平衡因子 为 0

R_Child 平衡因子 为 0

parent 平衡因子为 -1

在RL_Child 的左边插入节点:

RL_Child  平衡因子 为 0

R_Child 平衡因子 为 1

parent 平衡因子为 0

代码:


总代码:

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class T>struct AVLTreeNode
{AVLTreeNode(const T& data = T()): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNode<T>* _pLeft;AVLTreeNode<T>* _pRight;AVLTreeNode<T>* _pParent;T _data;int _bf;   // 节点的平衡因子
};// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{typedef AVLTreeNode<T> Node;
public:AVLTree(): _pRoot(nullptr){}// 在AVL树中插入值为data的节点bool Insert(const T& data){//如果树为空就建立一个根节点if (_pRoot == nullptr){_pRoot = new Node(data);}//树不为空else{Node* parent = nullptr;Node* tmp = _pRoot;//用cur找位置 while (tmp){//插入值比当前结点小往左走if (tmp->_data < data){parent = tmp;tmp = tmp->_pRight;}//插入值比当前结点大往右走else if (tmp->_data > data){parent = tmp;tmp = tmp->_pLeft;}else{assert(false);}}//在parent的左边或者右边插入插入Node* cur = new Node(data);if (parent->_data < data){parent->_pRight = cur;cur->_pParent = parent;}else if (parent->_data > data){parent->_pLeft = cur;cur->_pParent = parent;}//最困难的平衡因子部分while (parent){//cur插入在右边,平衡因子++if (cur == parent->_pRight)parent->_bf++;//反之亦然elseparent->_bf--;//平衡因子为0 结束if (parent->_bf == 0)break;//平衡因子为1 或 -1,往上更新else if(parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_pParent;}else if(parent->_bf == -2 || parent->_bf == 2){//...// //单纯左边高if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);parent->_bf = 0;cur->_bf = 0;}//单纯右边高else if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);parent->_bf = 0;cur->_bf = 0;}//左边的右边高else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}//右边的左边高else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}}return true;}// AVL树的验证bool IsAVLTree(){return _Height(_pRoot);}void InOrder(){return _InOrder(_pRoot);}size_t Height(){return _Height(_pRoot);}
private:// 根据AVL树的概念验证pRoot是否为有效的AVL树bool _IsAVLTree(Node* pRoot){if (pRoot == nullptr)return true;int left = _Height(pRoot->_pLeft);int right = _Height(pRoot->_pRight);int differ = right - left;if (differ >= 2 || differ <= -2)return false;if (differ != pRoot->_bf)return false;return _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);}void _InOrder(Node* cur){if (cur == nullptr)return;_InOrder(cur->_pLeft);cout << cur->_data << " ";_InOrder(cur->_pRight);}size_t _Height(Node* pRoot){if (pRoot == nullptr)return 0;size_t left = _Height(pRoot->_pLeft);size_t right = _Height(pRoot->_pRight);return right > left ? right + 1 : left + 1;}// 右单旋void RotateR(Node* pParent){Node* L_Child = pParent->_pLeft;Node* LR_Child = L_Child->_pRight;//左边孩子的 右边的孩子 和parent相互连接if (LR_Child)LR_Child->_pParent = pParent;pParent->_pLeft = LR_Child;//左孩子变在上面 右边连接parent ,grandfather 相互连接Node* grandfather = pParent->_pParent;pParent->_pParent = L_Child;L_Child->_pRight = pParent;L_Child->_pParent = grandfather;if (grandfather == nullptr){_pRoot = L_Child;}else{if (grandfather->_pLeft == pParent)grandfather->_pLeft = L_Child;elsegrandfather->_pRight = L_Child;}}// 左单旋void RotateL(Node* pParent){Node* R_Child = pParent->_pRight;Node* RL_Child = R_Child->_pLeft;//if(RL_Child)RL_Child->_pParent = pParent;pParent->_pRight = RL_Child;Node* grandfather = pParent->_pParent;pParent->_pParent = R_Child;R_Child->_pLeft = pParent;R_Child->_pParent = grandfather;if (grandfather == nullptr){_pRoot = R_Child;}else{if (grandfather->_pLeft == pParent)grandfather->_pLeft = R_Child;elsegrandfather->_pRight = R_Child;}}// 右左双旋void RotateRL(Node* pParent){Node* RChild = pParent->_pRight;Node* RLChild = RChild->_pLeft;//旋转完之后再用bf来判断平衡因子int bf = RLChild->_bf;RotateR(RChild);RotateL(pParent);if (bf == 0){pParent->_bf = 0;RChild->_bf = 0;RLChild->_bf = 0;}else if (bf == 1){RLChild->_bf = 0;RChild->_bf = 0;pParent->_bf = -1;}else if (bf == -1){RLChild->_bf = 0;RChild->_bf = 1;pParent->_bf = 0;}elseassert(false);}// 左右双旋void RotateLR(Node* pParent){Node* LChild = pParent->_pLeft;Node* LRChild = LChild->_pRight;int bf = LRChild->_bf;RotateL(LChild);RotateR(pParent);if (bf == 0){LRChild->_bf = 0;pParent->_bf = 0;LChild->_bf = 0;}else if (bf == 1){LRChild->_bf = 0;LChild->_bf = -1;pParent->_bf = 0;}else if (bf == -1){LRChild->_bf = 0;LChild->_bf = 0;pParent->_bf = 1;}elseassert(false);}private:Node* _pRoot;};

相关文章:

AVL树解析

目录 一. AVL的概念 二 AVL树的插入 2.1先按二叉搜索树的规则插入 2.2 AVL的重点&#xff1a;平衡因子更新 3.1 更新后parent的平衡因子等于0。 3.2 更新后parent的平衡因子等于1 或 -1&#xff0c;需要继续往上更新。 3.3 更新后parent的平衡因子等于2 或 -2&#xff0c;需…...

栈和队列(Java)

一.栈&#xff08;Stack&#xff09; 1.定义 栈是限定仅在表尾进行插入或删除操作的线性表 一般的表尾称为栈顶 表头称为栈底 栈具有“后进先出”的特点 2.对栈的模拟 栈主要具有以下功能&#xff1a; push(Object item)&#xff1a;将元素item压入栈顶。 pop()&am…...

C#设计原则

文章目录 项目地址一、开放封闭原则1.1 不好的版本1.2 将BankProcess的实现改为接口1.3 修改BankStuff类和IBankClient类二、依赖倒置原则2.1 高层不应该依赖于低层模块2.1.1 不好的例子2.1.2 修改:将各个国家的歌曲抽象2.2 抽象不应该依于细节2.2.1 不同的人开不同的车(接口…...

easyfs 简易文件系统

easyfs easyfs 简易文件系统文件系统虚拟文件系统 VFS简易文件系统 easyfs磁盘布局超级块 easyfs 文件系统结构磁盘上的索引结构索引节点Inode 和 DiskInode 之间的关系举例说明读取文件的过程&#xff08; /hello &#xff09; 参考文档 easyfs 简易文件系统 文件系统 常规文…...

【架构论文-1】面向服务架构(SOA)

【摘要】 本文以我参加公司的“生产线数字孪生”项目为例&#xff0c;论述了“面向服务架构设计及其应用”。该项目的目标是构建某车企的数字孪生平台&#xff0c;在虚拟场景中能够仿真还原真实产线的动作和节拍&#xff0c;实现虚实联动&#xff0c;从而提前规避问题&#xff…...

刚刚!更新宁德时代社招Verify测评语言理解数字推理SHL题库、网盘资料、高分答案

宁德时代社招入职的Verify测评主要分为两大块&#xff1a;语言理解和数字推理。语言理解部分包括阅读理解、逻辑填空和语句排序&#xff0c;要求在17分钟内完成30题。数字推理部分包括数字序列、数学问题解决和图表分析&#xff0c;同样要求在17分钟内完成18题。这些测评题目旨…...

C++笔记---智能指针

1. 什么是智能指针 1.1 RALL设计思想 RAII&#xff08;Resource Acquisition Is Initialization&#xff0c;资源获取即初始化&#xff09;是一种资源管理类的设计思想&#xff0c;广泛应用于C等支持对象导向编程的语言中。它的核心思想是将资源的管理与对象的生命周期紧密绑定…...

CentOS 7系统中更改YUM源为阿里云的镜像源

引言 更换阿里的镜像源可以带来诸多好处&#xff0c;包括提高下载速度、提升稳定性、同步更新、简化配置、节省带宽资源以及增强系统安全性等。因此&#xff0c;对于使用CentOS系统的用户来说&#xff0c;更换阿里的镜像源是一个值得考虑的选择。 1.备份yum源 mv /etc/yum.r…...

Python酷库之旅-第三方库Pandas(206)

目录 一、用法精讲 961、pandas.IntervalIndex.mid属性 961-1、语法 961-2、参数 961-3、功能 961-4、返回值 961-5、说明 961-6、用法 961-6-1、数据准备 961-6-2、代码示例 961-6-3、结果输出 962、pandas.IntervalIndex.length属性 962-1、语法 962-2、参数 …...

3.4CQU数学实验???

meshgrid 是一个用于生成网格点坐标的函数。它常用于在二维或三维空间中创建坐标网格&#xff0c;用于可视化和数据处理。 在二维情况下&#xff0c;meshgrid 函数接受两个一维数组作为输入&#xff0c;并返回两个二维数组&#xff0c;这两个数组中的元素分别表示了所有可能的…...

Linux(CentOS)开放端口/关闭端口

一、普通用户使用 sudo 操作&#xff0c;开放/关闭端口&#xff0c;80 1、检查端口是否开放 sudo firewall-cmd --zonepublic --query-port80/tcp 2、开放端口 sudo firewall-cmd --zonepublic --add-port80/tcp --permanent 3、重新加载&#xff08;开放或关闭端口后都需…...

GreenDao适配AGP8.7+

升级配置 工具版本Android StudioLadybug 2024.2.1 Path2AGP8.7.2KPG1.8.21GGP3.3.1明细 classpath "com.android.tools.build:gradle:$agp_version"classpath "org.jetbrains.kotlin:kotlin-gradle-plugin:$kgp_version"classpath "org.greenrobot:g…...

【前端】Typescript从入门到进阶

以下是 TypeScript 的常用知识点总结&#xff0c;涵盖了从基础到入门的内容&#xff0c;并配有代码示例&#xff1a; 1. TypeScript 基础 1.1 安装和配置 安装 TypeScript 并初始化配置文件&#xff1a; npm install -g typescript tsc --init 1.2 基本类型 TypeScript 提供…...

在 RHEL 8 | CentOS Linux release 8.5.2111上安装 Zabbix 6

1. 备份YUM源文件 cd /etc/yum.repos.d/ mkdir bak mv C* ./bak/ wget -O /etc/yum.repos.d/CentOS-Linux-BaseOS.repo https://mirrors.aliyun.com/repo/Centos-vault-8.5.2111.repo yum clean all yum makecache2. 将 SELinux 设置为宽容模式&#xff0c;如下所示。 sudo s…...

光纤HDMI线怎么连接回音壁?

第一步&#xff1a;准备HDMI线、光纤线&#xff08;TOSLINK线&#xff09;、视频源设备、回音壁 第二步&#xff1a;连接HDMI线&#xff0c;找到视频源设备上的HDMI输出口&#xff0c;将HDMI线的一端插入这个接口&#xff0c;再把HDMI线的另一端插入回音壁的HDMI输入口。注意检…...

屏幕后期处理

1、屏幕后期处理效果 屏幕后期处理效果&#xff08; Screen Post-Processing Effects&#xff09;是一种在渲染管线的最后阶段应用的视觉效果&#xff0c;允许在场景渲染完成后对最终图像进行各种调整和效果处理&#xff0c;从而增强视觉体验 常见的屏幕后期处理效果有&#x…...

K8资源之endpoint资源EP资源

1 endpoint资源概述 endpoint资源在K8S中用来表s示vc与后端 Pod 之间的连接关系的对象。当创建svc时&#xff0c;svc根据标签是否相同或svc名字是否和ep名字相同&#xff0c;把svc和ip关联上。 删除svc时&#xff0c;会自动的删除同名的ep资源。 2 ep资源和svc的关联测试 […...

微软日志丢失事件敲响安全警钟

NEWS | 事件回顾 最近&#xff0c;全球最大的软件公司之一——微软&#xff0c;遭遇了一场罕见的日志丢失危机。据报告&#xff0c;从9月2日至9月19日&#xff0c;持续长达两周的时间里&#xff0c;微软的多项核心云服务&#xff0c;包括身份验证平台Microsoft Entra、安全信息…...

Qt生成应用程序exe

1. 将工程用MinGW编译器在release模式下编译&#xff0c;生成可执行文件XXX.exe&#xff0c;新建一个文件夹如&#xff1a;F:\Setup\minGW&#xff0c;把exe文件放到这个目录下。 2. 将该编译器的bin文件添加到PATH环境变量里&#xff1a;bin文件路径为&#xff1a;D:\Qt\Qt5.…...

C#中的HttpContent、HttpClientHandle、HttpWebRequest

C#中的HttpContent 在C#中&#xff0c;HttpContent 是 System.Net.Http 命名空间下的一个类&#xff0c;它是 HttpClient 类用来发送和接收HTTP内容的基础。HttpContent 表示HTTP请求或响应的正文内容&#xff0c;并且可以序列化和反序列化数据。 HttpContent 是一个抽象类&a…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...