Когда дерево 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 разных дерева с одинаковыми элементами. Для дерева слева я вставил 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