408|第七章-DS-B树/B+树数据结构|python|数据结构

DS-B树/B+树

思维导图
基本操作
- 增考虑分裂
- 删除考虑合并
- - 当删除的关键字的结点的关键字总数>=?m/2?
  - 当删除的关键字的结点关键字总数=?m/2?-1时
  - 如果当该结点的左右兄弟都不够借关键字时
习题题型归纳分析，理思路和过程

思维导图
基本操作

原始状态

文章图片

增考虑分裂

结点的关键字数>m-1就要分裂
该插入的关键字左边成为该关键字的左结点，右边的关键字成为该插入关键字的右结点，而该关键字上移

插入18

插入前
文章图片

插入后

文章图片

删除考虑合并当删除的关键字的结点的关键字总数>=?m/2?

即删除该关键字后剩余的关键字总数>=?m/2?-1
则直接删除

删除前

文章图片

删除36
删除后

文章图片

当删除的关键字的结点关键字总数=?m/2?-1时

如果该结点的兄弟够借
左结点/右结点的关键字总数>=?m/2?
如果借左结点，则该关键字结点的双亲下来，填充补位，左结点的最大最右的上取充当新的双亲关键字

删除前

文章图片

删除35
删除后

文章图片

如果当该结点的左右兄弟都不够借关键字时

即左右结点的关键字都是?m/2?-1
那么则要合并
删除该关键字后
该关键字的双亲与其还未删除的左结点/右节点的关键字进行合并

删除前

文章图片

删除33
删除后

文章图片

习题题型归纳分析，理思路和过程

P275 T8

文章图片

这题的总结在思维导图中有：题型位只给出m阶B树的高度
只给出高度，那么
①最少的节点就是每个节点的关键字最少，因为关键字最少的时候，其对应的分支数也最少，那么分出去的节点就最少
②最多的结点数就是每个节点的关键字最多，那么其对应的每个节点分支数就越多，那么分出去的节点就越多

这题3阶B树非根节点的非叶子节点最少的分支数为?m/2?=2，那么就相当于二叉树结点的计算，高度为5的结点数就为25-1=32
而最多的结点数位分支数最多=m=3，那么根据等比数列求和得，其结点数=(35-1)/(3-1)=121个
因此 B D

P275 T9

文章图片

这题的总结在思维导图中有：题型位只给出m阶B树的高度
关键字最少，在只给出高度的时候，结点数是最少的，因为分支数最少
5阶B树，非根节点的非叶子结点每个结点的最少关键字为?m/2?-1=2，分支数最少为=3
根结点的最少关键字为1，最少分支数=2
题目要求求关键字最少，那么根据归纳法求和即可
1+21 * 2=5个关键字
高度为2的结点数=1+2=3

3. P275 T10 【408|第七章-DS-B树/B+树】

文章图片

题型为给出关键字个数，求结点数
这题为求结点数最多，那么就要每个结点的关键字最少
4阶B树的每个结点的最少关键字为?m/2?-1=1，分支数最少为2,这题中最少的关键字数就是最少的结点数
就用总结归纳法：1*20+1 * 21+1 *22+1 *23=15
D

4. P276 T11 这题是考细节

文章图片

考点是：根节点的关键字最少是1，非根节点的非叶子结点最少关键字为?m/2?-1
因此求出非根节点的非叶子结点的关键字再加1，即是包含的最少关键字

文章图片

这题题型是是给出关键字，求高度
那么关键字的数目限定了，
最小的高度就是每个结点的关键字数目最多的时候，高度最小
最大的高度就是每个结点的关键字数目最少的时候，高度最大
5阶B树，根结点最少关键字1，最少分支=2
非根节点的非叶子结点最少关键字数=?m/2?-1=2，最少分支数=3
那么通过等比求和公式求其最大高度，通过最少分支数=3，相当于求三叉树
1 + 2*2+2 * (2 * (3(3h-2-1))/(3-1))>=53，那么h取4 因此最大高度为C
最小高度要求每个结点的关键字个数最多，那么5阶B树中每个结点的最多关键字个数=4（包括根节点）
那么通过等比数列求和公式得
4*(5h-1)/(5-1)>=53
因此h取3，因此最小高度为B

5. P276 T13

文章图片

这题和上一题一样的方法
3阶B树，根节点最少1个关键字，2个分支，最多2个关键字，3个分支
非根节点的非叶子结点最少1个关键字，2个分支，最多2个关键字，3个分支
最大高度：每个结点最少关键字
就类比求二叉树了求最大高度，2h-1/(2-1)>=2047 h取11 ,所以为A

最小高度：每个结点最多关键字
2 * (3h-1)/(3-1)>=2047
最小高度为7，所以为D