数据结构学习笔记——查找算法中的树形查找(平衡二叉树)

目录

  • 一、平衡二叉树的定义
  • 二、平衡因子
  • 三、平衡二叉树的插入和构造
    • (一)LL型旋转
    • (二)LR型旋转
    • (三)RR型旋转
    • (四)RL型旋转
  • 四、平衡二叉树的删除
    • (一)叶子结点
    • (二)只有左/右子树,没有右/左子树
    • (三)既有左子树,又有右子树
  • 五、平衡二叉树的查找和平均查找长度

一、平衡二叉树的定义

平衡二叉树以二叉排序树为基础,若二叉排序树中左、右子树的高度之差的绝对值不超过1,则称为平衡二叉树(AVL树),其左、右子树也为一棵平衡二叉树,其平均查找长度为O(log2n),如下:
在这里插入图片描述

  • 一棵具有 m 层的平衡二叉树(AVL),最多有2m-1个结点,由斐波那契数列(Fibonacci),可得最少有f(m) = f(m-1) + f(m-2) + 1个结点,其中f(1) = 1 、f(2) = 2、f(3) = 4。

例如,具有5层结点的平衡二叉树的结点个数至少为f(5) = f(5-1) + f(5-2) + 1= f(4) + f(3) + 1=[f(3) + f(2) + 1]+[f(2) + f(1) + 1]+1=4+2+1+2+1+1+1=12个结点。

二、平衡因子

二叉树中左子树的深度减去其右子树深度,称为该结点的平衡因子,平衡二叉树中结点的平衡因子只可能为1-10三种,其中叶子结点的平衡因子均为0,例如下面这个二叉树为平衡二叉树:

叶子结点0、1、6的平衡因子均为0,
结点4的左子树深度为1,右子树深度为0,所以平衡因子为1-0=1,
结点9的左子树深度为1,右子树深度为0,所以平衡因子为1-0=1,
结点2的左子树深度为1,右子树深度为2,所以平衡因子为1-2=-1,
结点5的左子树深度为3,右子树深度为2,所以平衡因子为3-2=1。
在这里插入图片描述
而,下图这个二叉树为非平衡二叉树:
在这里插入图片描述
叶子结点0、1、4、9的平衡因子均为0,
结点3的左子树深度为1,右子树深度为1,所以平衡因子为1-1=0,
结点2的左子树深度为1,右子树深度为2,所以平衡因子为1-2=-1,
结点5的左子树深度为3,右子树深度为1,所以平衡因子为3-1=2,不满足平衡二叉树的要求。
在这里插入图片描述

三、平衡二叉树的插入和构造

平衡二叉树的插入操作性质与二叉排序树一样,也是要在保证一定条件下进行插入操作,若导致不满足条件则需要进行调整。若平衡二叉树中插入一个元素时导致发生了不平衡,则需要调整元素的位置关系,使其达到平衡,调整遵循的原则是每次调整的对象都是最小不平衡子树,即离插入结点最近的其平衡因子的绝对值大于1的结点作为根的子树。
插入新结点导致不平衡的情况有以下四种:

类别操作
LL型旋转(右单旋转)在结点的左子树的左子树插入新结点导致失衡
LR型旋转(先左后右旋转)在结点的左子树的右子树插入新结点导致失衡
RR型旋转(左单旋转)在结点的右子树的右子树插入新结点导致失衡
RL型旋转(先右后左旋转)在结点的右子树的左子树插入新结点导致失衡

(一)LL型旋转

若在结点的左子树的左子树插入新结点导致平衡二叉树失衡,则进行LL型旋转,即右单旋转。【向右顺时针旋转】
在这里插入图片描述
插入新结点6后导致平衡二叉树失衡,插入位置是结点9的左子树的左子树处,所以进行LL型旋转,如下:
在这里插入图片描述
调整后的二叉树即为平衡二叉树。

(二)LR型旋转

若在结点的左子树的右子树插入新结点导致平衡二叉树失衡,则进行LR型旋转。【先左旋转后右旋转】
在这里插入图片描述
插入新结点7后导致平衡二叉树失衡,插入位置是结点9的左子树的右子树处,所以进行LR型旋转,如下:
在这里插入图片描述
调整后的二叉树即为平衡二叉树。

(三)RR型旋转

若在结点的右子树的右子树插入新结点导致平衡二叉树失衡,则进行RR型旋转,即左单旋转。【向左逆时针旋转】
在这里插入图片描述
插入新结点10后导致平衡二叉树失衡,插入位置是结点7的右子树的右子树处,所以进行RR型旋转,如下:
在这里插入图片描述
调整后的二叉树即为平衡二叉树。

