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

数据结构-二叉树-AVL树(平衡二叉树)

红黑树是平衡二叉树的一个变种。

一、 产生平衡二叉树的原因。

二叉搜索树的问题在于极端场景下退化为类似链表的结构,所以搜索的时间复杂度就变成了O(N)。为了保证二叉树不退化为链表,我们必须保证二叉树的的平衡性。

二叉平衡搜索树就是解决上面的问题的。就是AVL树和红黑树

拓展就是多叉平衡二叉树,那就是B树系列。然后哈希表也可以搜索。

二、二叉平衡树的概念。

当二叉搜索树中插入新节点后,如果能保证每个节点的左右子树高度只差的绝对值不超过1.即可降低树的高度,从而减少平均搜索的长度

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

它的左右子树都是AVL树,左右子树高度之差(平衡因子)的绝对值不超过1。增删查改:高度次 -O(logN)

三、平衡二叉树的插入。

在插入时,我们可以先构造二叉搜索树。然后再进行平衡操作。

1、新增在左边,parent平衡因子要减减

2、新增在右边,parent平衡因子要加加

3、更新后parent平衡因子==0,说明parent所在的子树的高度不变,不会影响祖先,不用再继续沿着到root的路径往上更新。插入完成

4、更新后parent平衡因子==负1or1,说明parent所在的子树的高度变化,会影响祖先,再继续沿着到root的路径往上更新。

5、更新后parent平衡因子 == 2or负2,说明parent所在的子树的高度变化且不平衡。对parent所在子树进行旋转,让它平衡。插入结束。

 6、更新到根节点也是一种插入结束的情况。那么如何进行平衡呢   

我们这里需要用到旋转平衡。

旋转的时候需要注意的问题。

1、保持它是搜索树

2、变成平衡树且降低整棵树的高度

左单旋:

核心操作就是parent->right = cur->left;cur->left = parent; 

这么做的原因是:cur->left一定比parent要大。然后放在parent的右边是符合搜索树的定义的。

 

注意要修改父亲,还要注意curleft为空的情况。修改平衡因子。还有要把子树跟原来的树连接

如果是独立的树 parent  == _root,进行parent->_parent置空。

如果不是独立的树我们需要对parent->_parent进行保存为ppnode,然后进行判断子树是属于ppnode的左子树还是右子树修改ppnode的左右子树为cur,然后修改cur的父亲指针。

抽象图的解释:

插入之前abc为符合AVL规则的子树。 无论是哪种情况,我们的旋转过程是不变的。插入前的AVL树有无数种情况,我们需要使用抽象图来表示。

双旋:

分为先左后右,先右后左

上面只是先右后左的图片。

相关文章:

数据结构-二叉树-AVL树(平衡二叉树)

红黑树是平衡二叉树的一个变种。 一、 产生平衡二叉树的原因。 二叉搜索树的问题在于极端场景下退化为类似链表的结构,所以搜索的时间复杂度就变成了O(N)。为了保证二叉树不退化为链表,我们必须保证二叉树的的平衡性。 二叉平衡搜索树就是解决上面的问…...

【Qt问题】windeployqt如何提取Qt依赖库

往期回顾 【Qt问题】Qt Creator 如何链接第三方库-CSDN博客 【Qt问题】Qt 如何带参数启动外部进程-CSDN博客 【Qt问题】VS2019 Qt win32项目如何添加x64编译方式-CSDN博客 【Qt问题】windeployqt如何提取Qt依赖库 考虑这个问题主要是:当我们的程序运行好之后&#…...

VS2019下使用MFC完成科技项目管理系统

背景: (一)实验目的 通过该实验,使学生掌握windows程序设计的基本方法。了解科技项目组织管理的主要内容和管理方面的基本常识,熟练应用数据库知识,通过处理过程对计算机软件系统工作原理的进一步理解&…...

【Android】Kotlin学习之数据容器(数组for循环遍历)

数组遍历 1. for ( item in arr){…} 2. for ( i in arr.indeces ) {…} (遍历下标) 3. for ((index, item) in arr.withInfex()) {…} (遍历下标和元素) 4. arr.forEach {} ( 遍历元素 ) 5. arr.forEachIndexed{index, item -> …}...

JavaWeb_请求响应_简单参数实体参数

一、SpringBoot方式接收携带简单参数的请求 简单参数:参数名与形参变量名相同,定义形参即可接收参数。并且在接收过程中,会进行自动的类型转换。 启动应用程序后,在postman中进行测试: 请求成功,响应回了O…...

windows端口复用

