algorithm - 为什么插入2-3-4树时节点分裂？

Question

在下面描绘的2-3-4 树中（来自Java 中的数据结构和算法，第 2 版），为什么插入99会导致节点分裂，83/92/104因为它似乎99可以插入到正确的孩子（C孩子，进入紧接在97) 之后没有任何拆分？

Answer 1

将 99 插入 C 是可以的，因为它将保持所有不变量，但如果插入总是在向下的过程中扩展 4 个节点，则算法通常更简单。然后总会有空间进行任何需要的提升和旋转。比较 C 本身已经是 4 节点的情况可能会有所帮助。

Answer 2

保持树平衡，保证性能。插入是递归的，它会命中一个 4 节点（具有 3 个值和 4 个子节点的节点），这将导致拆分完成。