(四)RL型旋转

若在结点的右子树的左子树插入新结点导致平衡二叉树失衡,则进行RL型旋转。【先右旋转后左旋转】
在这里插入图片描述
插入新结点6后导致平衡二叉树失衡,插入位置是结点5的右子树的左子树处,所以进行RL型旋转,如下:
在这里插入图片描述
调整后的二叉树即为平衡二叉树。

四、平衡二叉树的删除

(一)叶子结点

平衡二叉树中,若要删除的结点只有叶子结点,则可直接将其删除,不影响平衡二叉树。
例如,删除平衡二叉树中的结点9,由于该结点是叶子结点,所以直接删除,如下:
在这里插入图片描述

(二)只有左/右子树,没有右/左子树

平衡二叉树中,若要删除的结点只有左/右子树,没有右/左子树,此时将该结点删除,后面的子结点接上即可,从而不影响平衡二叉树。
在这里插入图片描述

(三)既有左子树,又有右子树

平衡二叉树中,若要删除的结点既有左子树,又有右子树,此时可沿着左(右)子树的右(左)指针,一直走到右(左)子树的最右(左)边的一个结点,用该结点与要删除的结点代替【找到交换的结点】,然后,可以将其转换为(一)、(二)中的情况,若替代后,该结点为叶子结点则按照(一)进行删除,若非叶子结点则按照(二)进行删除。
例如,删除平衡二叉树中结点11,首先找到要交换的结点,即结点9,所以结点11与结点9进行交换,如下:
在这里插入图片描述
然后,由于此时结点11是叶子结点,此时转换为第一种情况,所以可直接删除,如下:
在这里插入图片描述

五、平衡二叉树的查找和平均查找长度

平衡二叉树的查找与二叉排序树一样,含有n个结点的平衡二叉树的最大深度为h=⌈log2(n+1)⌉,所以其平均查找长度为O(log2n),另外平衡二叉树的最小深度为h=⌈log2(n+1)⌉。

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

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

相关文章

【网络协议】TCP

TCP协议全称为传输控制协议(Transmission Control Protocol).要理解TCP就要从他的特性开始说,这些特性各自之间或多或少各有联结,需要以宏观视角来看待。 目录: 1.TCP报文格式 因为报文解释过于繁琐,具体内容请看这篇文章TCP报文…

oracle分组合并数值带顺序

