什么时候2-3-4树不具有相同的结构？

Question

我刚看到这个问题被问在我使用的数据结构和教科书问题去

举一个例子来表明，以下说法是错误的：“2-3-4树存储无论条目插入的顺序如何，条目集总是具有相同的结构。“

我知道最好的情况是O（log n），它比使用BST更好，但这是关于它，我似乎无法找到合理的解释。这个陈述怎么可能被证明是错误的？

Answer 1

如果您制作了一些树叶满叶和一些树叶，那么您放置下一个节点的位置决定了是否会分割另一叶子。

因此，如果我们通过插入2,3,4,5开始，那么根将分裂成2个叶子的新根。一个将有2个值和一个将有1。然后我们插入1,6，和那些叶子的一个必满：

 3 
    /\ 
    1,2 4,5,6 

现在，如果我们插入0，什么都不会分裂，但如果把它插入7 ，右叶会分裂。

实际的数字并不重要，当然，插入顺序与它们的排序顺序有什么关系，所以我们可以使这两个不同的树具有相同的元素。对于左侧的树，我插入了2,3,4,5,1,6,7，而对于右侧的我插入3,4,5,6,2,7,1

 3,5    4 
    /| \  / \ 
    1,2 4 6,7  1,2,3 5,6,7