数据结构和算法-B树(B树的查找 B树的最大高度和最小高度)

这篇具有很好参考价值的文章主要介绍了数据结构和算法-B树(B树的查找 B树的最大高度和最小高度)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

回顾:二叉查找树

数据结构和算法-B树(B树的查找 B树的最大高度和最小高度),王道数据结构和算法考研笔记,数据结构,算法,b树

五叉查找树

进一步对范围划分,处于不同划分进入不同子树
四个数做划分,此时有五个区间
此时一个节点对应多个关键字,如果叶子节点依然没有对应的关键字,那么即查找失败,然后看看在叶子节点的关键字的哪个区间
此时每个节点可以只有一个关键字,也可以有多个关键字,其对应的子树个数自然也就不同
数据结构和算法-B树(B树的查找 B树的最大高度和最小高度),王道数据结构和算法考研笔记,数据结构,算法,b树

如何查找

查找成功

9小于22,进入左子树,到左子树的根节点,此时比对关键字,可以顺序找,也可以折半找,此时没找到,但范围区间找到了,此时跳到三个子树的第二个子树上,再次顺序查找,发现找到对应的关键字,查找成功
数据结构和算法-B树(B树的查找 B树的最大高度和最小高度),王道数据结构和算法考研笔记,数据结构,算法,b树

查找失败

41大于22,首先到右子树去,比对关键字,在对应的第二个子树,进入该子树,再次比对关键字,此时进入对应的第二子树,但此时为空,所以没找到

数据结构和算法-B树(B树的查找 B树的最大高度和最小高度),王道数据结构和算法考研笔记,数据结构,算法,b树

如何保证查找效率

保证树越矮越好,那么比对次数也就更少
子树个数=关键字个数+1
数据结构和算法-B树(B树的查找 B树的最大高度和最小高度),王道数据结构和算法考研笔记,数据结构,算法,b树
子树高度都相同
数据结构和算法-B树(B树的查找 B树的最大高度和最小高度),王道数据结构和算法考研笔记,数据结构,算法,b树

B树

节点多路,然后各个节点的子树的高度都是平衡的,所以称为多路平衡查找树。
m阶B树可为空。此时没有节点
每个节点最多为m颗子树,最多m-1颗关键字
最少的话除根节点的子树最少可以为0,其次是2,如果为1,那么由于此时根节点的关键字含一个树,此时有两个分支,那么其中一个有高度,另一个没有高度,不符合B树的要求
其他节点最少为m/2向上取整。
数据结构和算法-B树(B树的查找 B树的最大高度和最小高度),王道数据结构和算法考研笔记,数据结构,算法,b树

此时叶节点都是空结点,终端节点不是空节点
非叶节点的结构即当关键字按从小到大排序时,比较关键字时若发现第一个Pi大于所寻找的关键字,那么此时对应的子树根节点为Ki

数据结构和算法-B树(B树的查找 B树的最大高度和最小高度),王道数据结构和算法考研笔记,数据结构,算法,b树
下面是简单概括
数据结构和算法-B树(B树的查找 B树的最大高度和最小高度),王道数据结构和算法考研笔记,数据结构,算法,b树

B树的高度

最小高度此时尽可能满,即从根节点开始,都有m个子树,此时每个节点有m-1个关键字。
每行的节点数目是m的次方,每个节点又有m-1个关键字,关键字总树为n
此时n对应上限的是满的m叉树,可以求h的最小值

数据结构和算法-B树(B树的查找 B树的最大高度和最小高度),王道数据结构和算法考研笔记,数据结构,算法,b树

此时最大高度对应的是分叉最少,此时最少根节点两个分叉,其他节点都是m/2向上取整个分叉

此时利用的是叶子节点的关系
为啥n个关键字的B树必有n+1个叶子节点,是因为此时可以想象一下B树的本质就是分区间,最后对应的区间全部都是落在叶子节点中的,所以说n个关键字的B树,必须有n+1个叶子节点

但此时高度最高的B树对应的叶子节点个数的下限其实为 如图中的第h+1层共有叶子节点……个,因为终端节点的关键字个数可以无限制增加的,
此时假设此时h为最高的B树的高度,那么此时高度最高的B树的除终端节点的节点的关键字数目必须为最小节点关键字总数,终端节点的关键字数目可以大于等于节点最小关键字总数。

所以高度为h的最高的B树,此时的叶子节点树最小就是图中等比得来的,最大得小于终端节点的关键字总数可以多到为此时等比得来得叶子节点的关键字的数模加上终端节点关键字数目,若等于,此时高度还可以增加了

