2-3-4删除树操作

Question

如果2-3-4树的结构如下，如何从树中删除节点1：

            4      10
        /       |       \
      2        6,8      12,14 
    /  \     /  |  \   /   |   \
   1   3    5   7  9  11  13   15

Answer 1

在我看来，您只需删除具有单个子节点的叶子或内部节点，而您删除的任何子节点的子节点都必须保持相同的级别。

这需要从上面的级别向下拉出一个关键点来容纳它们，它与同级项合并。

如果父级只有一个键，这将导致级联删除。

Deleting 1 by pulling down 2 causes a cascaded delete:
     
      4 ,  10
  /     |      \
 X     6,8      12,14
 |    / | \     / |  \
2,3  5  7  9  11  13  15

The cascaded delete pulls down the 4:
     
           10
         /    \
    4,6,8      12,14
   / | | \     / |  \
2,3  5 7  9  11  13  15

如果同级项太大而无法合并，则可能需要从同级项重新分发。如果这是一个2-3的树，这将是必需的，例如：

Redistributing a key from 6,8
     
        6  ,  10
     /     |      \
    4      8      12,14
   / \    / \     / |  \
2,3   5  7   9  11  13  15