DS-B树/B+树
思维导图
基本操作
原始状态
增考虑分裂
结点的关键字数>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
题型为给出关键字个数，求结点数
这题为求结点数最多，那么就要每个结点的关键字最少
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