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