首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

咬文嚼图式的介绍二叉树、B树/B-树

编程知识
2024年07月16日 14:50

前言

因为本人天资愚钝,所以总喜欢将抽象化的事务具象化表达。对于各类眼花缭乱的树,只需要认知到它们只是一种数据结构,类似数组,切片,列表,映射等这些耳熟能详的词汇。对于一个数据结构而言,无非就是增删改查而已,既然各类树也是数据结构,它们就不能逃离增删改查的桎梏。

那么,为什么我们需要树这种数据结构呢,直接用数组不行吗,用切片不行吗?当然可以,只不过现实世界是缤纷杂乱的,而又没有一种万能药式的数据结构以应对千变万化的业务需求。所以,才会有各类树,而且一些“高级”数据结构是基于树形数据结构的,例如映射。

二叉树

在中文语境中,节点结点傻傻分不清楚,故后文以 node 代表 "结点",root node 代表根节点,child node 代表 “子节点”

二叉树是诸多树状结构的始祖,至于为什么不是三叉树,四叉树,或许是因为计算机只能数到二吧,哈哈,开个玩笑。二叉树很简单,每个 node 最多存在两个 child node,第一个节点称之为 root node。

二叉树具备着一些基本的数学性质,不过很简单,定义从 i 从 0 开始:

  • i 层至多有 2i 个 node;
  • 深度为 i 层二叉树至多有 2i+1-1 个 node。

二叉树的特殊类型

这里有兴趣的可以了解一下,不影响后文的阅读。二叉树根据 child node 的不同,衍生出了几种特殊类型:在一颗二叉树中,如果每个 node 都有 0 或 2 个 child node,则二叉树是满二叉树;定义从 i 从 0 开始,一棵深度为 i,且仅有 2i+1−1 个 node 的二叉树,称为完美二叉树;若除最后一层外的其余层都是满的,并且最后一层要么是满的,要么在右边缺少连续若干 node,则此二叉树为完全二叉树

二叉搜索树

二叉搜索树(Binary Search Tree),也叫二叉查找树,有序二叉树,排序二叉树(名字还挺多)。它是一种常用且特殊的二叉树,它具备一个特有的性质,left node(左结点)始终小于 parent node (父结点),right node 始终大于 parent node。

二叉搜索树的查找

  1. 二叉搜索树从 root node 开始,如果命中则返回;
  2. 否则,目标值比 node 小进入 left node;
  3. 比 node 大进入 right node;
  4. 如果左右都为空,则未命中。

二叉搜索树的遍历

二叉搜索树有不同的遍历方式,这里介绍常用的中序遍历方式:

  1. 先遍历左子树;
  2. 然后查找当前左子树的 parent node;
  3. 遍历右子树。

二叉搜索树的插入

  1. 二叉搜索树从 root node 开始,如果命中则不进行操作;
  2. 否则,目标值比 node 小进入 left node;
  3. 比 node 大进入 right node;
  4. 最终将值插入搜索停止的地方。

二叉搜索树的删除

二叉树的删除和查询基本一致,只要在命中时删除即可。

  1. 二叉搜索树从 root node 开始,如果命中则删除;
  2. 否则,目标值比 node 小进入 left node;
  3. 比 node 大进入 right node;
  4. 删除后使用该 node 左子树最大值或者右子树最小值替代该 node。

自平衡二叉树

从上面的几张动图中我们知晓,二叉搜索树不同于线性结构,它可以大大降低查找,插入的时间复杂度。但在特殊情况下,二叉搜索树可能退化为线性结构,假如我们依次插入1,2,3,4,5:

此时,二叉搜索树退化为线性结构,效率重新变回遍历。于是,便出现了自平衡二叉树,例如 AVL 树,红黑树,替罪羊树等。但它们并不是本文重点,下面我要介绍的是另外一种很常见的自平衡二叉树:B树。

B树

