data-structures - 从 B 树中插入和删除

Question

我遇到过这个问题，无法回答。

给定一个 9 阶和 4 层的 B-tree 将插入，并且在它删除一个新项目之后 x 总是将树带到它的第一个结构？

删除和插入现有项目 x 是否总是将树带到它的第一个结构？证明给我看。

到目前为止，我试图反驳它，但无法反驳。现在我真的找不到答案，我并不是要一个完整的证据，一个关于如何证明它会让我满意的一般想法。

Answer 1

答案显然取决于插入和删除方法的实现，但简而言之：不。

我不会给你一个完整的证明（因为你没有要求它，因为我太懒了）但一般的想法应该是通常当你删除一个节点时，对面的最里面的节点（相对给父母）取而代之。因此，在该节点存在的任何情况下，它都会向上移动。这也意味着该节点不是叶子，这是一个问题，因为插入通常会将新节点作为叶子放在树上。因此，只有当对面（相对于父节点）最里面的节点为空时，才会保持原始结构。

这是我指的删除。如果您删除 2 并重新插入它，那就是反证。