Какой правильный способ вставки в 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 значения, затем родитель будет разделяться.