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

按照我的想法，您只删除具有单个 child 的叶子或内部节点，并且您删除的任何内容的 children 都必须保持相同的水平。

这需要从上层拉下一个键来容纳它们，并与同级合并。

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

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

2-3-4 树删除操作

2-3-4 Tree Deletion Operation

data-structures

tree

b-tree