往该B树中插入关键码72后,该B树的叶结点数为 从该B树中删除关键码15后,该B树的叶结点数为

admin2009-01-27  19

问题 往该B树中插入关键码72后,该B树的叶结点数为
从该B树中删除关键码15后,该B树的叶结点数为

选项 A、5   
B、6
C、7   
D、8

答案A

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

最新回复(0)