data-structures - 插入 2-3 树的正确方法是什么？

Question

我的班主任给了我一个问题，要求我在 2-3 树中执行插入操作。

我做的是上层方法。而他想要的是下面的方法。你能告诉我哪种方法是正确的，因为我在网上查看过，我可以在那里看到这两种方法。但是我还是不知道为什么我掉了10分！提前感谢您的帮助。

Answer 1

让我首先说 2-3 棵树有很多不同的版本，所以可能会造成混淆。实际上，它们仅在存储值的方式上有所不同。有些只将值存储在叶子中，而另一些则将值存储在每个节点中。

我相信你的老师正在使用 2-3 棵树的后一种定义。所以你的树的问题是“根”节点与它的子节点具有相同的值，一个节点永远不会与它的子节点共享相同的值。虽然，我不认为你的老师提供的是真正的 2-3 树。当一个节点包含 3 个值时，一个 2-3 树将分裂。我希望下面是正确的输出：

将 4 添加到树：

(4)

将 7 添加到树：

(4,7)

将 6 添加到树中：

(4,6,7)
*splits*
  (6)
(4) (7)

一旦根节点获得 3 个值，它就会分裂成一棵 1-2 树。

如果要插入 8：

  (6)
(4) (7,8)

如果要插入 9：

   (6)
 (4) (7,8,9)
 *push-up*
   (6,8)
(4) (7) (9)

当一个非根节点得到 3 个值时；将中间值向上推到父级，如果向上推该值使父级具有 3 个值，则父级将分裂。