1. 概述 使用 HTTP.sys 中的 Net.tcp Port Sharing 服务,配合 WinRM 实现端口复用。 优点: HTTP.sys 为 windows 原生机制, WinRM 为 windows 自带功能,动作较小,不易触发主 动防御。 需要管理员权限。 2. 原理 (…...

[Redis] 使用布隆过滤器和分布式锁实现用户注册

布隆过滤器(Bloom Filter)是一种数据结构,用于快速判断一个元素是否可能存在于一个集合中。它通过使用多个哈希函数和一个位数组来表示一个集合,当一个元素被加入到集合时,通过哈希函数计算出多个哈希值,并…...

Okhttp 发送https请求,忽略ssl认证

工具类 import lombok.extern.slf4j.Slf4j;import javax.net.ssl.HostnameVerifier; import javax.net.ssl.SSLContext; import javax.net.ssl.SSLSocketFactory; import javax.net.ssl.TrustManager; import javax.net.ssl.TrustManagerFactory; import javax.net.ssl.X509Tru…...

IT项目管理-大题【太原理工大学】

一、根据进度网络写出时间参数表、关键路径、总工期 此类题一般是给一个表,问三问。 第一问会问某个活动的时间参数,但我们需要把整个表都求出来,否则单求一个很困难(如果你就是不想求整张表也行,不是硬性要求&#xf…...

【代码随想录】day48

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、198打家劫舍二、213打家劫舍II三、337打家劫舍III 一、198打家劫舍 class Solution { public:int rob(vector<int>& nums) {vector<int> dp(n…...

【补充】1-auth的使用、扩写auth的user表、django支持缓存

1 Auth的使用 1.1 扩写auth的user表 2 缓存 1 Auth的使用 # django 的一个app---》用户的登录&#xff0c;退出&#xff0c;注册。。。# 配置文件中配置&#xff1a;---》表会被迁移INSTALLED_APPS [django.contrib.auth,]# auth有哪些表---权限控制&#xff1a;-Permission&a…...

力扣-21. 合并两个有序链表-js实现

/*** Definition for singly-linked list.* function ListNode(val, next) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }*/ /*** param {ListNode} list1* param {ListNode} list2* return {ListNode}*/ const mergeTwoList…...

tensorflow报错

参考 TensorFlow binary is optimized to use available CPU instructions in performance-critical operations._this tensorflow binary is optimized to use availab-CSDN博客 解决Python中cuBLAS插件无法注册问题_unable to register cudnn factory: attempting to re-CS…...

企业数字化转型走向平台化运营会经历哪些阶段?

蚓链实践总结企业数字化转型走向平台化运营通常会经历以下几个阶段&#xff1a; 1. 规划与准备阶段&#xff1a;明确转型目标和战略&#xff0c;评估现有业务和技术状况&#xff0c;制定转型计划。 2. 基础建设阶段&#xff1a;搭建数字化基础设施&#xff0c;包括云平台、数…...

最新AI实景自动无人直播软件教你实现24小时不下播带货;智能化引领直播新时代

随着互联网的快速发展&#xff0c;直播行业已经成为商家品牌推广和商品销售的热门方式。而如今&#xff0c;一款令人惊叹的AI实景自动无人直播软件正在让直播变得更加智能化和便捷化&#xff0c;为商家带来全新的直播体验。 AI实景自动无人直播软件的一大优势是其智能讲解功能。…...

《二十一》QT QML编程基础

QML概述 QML&#xff08;Qt Meta-Object Language&#xff09;是一种声明性语言&#xff0c;它被用于描述Qt框架中用户界面的结构和行为。QML提供了一种简洁、灵活的方式来创建动态和交互式的界面。 QML基于JavaScript语法&#xff0c;通过使用QML类型和属性来定义界面的元素…...

免费的发票查验接口平台 PHP开发示例

信息爆炸的时代&#xff0c;发票管理工作也在不断走向数字化管理。传统手动录入的方式不仅耗时长&#xff0c;繁琐低效&#xff0c;且容易出现人为错漏的风险&#xff0c;让财务工作者头疼不已。人工智能时代&#xff0c;翔云推出了发票识别发票查验接口&#xff0c;以此来助力…...

10、算数运算符(以 ‘/’、‘%’、‘++’为主去讲解)(Java超详细版本)

算数运算符 一、算数运算符二、“ / ”的使用三、“ % ”的使用四、“ ”的使用⭐ 一、算数运算符 算数运算符是对数值类型的变量进行运算的&#xff0c;在Java程序中使用的非常多的。 二、“ / ”的使用 1、Java中 “ / ” 的运算结果是省略小数部分的整数&#xff0c;不存…...

向量数据库:PGVector

一、PGVector 介绍 PGVector 是一个基于 PostgreSQL 的扩展插件&#xff0c;为用户提供了一套强大的向量存储和查询的功能&#xff1a; 精确和近似最近邻搜索单精度&#xff08;Single-precision&#xff09;、半精度&#xff08;Half-precision&#xff09;、二进制&#xff…...

redux实现原理

Redux 是一个用于 JavaScript 应用程序状态管理的库。它被设计用来管理整个应用程序的状态&#xff0c;并且与 React 结合使用时非常流行。Redux 的实现原理可以简要概括为以下几个关键概念&#xff1a; 单一数据源 (Single Source of Truth)&#xff1a;Redux 应用程序的所有状…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...