(13)从该 B 树中删除关键码 15 后,该B 树的叶结点数为( )。 A)5 B)6 C)7 D)8

Question

（13）从该 B 树中删除关键码 15 后，该B 树的叶结点数为（ ）。

A）5

B）6

C）7

D）8

Answer 1

正确答案：A

（13）【答案】A)
【解析】当从B树中删除一个关键字Ki时，一段有以下两种情况。
1） 如果该关键字所在的结点不是最下层的非叶子结点，则先需要把此关键字与它在B树中的后继对换位置，即以指针Pi所指子树中的最小关键字Y代替Ki，然后在相应的结点中删除Y。
2） 如果该关键字所在的结点正好是最下层的非叶子结点，在这种情况下赊有以下两种可能:
①,若该关键字Ki所在结点中的关键字个数不小于[m/2],则直接从该结点中删除该关键字和相应指针即可。
②若该关键字Ki所在结点中的关键字个数小于[m/2],则直接从该结点中删除该关键字会导致结点中所含关键字个数小于[m/2]-1。在这种情况下，需考察该结点在B树中的左或右兄弟结点，从兄弟结点中移若干个关键字到该结点中来（这也涉及它们的双亲结点中的一个关键字要作相应的变化），使两个结点中所含关键字个数基本相同，但如果其兄弟结点的关键字个数也很少，刚好等于[m/2]-1，这种移动则不能进行，这种情形下，需要把删除了关键字Ki的结点、它的兄弟结点及它们本题情况属于②，所以选择A)