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

Question

在下面描述的2-3-4树中(来自Java中的数据结构和算法,第2版),为什么插入99会导致节点分裂,83/92/104当它看起来像是99已经被插入到正确的孩子(C孩子,进入紧接着发现97)没有任何分裂吗？

Answer 1

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