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

Question

我刚刚在我正在使用的数据结构教科书中看到这个问题，问题是

Give an example to show that the following claim is wrong: "A 2-3-4 tree storing a set of entries will always have the same structure, regardless of the order in which the entries are inserted."

我知道最好的情况是 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

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

When would a 2-3-4 tree not have the same structure?

java

data-structures

2-3-4-tree