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

文章目录

回顾：二叉查找树

在这里插入图片描述

五叉查找树

进一步对范围划分，处于不同划分进入不同子树
四个数做划分，此时有五个区间
此时一个节点对应多个关键字,如果叶子节点依然没有对应的关键字，那么即查找失败，然后看看在叶子节点的关键字的哪个区间
此时每个节点可以只有一个关键字，也可以有多个关键字，其对应的子树个数自然也就不同
在这里插入图片描述

如何查找

查找成功

9小于22，进入左子树，到左子树的根节点，此时比对关键字，可以顺序找，也可以折半找，此时没找到，但范围区间找到了，此时跳到三个子树的第二个子树上，再次顺序查找，发现找到对应的关键字，查找成功
在这里插入图片描述

查找失败

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

在这里插入图片描述

如何保证查找效率

保证树越矮越好，那么比对次数也就更少
子树个数=关键字个数+1
在这里插入图片描述
子树高度都相同
在这里插入图片描述

B树

节点多路，然后各个节点的子树的高度都是平衡的，所以称为多路平衡查找树。
m阶B树可为空。此时没有节点
每个节点最多为m颗子树，最多m-1颗关键字
最少的话除根节点的子树最少可以为0，其次是2，如果为1，那么由于此时根节点的关键字含一个树，此时有两个分支，那么其中一个有高度，另一个没有高度，不符合B树的要求
其他节点最少为m/2向上取整。
在这里插入图片描述

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

在这里插入图片描述
下面是简单概括
在这里插入图片描述

B树的高度

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

在这里插入图片描述

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

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

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

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

所以此时关键字数目为n的对应的最高的高度为h的B树的叶子节点的关键字的数目一定是大于最高的高度为h的B树的叶子节点的最少数目（等比得来的）
在这里插入图片描述此时利用的是如果关键字总数小于当每个节点的关键字都是最少时构成的树的关键字总数的话，那么此时高度一定小于h，因为此时若依然为h，那么此时由于任何一个节点都不能有更少的关键字，所以失败。所以如果此时最大高度为h时，那么此时关键字总数一定大于高度为h当每个节点的关键字都是最少时构成的树的关键字总数
在这里插入图片描述

在这里插入图片描述

小结

B：balance。即左右子树平衡，高度一样嘛
在这里插入图片描述