Какой правильный метод вставки в 2-3 дерева?

Question

Мой учитель дал мне вопрос, чтобы выполнить вставку в 2-3 дерева.

То, что я сделал, было верхним методом. И что он хотел, так это метод ниже. Можете ли вы сказать мне, какой метод правильный, когда я смотрел в Интернете, и я могу увидеть оба метода там. Но я до сих пор не знаю, почему я потерял 10 баллов! Заранее спасибо за помощь.

Answer 1

Позвольте мне начать с того, что существует много разных версий 2-3 деревьев, так что это может сбить с толку. На самом деле они отличаются только по способу хранения ценностей. Некоторые хранят значения только в листах, а другие хранят значения в каждом узле.

Я считаю, что ваш учитель использует последнее определение 2-3 дерева. Таким образом, проблема с вашим деревом состоит в том, что "корневой" узел имеет те же значения, что и его дочерние элементы, узел никогда не будет иметь те же значения, что и его дочерние элементы. Хотя, я не думаю, что то, что поставил твой учитель, тоже является настоящим деревом 2-3 Дерево 2-3 расколется, когда узел содержит 3 значения. Я ожидаю, что ниже будет правильный вывод:

Добавьте 4 к дереву:

(4)

Добавьте 7 к дереву:

(4,7)

Добавьте 6 к дереву:

(4,6,7)
*splits*
  (6)
(4) (7)

Как только корневой узел получает 3 значения, он разделяется на 1-2 дерева.

Если бы вы должны были вставить 8:

  (6)
(4) (7,8)

Если вы должны были вставить 9:

   (6)
 (4) (7,8,9)
 *push-up*
   (6,8)
(4) (7) (9)

Когда некорневой узел получает 3 значения; подтолкнуть среднее значение до родительского, если при увеличении значения у родителя будет 3 значения, то родительский разделится.