2. 考研
  3. 设有3阶B一树，如图1-4所示。 在该B一树上依次插入关键字33和97。试画出两次插入后的B-树。

设有3阶B一树，如图1-4所示。 在该B一树上依次插入关键字33和97。试画出两次插入后的B-树。

admin2014-04-17  81
问题 设有3阶B一树，如图1-4所示。

在该B一树上依次插入关键字33和97。试画出两次插入后的B-树。
选项
答案插入33：第一步需要定位，33应该被插入35和41的那个叶子结点。由于该叶子结点没有了空位置(怎么检测是否有空位置?m阶B-树最多只能有m-1个关键字)，所以需要进行分裂操作。插入后的情况应该是35、41、33，那么怎么分裂?首先需要取一个新结点，把原结点上的关键字按照升序排列，即33、35、41。从中间位置(即[m／2]之处)把关键字(不包括中间位置的关键字)分成两部分，左部分所含的关键字放在旧结点中，右边所含的关键字放在新结点中，中间位置的关键字连同新结点的存储位置插入到双亲结点中，如图1一11所示。 [*] 如果双亲结点的关键字个数也超过分支数减1，则要再分裂，再往上插，直至这个过程传到根结点为止。从以上步骤可以得出插入33之后的B一树，如图1-12所示。 [*] 可能疑问点：结点下面的小方块都是什么? 提示：小方块就是叶子结点，因为叶子结点本身不带有信息，所以有些教材都不画出来，但是叶子结点这一层一定要计入树的高度。另外，叶子结点一般也被认为外部结点(类似于折半查找判定树的外部结点)或是查找失败的结点。 插入97：过程与上面的一样，最终结果如图1-13所示。[*]
解析
转载请注明原文地址:https://kaotiyun.com/show/Jixi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)