第七章-DS-B树/B+树

DS-B树/B+树

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

思维导图

基本操作

原始状态
第七章-DS-B树/B+树_第1张图片

增考虑分裂

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

插入18

插入前第七章-DS-B树/B+树_第2张图片
插入后
第七章-DS-B树/B+树_第3张图片

删除考虑合并

当删除的关键字的结点的关键字总数>=⌈m/2⌉

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

删除前

第七章-DS-B树/B+树_第4张图片
删除36
删除后
第七章-DS-B树/B+树_第5张图片

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

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

删除前
第七章-DS-B树/B+树_第6张图片
删除35
删除后
第七章-DS-B树/B+树_第7张图片

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

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

删除前
第七章-DS-B树/B+树_第8张图片
删除33
删除后
第七章-DS-B树/B+树_第9张图片

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

  1. P275 T8
    在这里插入图片描述

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

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


  1. P275 T9
    在这里插入图片描述

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


3. P275 T10

第七章-DS-B树/B+树_第10张图片

题型为给出关键字个数,求结点数
这题为求结点数最多,那么就要每个结点的关键字最少
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

你可能感兴趣的