0

我刚刚在我正在使用的数据结构教科书中看到这个问题被问到了，问题就出来了

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

我知道最好的情况是 O(log n)，它比使用 BST 更好，但仅此而已，我似乎找不到合理的解释。如何证明这种说法是错误的？

4

1 回答 1

0

如果你制作一棵树，有些叶子是满的，有些叶子没有，那么你放置下一个节点的位置决定了另一个叶子是否会分裂。

因此，如果我们从插入 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
于 2016-07-08T13:44:56.773 回答