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

基于树表的查找

二叉排序树

相关概念

存储结构

查找

具体实现

算法分析

插入

创建

删除

无孩子

有一个孩子

有左右孩子 

示例

平衡二叉树

概念

示例

插入调整

类型

由插入结点在失衡结点的位置来定:插入结点C为失衡结点A的左子树的左孩子,因此为LL型。

原则

即选择中间结点作为新的树根,比其小的结点居左,比其大的结点居右,从而降低树高。

LL型

由调整原则可得:

取大小中间结点B作为根结点,插入结点比B小,A比根大,则分别作为其左右结点;

又因为B的右孩子比插入结点大,比A结点小,则作为A的左孩子

RR型

LR型

首先,找最小失衡子树;再用调整性原则进行调整。

最小失衡树由A B C三个结点组成。

其大小顺序为B<C<A,取中间结点C作为树根,则B A分别作为其左右孩子。

若C有左孩子,必定大于B,调整为B的右孩子;

若C有右孩子,必定小于A,调整为A的左孩子。

RL型

同理,首先,找最小失衡子树;再用调整性原则进行调整。

最小失衡树由A B C三个结点组成。

其大小顺序为A<C<B,取中间结点C作为树根,则A B分别作为其左右孩子。

若C有左孩子,必定大于A,调整为A的右孩子;

若C有右孩子,必定小于B,调整为B的左孩子。

示例

小结

调整过程就无需在意是左旋还是右旋,只需两个步骤:找最小失衡子树,结合调整原则。

删除调整

找最小失衡子树,按调整原则进行调整即可。

例1

无需调整,直接删除

例2

删除叶结点,还需向下调整

利用调整原则进行调整:

取中间结点80,比其小75作为其左孩子,比其大90作为其右孩子;

80有左孩子必定比75大,77作为75右孩子;

例3

删除结点有左右子树,

第一种:用前驱结点顶替(复制到)要删除的结点

利用调整性原则进行调整

第二种:用后继结点顶替(复制到)要删除的结点

利用失衡原则进行调整:

看成RR型,调整90为根结点

看成RL型,调整85作为根结点


http://www.mrgr.cn/news/29514.html

相关文章:

  • PostgreSQL序列:创建、管理与高效应用指南
  • 如何使用Django写个接口,然后postman中调用
  • 【Git】Git Clone 指定自定义文件夹名称:详尽指南
  • Redis8:商户查询缓存2
  • 半导体制造技术导论(第二版)萧宏 第二章集成电路工艺介绍答案
  • LLMs之Code:Github Spark的简介、安装和使用方法、案例应用之详细攻略
  • 网络封装分用
  • OpenHarmony(鸿蒙南向开发)——标准系统方案之瑞芯微RK3568移植案例(下)
  • 伪工厂模式制造敌人
  • 喜报!亲笔签数字科技荣获2024年“数据要素X”大赛重庆分赛三等奖
  • 构建 LLM 应用程序时经常遇到的高级概念的快速指南
  • 3.postman脚本语言、接口关联(json引用(变量)、脚本用正则表达式)、断言封装、自动化构造接口请求(Postman工具)
  • 直播开播极速流,如何有效接入?
  • 基于Spring Boot的学生社区故障维修预约系统的设计与实现(开题报告)
  • C++面试模拟01
  • C++:日期类的实现
  • YOLOv8改进:SA注意力机制【注意力系列篇】(附详细的修改步骤,以及代码,与其他一些注意力机制相比,不仅准确度更高,而且模型更加轻量化。)
  • 隐藏excel单元格数据的两个方法
  • 【d2l安装超详细老妈子教程】
  • 史上最强异步编程~CompletableFuture精读
  • hym8563/pcf8563 定时关机后,中断没有清除,导致INT脚一直为低,系统不开机。
  • GEE教程:1950-2023年ECMWF数据中积雪的长时序统计分析
  • 什么是泛在智能?应用在哪些场景?
  • PMP出成绩非常慢?PDU如何获取?
  • 为什么收录是谷歌seo的底子?
  • 在 Docker 中部署无头 Chrome:在 Browserless 中运行