B树和B-树是同一个概念。B树相对于二叉树有两点最大的不同:

  • 每个 node 可以有不止一个数值
  • 每个 node 也可以有不止两个 child node

B树有两种类型 node:

  • internal node(内部结点):不仅仅存储数据,也具备 child node;
  • leaf node(叶子结点):仅存储数据,不具备 child node。

这两种 node 不同于前文所提的 root node 和 child node。root 和 child 是相对于阶层的概念,而 internal 和 leaf 是相对于性质的概念

一个简单的图例如下:

图中的蓝色方块是 internal node,绿色则是 leaf node。

B树有一些需要满足的性质,这里的抽象的逻辑有些烧脑,我会对照前面的图片来解释。设定一颗 m 阶的B树,m = 3

设 internal node 的 child node 个数为 k

  1. 如果 internal node 是 root node,那么 k = [2, m],比如上图的 8 有两个 child node(3|6, 10/12);
  2. 如果 internal node 不是 root node,那么 k = [m/2, m],m/2 向上取整,比如上图的 3|6 有三个 child node;
  3. 如果 root node 的 k 为 0,那么 root node 是 leaf 类型的;
  4. 所有 leaf node 在同一层,上图最后一行的六个 node。

设任意 node 键值个数为 n

  1. 对于 internal node, n = k-1, 升序排序,满足 k[i] < k[i+1],比如上图的三个 internal(8,3|6,10|12) 都满足此规律;
  2. 对于 leaf node,n = [0, m-1],同样升序排序,比如上图最后一个的六个 leaf,其键值最多为两个。 

上述的概念有些抽象,但是这是理解B树关键的地方所在,后面在B树的插入讲解,会有更多具象的动图来解释这些概念。

B树的查找

B树的查找类似于二叉树:

  1. 从 root node 开始,如果目标值小于 root node,进入左子树,否则进入右子树;
  2. 遍历 child node 的多个键值;
  3. 如果匹配到键值,则返回;
  4. 如果不匹配,则根据目标值的范围选择对应的子树;
  5. 重复步骤2、3、4,直到匹配成功返回或者未找到。

假如我们要查找 11:

B树的遍历

B树的遍历方式类似二叉搜索树,不过因为B树一个 node 有多个键值和多个 child node,所以需要遍历每个左右子树和键值:

  1. 先遍历第一个左子树,也就是 parent node 第一个键值的左边;
  2. 然后查找当前 parent node 的第一个键值;
  3. 遍历第二个左子树,也就是 parent node 第二个键值的左边;
  4. 遍历完搜索的左子树,最后遍历当前 parent 的最右子树,即最后一个键值的右边。

B树的插入

插入前面的过程和查询一致,在插入后可能需要重整 node,以符合B树的性质,例如插入 16:

  1. 先查找到目标 node,也就是 13|15
  2. 因为这是一颗 3 阶B树,所以 node 最多只能有两个键值,于是向上传递中间值 15;
  3. parent node 最多也只能有两个键值,于是继续向上传递中间值 12;
  4. 此时 root node 是 8|12,需要有三个 child node,于是 10|15 需要拆分,再向下进一步调整,至此,插入 16 完成。

 

B树的删除

删除是插入的逆操作,但是往往比插入更复杂,因为删除后经常需要重整 node:

  1. 先查找到目标 node,也就是 16
  2. 删除 16,此时 15 child node 剩下一个,不符合条件,递归向上调整,一直到根节点;
  3. 直到所有的条件都满足后,删除 16 完成。

