algorithm - 删除 2-3-4 树中的一个内部节点

Question

我想从下面的 2-3-4 树中删除 15。我想简单地将 17 向上移动，但我不知道这是否正确，因为它必须是完整的。

从以下树中删除 15:

删除后的 2-3-4 树会是什么样子？我假设在这种情况下简单地向上移动 17 是不正确的。但我不太确定。

Answer 1

您拥有的树不是有效的 2 3 4 树，因为它有一个重复的 6。

要从 2 3 4 树中删除一个内部值，您只需将要删除的值替换为它的下一个最大项，它的顺序后继项，即 17。这减少了删除问题，删除一个值来自叶节点。那么问题来了，如何删除一个叶子节点的值呢？

当您从 2 3 4 树的叶子中删除时，如果它是 3 节点或 4 节点，您只需删除该项目。如果它是 2 节点，则该节点为空。这称为下溢。要解决此问题，您必须将遇到的所有 2 节点转换为 3 或 4 节点。您必须处理三种情况，具体取决于是否有相邻的兄弟节点是 3 节点或 4 节点，或者它们是否都是 2 节点。这在下面的链接中进行了解释。

有关从 2 3 4 树中删除的讨论，请参阅幻灯片 51 到 53:

http://www.serc.iisc.ernet.in/~viren/Courses/2009/SE286/2-3Trees-Mod.ppt

2 3 4 删除(和插入)也在以下位置进行了解释和说明:

• http://www.cs.toronto.edu/~krueger/cscB63h/lectures/tut04.txt
• http://www.cs.ubc.ca/~liorma/cpsc320/files/B-trees.pdf

有关实现 2 3 4 树(在 C++11 中)的源代码，请参阅:

http://cplusplus.kurttest.com/notes/tree234.html