所以此时关键字数目为n的对应的最高的高度为h的B树的叶子节点的关键字的数目一定是大于最高的高度为h的B树的叶子节点的最少数目(等比得来的)
数据结构和算法-B树(B树的查找 B树的最大高度和最小高度),王道数据结构和算法考研笔记,数据结构,算法,b树此时利用的是如果关键字总数小于当每个节点的关键字都是最少时构成的树的关键字总数的话,那么此时高度一定小于h,因为此时若依然为h,那么此时由于任何一个节点都不能有更少的关键字,所以失败。所以如果此时最大高度为h时,那么此时关键字总数一定大于高度为h当每个节点的关键字都是最少时构成的树的关键字总数
数据结构和算法-B树(B树的查找 B树的最大高度和最小高度),王道数据结构和算法考研笔记,数据结构,算法,b树

数据结构和算法-B树(B树的查找 B树的最大高度和最小高度),王道数据结构和算法考研笔记,数据结构,算法,b树

小结

B:balance。即左右子树平衡,高度一样嘛
数据结构和算法-B树(B树的查找 B树的最大高度和最小高度),王道数据结构和算法考研笔记,数据结构,算法,b树文章来源地址https://www.toymoban.com/news/detail-770495.html

到了这里,关于数据结构和算法-B树(B树的查找 B树的最大高度和最小高度)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言数据结构二叉排序树的建立、插入、删除、查找操作(原理+完整代码)

    1、若左子树不为空,左子树上所有节点值小于 它根节点的值 2、若右子树不为空,右子树上所有节点值大于 它根节点的值 3、每个节点的左右子树也是二叉排序树 目的:提高查找、插入、删除的速度(不是为了排序) 时间复杂度:由于查找性能取决于树的形态,所以

    2024年02月09日
    浏览(49)
  • Java学数据结构(2)——树Tree & 二叉树binary tree & 二叉查找树 & AVL树 & 树的遍历

    1.树的出现:解决链表线性访问时间太慢,树的时间复杂度O(logN); 2.二叉树的定义,最多两个儿子节点; 3.二叉查找树,左小,右大,中居中;remove方法,两种,只有一个儿子节点,有两个儿子节点; 4.AVL树,在二叉查找树基础上加平衡条件,旋转方法,单旋转,双旋转;

    2024年02月10日
    浏览(49)
  • Java数据结构与算法:查找算法之二分查找

    大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编,欢迎回到本专栏。在这个冰冷的季节里,我们将一同探讨Java中一种高效的查找算法——二分查找。让我们点燃知识的火花,一同解锁这个查找奇迹的秘密! 二分查找简介 二分查找,也称为折半查找,

    2024年01月21日
    浏览(47)
  • 数据结构算法--1 顺序查找二分查找

    顺序查找时间复杂度为O(n) 我们可以借助Python中的函数enumerate,通过enumerate遍历列表返回其索引和值 也可以通过列表长度依次遍历: 但是二分查找时间复杂度为O(logn):

    2024年02月12日
    浏览(54)
  • 数据结构--》掌握数据结构中的查找算法

            当你需要从大量数据中查找某个元素时,查找算法就变得非常重要。         无论你是初学者还是进阶者,本文将为你提供简单易懂、实用可行的知识点,帮助你更好地掌握查找在数据结构和算法中的重要性,进而提升算法解题的能力。接下来让我们开启数据

    2024年02月08日
    浏览(57)
  • 【数据结构(七)】查找算法

    在 java 中,我们常用的查找有四种:     ① 顺序(线性)查找     ② 二分查找/折半查找     ③ 插值查找     ④ 斐波那契查找 问题:     数组arr[] = {1, 9, 11, -1, 34, 89},使用线性查找方式,找出11所在的位置。 代码实现: 运行结果: 问题:     请

    2024年02月04日
    浏览(51)
  • 数据结构--6.3查找算法(静态、动态)(插值查找)

    静态查找:数据集合稳定,不需要添加,删除元素的查找操作。 动态查找:数据集合在查找的过程中需要同时添加或删除元素的查找操作。 对于静态查找来说,我们不妨可以用线性表结构组织数据,这样可以使用顺序查找算法,如果我们在对进行排序,则可以使用折

    2024年02月09日
    浏览(43)
  • 数据结构与算法:树形查找

    左子树结点值 根结点值 右子树结点值 对二叉排序树进行中序遍历,可以得到一个递增的有序数列 原理: 对于一个给定的二叉排序树,如果要查找一个节点,可以按照以下步骤进行: 从根节点开始比较。 如果要查找的值等于当前节点的值,则找到了目标节点,返回该节点。

    2024年02月06日
    浏览(44)
  • 数据结构与算法之查找: 顺序查找 (Javascript版)

    顺序查找 思路 遍历数组 找到跟目标值相等元素,就返回它的下标 没有找到,返回-1 算法实现 总结 非常低效,算是入门搜索 时间复杂度:O(n) 对于数组结构或链表结构而言,没什么太多可说的

    2024年02月05日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包