From:https://www.cnblogs.com/oldme/p/18305424
本文地址: http://www.shuzixingkong.net/article/107
0评论
提交 加载更多评论
其他文章 manim边学边做--Matrix
在代数问题中,矩阵是必不可少的工具,manim中提供了一套展示矩阵(Matrix)的模块,专门用于在动画中显示矩阵格式的数据。关于矩阵的类主要有4个: Matrix:通用的矩阵 IntegerMatrix:元素是整数的矩阵 DecimalMatrix:元素包含小数的矩阵 MobjectMatrix:
manim边学边做--Matrix manim边学边做--Matrix manim边学边做--Matrix
利用FastAPI和OpenAI-Whisper打造高效的语音转录服务
最近好久没有写博客了,浅浅记录下如何将OpenAI-Whisper做成Web服务吧&#129315; 介绍 在这篇指导性博客中,我们将探讨如何在Python中结合使用FastAPI和OpenAI-Whisper。OpenAI-Whisper是一个前沿的语音识别模型,而FastAPI是一个高性能的现代
利用FastAPI和OpenAI-Whisper打造高效的语音转录服务 利用FastAPI和OpenAI-Whisper打造高效的语音转录服务 利用FastAPI和OpenAI-Whisper打造高效的语音转录服务
iOS开发基础109-网络安全
在iOS开发中,保障应用的网络安全是一个非常重要的环节。以下是一些常见的网络安全措施及对应的示例代码: Swift版 1. 使用HTTPS 确保所有的网络请求使用HTTPS协议,以加密数据传输,防止中间人攻击。 示例代码: 在Info.plist中配置App Transport Security (
PixiJS源码分析系列:第二章 渲染在哪里开始?
第二章 渲染在哪里开始? 牢记,按第一章介绍的 npm start 启动本地调式环境才可进行调式 如果是 example 文件夹内的例子还需要 serve . 开启本地静态服务器 上一章介绍了 PixiJS 源码调式环境的安装,以及基本的调试方法。本章要研究一下它是如何渲染的 渲染大致步骤: 注册渲
PixiJS源码分析系列:第二章 渲染在哪里开始? PixiJS源码分析系列:第二章 渲染在哪里开始? PixiJS源码分析系列:第二章 渲染在哪里开始?
MViT:性能杠杠的多尺度ViT | ICCV 2021
论文提出了多尺度视觉Transformer模型MViT,将多尺度层级特征的基本概念与Transformer模型联系起来,在逐层扩展特征复杂度同时降低特征的分辨率。在视频识别和图像分类的任务中,MViT均优于单尺度的ViT。 来源:晓飞的算法工程笔记 公众号 论文: Multiscale Vision
MViT:性能杠杠的多尺度ViT | ICCV 2021 MViT:性能杠杠的多尺度ViT | ICCV 2021 MViT:性能杠杠的多尺度ViT | ICCV 2021
yearrecord——一个类似痕迹墙的React数据展示组件
介绍一下自己做的一个类似于力扣个人主页提交记录和GitHub主页贡献记录的React组件。 下图分别是力扣个人主页提交记录和GitHub个人主页的贡献记录,像这样类似痕迹墙的形式可以比较直观且高效得展示一段时间内得数据记录。 然而要从0实现这个功能还是有一些麻烦得,并且该功能可用的场景也比较多,于是
yearrecord——一个类似痕迹墙的React数据展示组件 yearrecord——一个类似痕迹墙的React数据展示组件 yearrecord——一个类似痕迹墙的React数据展示组件
Asp .Net Core 系列:基于 T4 模板生成代码
目录简介组成部分分类Visual Studio 中使用T4模板1.创建T4模板文件2. 编写T4模板3. 转换模板中心控制Manager根据 MySQL 数据库生成实体 简介 T4模板,即Text Template Transformation Toolkit,是微软官方在Visual Studio
Asp .Net Core 系列:基于 T4 模板生成代码
从基础到高级应用,详解用Python实现容器化和微服务架构
本文分享自华为云社区《Python微服务与容器化实践详解【从基础到高级应用】》,作者: 柠檬味拥抱。 Python中的容器化和微服务架构实践 在现代软件开发中,容器化和微服务架构已经成为主流。容器化技术使得应用程序可以在任何环境中一致运行,而微服务架构通过将应用拆分成多个独立的服务,从而提升了系统的