比如:有如下一张设备电子围栏位置坐标的表(tb_equ_point)。 equ_name:设备电子围栏名称 point_id:点位坐标id point_x:点位x坐标 point_y:点位y坐标。 附数据: INSERT INTO "tb_equ_point" ("EQU_NAME",…

Spark SQL案例【电商购买数据分析】

数据说明 Spark 数据分析 (Scala) import org.apache.spark.rdd.RDD import org.apache.spark.sql.{DataFrame, SparkSession} import org.apache.spark.{SparkConf, SparkContext}import java.io.{File, PrintWriter}object Taobao {case class Info(u…

十六)Stable Diffusion教程:出图流程化

今天说一个流程化出图的案例,适用很多方面。 1、得到线稿,自己画或者图生图加线稿lora出线稿;如果想sd出图调整参数不那么频繁细致,则线稿的素描关系、层次、精深要表现出来,表现清楚。 2、文生图,seed随机…

Java进阶篇--网络编程

​​​​​​​ 目录 计算机网络体系结构 什么是网络协议? 为什么要对网络协议分层? 网络通信协议 TCP/IP 协议族 应用层 运输层 网络层 数据链路层 物理层 TCP/IP 协议族 TCP的三次握手四次挥手 TCP报文的头部结构 三次握手 四次挥手 …

Fiddler抓取Https请求配置

官网:https://www.telerik.com/fiddler 配置抓取https包 1.Tools->Options->Https,勾选下面。 2.Actions ->Trust Root Certificate.安装证书到本地 3.在手机端设置代理:本机ip如:192.168.1.168 端口号:8888。 4.手机…

DockerKubernetes ❀ Service下Port端口区分

文章目录 概述案例 概述 在Kubernetes中,Service(svc)是一种抽象机制,用于将一组 Pod 暴露给其他应用程序或服务。Service 可以有三种类型的端口: nodePort:这是 Service 在节点上公开的端口。可以使用此…

处理conda安装工具的动态库问题——解决记录 libssl.1.0.0 系统中所有openssl位置全览 whereis openssl

处理conda安装工具的动态库问题——解决记录 处理conda安装工具的动态库问题——解决记录 - 简书 解决libssl.so.1.0.0: cannot open shared object file: No such file or directory问题 - 简书 openssl 默认版本问题(Anaconda相关)_anaconda openssl-…

嵌入式开源库之libmodbus学习笔记

socat 安装sudo apt-get install socat创建终端 socat -d -d pty,b115200 pty,b115200查看终端 ls /dev/pts/ minicom 安装 sudo apt-get install minicom链接虚拟终端 sudo minicom -D /dev/pts/3以十六进制显示 minicom -D /dev/pts/1 -H设置波特率 minicom -D /dev/pts/1…

第1篇 目标检测概述 —(2)目标检测算法介绍

前言:Hello大家好,我是小哥谈。目标检测算法是一种计算机视觉算法,用于在图像或视频中识别和定位特定的目标物体。常见的目标检测算法包括传统的基于特征的方法(如Haar特征和HOG特征)以及基于深度学习的方法&#xff0…

[React] Context上下文的使用

文章目录 1.Context的介绍2.为什么需要Context3.Context的使用 1.Context的介绍 Context旨在为React复杂嵌套的各个组件提供一个生命周期内的统一属性访问对象,从而避免我们出现当出现复杂嵌套结构的组件需要一层层通过属性传递值得问题。 Context是为了提供一个组…

CTF 入门指南:从零开始学习网络安全竞赛

文章目录 写在前面CTF 简介和背景CTF 赛题类型介绍CTF 技能和工具准备好书推荐 写作末尾 写在前面 CTF比赛是快速提升网络安全实战技能的重要途径,已成为各个行业选拔网络安全人才的通用方法。但是,本书作者在从事CTF培训的过程中,发现存在几…

网络爬虫--伪装浏览器

从用户请求的Headers反反爬 在访问某些网站的时候,网站通常会用判断访问是否带有头文件来鉴别该访问是否为爬虫,用来作为反爬取的一种策略。很多网站都会对Headers的User-Agent进行检测,还有一部分网站会对Referer进行检测(一些资…

阿里云 Oss 权限控制

前言 最近公司的私有 Oss 服务满了,且 Oss 地址需要设置权限,只有当前系统的登录用户才能访问 Oss 下载地址。一开始想着用 Nginx 做个转发来着,Nginx 每当检测当前请求包含特定的 Oss 地址就转发到我们的统一鉴权接口上去,但是紧…

ElementUI动态树,数据表格以及分页的实现

目录 前言 一. ElementUI动态树 二. 数据表格和分页 三. 后端代码 service层 controller层 前言 在上一篇博客中实现了左侧菜单栏,在此基础上将它变为动态的,即动态的展示数据库的数据。还有数据表格的实现以及分页。(纯代码分享&#…

SpringCloud + SpringGateway 解决Get请求传参为特殊字符导致400无法通过网关转发的问题

title: “SpringCloud SpringGateway 解决Get请求传参为特殊字符导致400无法通过网关转发的问题” createTime: 2021-11-24T10:27:5708:00 updateTime: 2021-11-24T10:27:5708:00 draft: false author: “Atomicyo” tags: [“tomcat”] categories: [“java”] description: …

燃气安全如何保障?万宾燃气管网监测系统时刻感知管网运行态势

近年来随着我国城镇化建设的加快,燃气已经成为每个家庭的必需品。然而,每年夏季频繁发生的燃气爆炸事故,已经严重危害人民生命财产安全危害社会公共安全和公共利益。为了保障燃气安全运行,近日,许多城市都在大力推进燃…

wepack打包生产环境使用http-proxy-middleware做api代理转发的方法

首先安装http-proxy-middleware依赖,这个用npm和yarn安装都可以。 然后在express服务器的代码增加如下内容: const express require("express"); const app express(); const { createProxyMiddleware, fixRequestBody, } require("h…

WebGL笔记:绘制多个点,三角形,以及画各种不同的线条

绘制多点 1 ) WebGL 缓冲区 我们在用js定点位的时候,肯定是要建立一份顶点数据的,这份顶点数据是给着色器的,因为着色器需要这份顶点数据绘图然而,我们在js中建立顶点数据,着色器肯定是拿不到的&#xff…

ElementUI之首页导航与左侧菜单

目录 一、Mock 1.1 什么是Mock.js 1.2 安装与配置 1.2.1 安装mock.js 1.2.2 引入mock.js 1.3 mock.js使用 1.3.1 定义测试数据文件 1.3.2 mock拦截Ajax请求 1.3.3 界面代码优化 二、总线 2.1 定义 2.2 类型分类 2.3 前期准备 2.4 配置组件与路由关系 2.4.1 配置…