如何从这棵 2-4 树（底部的树）中删除 26？

Question

我有这 2-4 棵树：

如何从这棵 2-4 树（底部的树）中删除 26？

我最大的问题是它的前任和后继都是 2 个节点，将它们中的任何一个替换为 26 都会使叶节点为空，或者在这么小的东西中可以这样做吗？或者我是否必须将 10、26 和 54 合并为叶节点？我将不胜感激任何帮助。

我主要尝试用 26 代替 10，但不确定从哪里开始，所以我最大的理论是将 26 与前任和后任合并。

Answer 1

你一开始就已经把事情搞混了。值 26 决不允许出现在 60 的right处。

让我们从头开始，执行以下操作：

• 添加：25 29 60 26 79 93 68 32 64 10
• 删除：25 29 60 26

添加 25 29 60 之后我们只有一个根节点：

    ┌────┬────┬────┐
    │ 25 │ 29 │ 60 │
    └────┴────┴────┘

在添加 26 之前，我们需要先分割根节点：

         ┌────┐
         │ 29 │
         ├────┤
       ┌─┘    └─┐
    ┌──┴─┐    ┌─┴──┐
    │ 25 │    │ 60 │
    └────┘    └────┘

现在我们可以添加 26、79 和 93：

              ┌────┐
              │ 29 │
              ├────┤
         ┌────┘    └──────┐
    ┌────┼────┐    ┌────┬─┴──┬────┐
    │ 25 │ 26 │    │ 60 │ 79 │ 93 │
    └────┴────┘    └────┴────┴────┘

在添加 68 之前，我们需要分割已满的叶子：

              ┌────┬────┐
              │ 29 │ 79 │
              ├────┼────┤
         ┌────┘    │    └──┐
    ┌────┼────┐  ┌─┴──┐  ┌─┴──┐
    │ 25 │ 26 │  │ 60 │  │ 93 │
    └────┴────┘  └────┘  └────┘

现在我们可以添加 68 和 32：

                    ┌────┬────┐
                    │ 29 │ 79 │
                    ├────┼────┤
         ┌──────────┘    │    └───────┐
    ┌────┼────┐  ┌────┬──┴─┬────┐  ┌──┴─┐
    │ 25 │ 26 │  │ 32 │ 60 │ 68 │  │ 93 │
    └────┴────┘  └────┴────┴────┘  └────┘

在添加 64 之前，我们需要分割已满的叶子：

                 ┌────┬────┬────┐
                 │ 29 │ 60 │ 79 │
                 ├────┼────┼────┤
         ┌───────┘   ┌┘    └┐   └────┐
    ┌────┼────┐   ┌──┴─┐  ┌─┴──┐  ┌──┴─┐
    │ 25 │ 26 │   │ 32 │  │ 68 │  │ 93 │
    └────┴────┘   └────┘  └────┘  └────┘

现在我们可以将 64 和 10 相加：

                      ┌────┬────┬────┐
                      │ 29 │ 60 │ 79 │
                      ├────┼────┼────┤
            ┌─────────┘  ┌─┘    └──┐ └────────┐
    ┌────┬──┴─┬────┐  ┌──┴─┐  ┌────┼────┐  ┌──┴─┐
    │ 10 | 25 │ 26 │  │ 32 │  │ 64 │ 68 │  │ 93 │
    └────┴────┴────┘  └────┘  └────┴────┘  └────┘

然后是拆除。我们可以在不合并的情况下删除 25 个：

                 ┌────┬────┬────┐
                 │ 29 │ 60 │ 79 │
                 ├────┼────┼────┤
         ┌───────┘  ┌─┘    └──┐ └────────┐
    ┌────┼────┐  ┌──┴─┐  ┌────┼────┐  ┌──┴─┐
    │ 10 | 26 │  │ 32 │  │ 64 │ 68 │  │ 93 │
    └────┴────┘  └────┘  └────┴────┘  └────┘

要删除 29 有几种可能性：

• 我们可以删除它的后继 (32)，将该值移动到根以替换 29，然后需要旋转：

  • 从左兄弟开始旋转，向根移动 26，向下移动 32，或者
  • 从右同级开始旋转，将 64 移至根部并向下移 32

• 我们可以删除其前身 (26)，将该值移动到根以替换 29。不需要旋转。请注意，结果与上面第一个子选项相同。让我们采取这个选项，所以我们得到：

            ┌────┬────┬────┐
            │ 26 │ 60 │ 79 │
            ├────┼────┼────┤
       ┌────┘  ┌─┘    └──┐ └────────┐
    ┌──┴─┐  ┌──┴─┐  ┌────┼────┐  ┌──┴─┐
    │ 10 │  │ 32 │  │ 64 │ 68 │  │ 93 │
    └────┘  └────┘  └────┴────┘  └────┘

要删除 60，我们可以再次从多个选项中进行选择。在这种情况下，我将删除其后继者，将 64 向上移动以替换 60：

           ┌────┬────┬────┐
           │ 26 │ 64 │ 79 │
           ├────┼────┼────┤
       ┌───┘   ┌┘    └┐   └────┐
    ┌──┴─┐  ┌──┴─┐  ┌─┴──┐  ┌──┴─┐
    │ 10 │  │ 32 │  │ 68 │  │ 93 │
    └────┘  └────┘  └────┘  └────┘

最后，我们需要删除 26。通常我们会用它的后继 32 来替换 26。但这里我们处于维基百科上描述的案例#3，其中涉及首先与父密钥融合成 4 节点。如果我们选择最左边的两片叶子进行融合，树就会变成这样：

                ┌────┬────┐
                │ 64 │ 79 │
                ├────┼────┤
            ┌───┘    └──┐ └──────┐
    ┌────┬──┴─┬────┐  ┌─┴──┐  ┌──┴─┐
    │ 10 │ 26 │ 32 │  │ 68 │  │ 93 │
    └────┴────┴────┘  └────┘  └────┘

...现在我们可以从叶子中删除 26 了：

             ┌────┬────┐
             │ 64 │ 79 │
             ├────┼────┤
         ┌───┘    └┐   └────┐
    ┌────┼────┐  ┌─┴──┐  ┌──┴─┐
    │ 10 │ 32 │  │ 68 │  │ 93 │
    └────┴────┘  └────┘  └────┘

就是这样。