题4

题4

题目

Q:在一棵 阶 B 树中做插入操作前，若一个结点中的关腱字个数等于 ( ) , 则插入操作后必须分裂成两个结点;
在一棵 阶 树中做删除操作前,若一个结点中的关键字个数等于 ( ) ,则删除操作后可能需要同它的左兄弟或右兄弟结点合并成一个结点.
A.
B.
C.
D.

分析

A:每个结点中最多可以容纳的关键字个数为 , 插入操作前若一个结点中的关键字个数等于 , 则插入操作后必须分裂成两个结点
关键字的数量问题，在题7中也有涉及
B树的操作分为两步
第一步是判断删除的是否是叶子结点，如果是叶子结点，那么直接删除，如果不是叶子结点，就来到第二步
第二步，找到删除的关键字的前驱或者后继，它在B树中，一定是叶子结点，问题转化为第一步的操作，是一个递归，然后替换删除的关键字，这和二叉排序树-aw的删除操作是类似的，也就是要找左子树的最大值或者右子树的最小值

因为每个结点至少有 个关键字，删除操作前若一个结点中的关键字个数等于 ,则删除操作后可能需要同它的左兄弟或右兄弟结点合并成一个结点，也就是下溢出

解

B
由于 树每个结点内的关键字个数最多为 ,所以当关键字个数大于 时,则应该分裂。
每个结点内的关键字个数至少为 个,所以当关键字个数少于 时,则可能与其他结点合并 (除非只有根结点)。
若将本题题干改为 树,请读者思考上述问题的解答。