data-structures - 插入 2-3-4 树

Question

考虑下面的 2-3-4 树（即最小度数为 2 的 B 树），其中每个数据项都是一个字母。通常的字母顺序用于构建树。

在上面的树中插入 G 的结果是什么？

我得到的答案是

但解决方案关键的答案是

谁能解释如何获得解决方案密钥提供的答案？

Answer 1

只要不违反不变量，该操作在技术上是有效的。CLRS 中的插入算法在向下的过程中分裂，所以它会像你一样分裂根。

但是，另一种实现可能会观察到第二个孩子是空的，而第一个孩子是满的。这意味着可以完成“旋转”并且根节点数不受影响。旋转包括将 L 向下推入第二个孩子（前置）并将 I 向上拉到 L 在根中的先前位置。现在第一个孩子只有两个条目，您可以插入其中。

使用您使用的 CLRS 方法进行动画插入