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

Question

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

从下列树中删除15：

​

删除后的2-3-4树会是什么样子？我认为，在这种情况下，简单地上升17是不正确的。但我不太确定。

Answer 1

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

若要从2 34树中删除内部值，只需将要删除的值替换为它的下一个最大项，即它的顺序后继项( 17 )。这将删除的问题减少到从叶节点中删除值。因此，问题是，如何删除叶节点值？

当您从树的叶中删除时，如果是3节点或4节点，您只需删除该项。如果它是一个2节点，则该节点将为空。这就是所谓的底流。要解决此问题，必须将遇到的所有2节点转换为3节点或4节点.有三种情况您必须处理，取决于是否有一个相邻的兄弟姐妹是一个3节点或4节点，或它们是否都是2节点。这将在下面的链接中解释。

关于从树中删除的讨论，请参见幻灯片51至53：

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

[2]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