algorithm - 在 B-Tree 中寻找继任者

Question

我之前发布了一个关于在平衡二叉搜索树中寻找后继的问题。现在我正在阅读 B-Trees（其中节点可以有超过 2 个子节点），这让我想知道如何在 B-Tree 中找到一个键的继承者？它通常与常规 BST 相同吗？

提前致谢。

Answer 1

逻辑类似，但需要稍作修改以处理可能有多个孩子的事实。

和以前一样，查找该值。然后，如果块中有任何值大于该值，则找出其中的最小值。如果这些值之间的子树中有任何子树，则下降到该子树并在那里取最小值。否则，将后继值作为您在第一步中找到的值。

如果没有后继者，则在树中备份，直到有后继者为止。然后，使用上述过程获得后继者。

希望这可以帮助！