专栏首页大前端当Kotlin遇见数据结构丨数据结构之树结构概述(含满二叉树、完全二叉树、平衡二叉树、二叉搜索树、红黑树、B-树、B+树、B*树)

当Kotlin遇见数据结构丨数据结构之树结构概述(含满二叉树、完全二叉树、平衡二叉树、二叉搜索树、红黑树、B-树、B+树、B*树)

1. 树结构示意图

补充:

  • 兄弟节点:具有相同父节点的节点互称为兄弟节点。
  • 树的深度:从根节点开始(其深度为0)自顶向下逐层累加的。上图中,3的深度是1,6的深度是2,10的深度是3。
  • 节点高度:从叶子节点开始(其高度为0)自底向上逐层累加的。6的高度是1,根节点1的高度是3。

2. 二叉树(Binary Tree)

  • 任何一个节点的子节点数量不超过2(子节点分为左节点与右节点)。
2.1 满二叉树(Full Binary Tree)
  • 所有叶子结点都在最后一层
  • 节点的总数为2^n-1 (n为树的高度)。
2.2 完全二叉树(Complete Binary Tree)
  • 所有叶子结点都在最后一层或倒数第二层。
  • 最后一层的叶子结点在左边连续,倒数第二节的叶子结点在右侧连续。
2.3 平衡二叉树(Balanced Binary Tree)
  • 也叫 AVL 树。
  • 它是一颗空树或左右两个子树的高度差的绝对值不超过1。
  • 左右两个子树均为平衡二叉树。
2.4 二叉搜索树(Binary Search Tree)
  • 也叫二叉查找树、二叉排序树。
  • 若子树不空,则子树上所有节点的值均小于或等于根节点的值。
  • 若右子树不空,则右子树所有节点的值均大于或等于根节点的值。
  • 左、右子树也分别为二叉排序树,或是一颗空树。
2.5 红黑树(Red Black Tree)
  • 每个节点都带有颜色属性(颜色为红或黑)的平衡二叉查找树。
  • 节点是红色或黑色。
  • 根节点是黑色。
  • 所有叶子结点都是黑色。
  • 每个红色节点必须有两个黑色的子节点(从每个叶子到根的所有路径上不能有两个连续的红色节点)。
  • 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

3. B 树

B-tree(多路搜索树,并不是二叉的)是一种常见的数据结构。使用B-tree结构可以显著减少定位记录时所经历的中间过程,从而加快存取速度。按照翻译,B 通常认为是Balance的简称。这个数据结构一般用于数据库的索引,综合效率较高。

3.1 B- 树

B-树 就是指 B树,也是一种用于查找的平衡树,但是它不是二叉树,B树可以拥有多于2个子节点,能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作,都在对数时间内完成。这种数据结构常被应用在数据库和文件系统的实作上。

  • 定义任意非叶子结点最多只有M个儿子;且M>2。
  • 根结点的儿子数为[2, M]。
  • 除根结点以外的非叶子结点的儿子数为[M/2, M]。
  • 每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)。
  • 非叶子结点的关键字个数=指向儿子的指针个数-1。
  • 非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1]。
  • 非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树。
  • 所有叶子结点位于同一层。
3.2 B+ 树

B+树 是 B树 的变体,也是一种多路搜索树

  • 其定义基本与B-树相同,除了:
  • 非叶子结点的子树指针与关键字个数相同。
  • 非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间)。
  • 为所有叶子结点增加一个链指针。
  • 所有关键字都在叶子结点出现。

特性:

  1. 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的。
  2. 不可能在非叶子结点命中。
  3. 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层。
  4. B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针。
  5. 更适合文件索引系统。
3.3 B* 树

是 B+树 的变体,在 B+树 的非根和非叶子结点再增加指向兄弟的指针

特性:

  1. B*树定义了非叶子结点关键字个数至少为(2/3)M,即块的最低使用率为2/3(代替B+树的1/2)。
  2. B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针。

所以,B*树分配新结点的概率比B+树要低,空间使用率更高。


本篇到此完结,如有补充内容随时更新!欢迎关注本人继续跟进技术干货的更新!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Kotlin Array 创建、增、删、改、查、插入

    码脑
  • Flutter跨平台移动端开发丨Widget、Element、State、状态管理

    widget 的主要工作是通过实现 build 函数 来构建自身。一个 widget 通常由一些低级别的 widget 组成,flutter 框架依次的构建这些...

    码脑
  • 计算机网络原理梳理丨物理层

    消息:人类能够感知的描述 信息:对事物的存在状态或存在方式的不确定性表述,可度量 通信:本质是在一点精确或近似地再生另一点的信息 通信系统:能够实现通信功...

    码脑
  • 数据结构简单要点总结(转)

    栈是只能在一端进行插入和删除的线性表。 (别看只是个定义,非常重要,已经道出了运算方法:只能在一端插入和删除。)

    Locker
  • 《大话数据结构》(二)

    1.树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中:(1)有且仅有一个特定的称为根(Root)的结点;(2)当n>1时,其余...

    硬核项目经理
  • 4.5.3 哈弗曼树(Huffman)树和哈弗曼编码

    树中结点被赋予一个表示某种意义的数值,称为该结点的权。从树根结点到任意结点的路径长度(经过的边数)与该结点上权值的乘积称为该结点的带权路径长度。树中所有叶结点的...

    week
  • 每天一算:二叉树的中序遍历

    下面这种写法使用了一个辅助结点p,这种写法其实可以看作是一个模版,对应的还有前序和后序的模版写法,形式很统一,方便于记忆。上篇更新前序的和后面要更新后序文章中都...

    五分钟学算法
  • 经典数据结构 [ B树,B+树 ]+B树的应用

    关于B树的原理和实现方法,我也是研究了好久才看明白的,没明白之前感觉一脸懵逼,看懂后才发现原来也很简单。所以同学们要是发现很难看懂的情况下,不要烦躁着急,可以先...

    用户1149268
  • 数据结构之树、森林和二叉树的转换

    树转换为二叉树 (1)加线。在所有兄弟结点之间加一条连线。 (2)去线。树中的每个结点,只保留它与第一个孩子结点的连线,删除它与其它孩子结点之间的连线。...

    大黄大黄大黄
  • 请你对Java中树的了解有多少?

    树 1200101班的学生信息表如图6.1所示,其中学生被分到了不同的学习小组,第一组组长是李华,组员有王丽、张阳、赵斌; 第二组组长是孙琪,组员有马丹; 第三...

    Java学习

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动