Как разбить узел при вставке в 2-3-4 дерева?

Question

Есть ли правило, как разделить узел в дереве 2-3-4?

E.g. Если я вставляю 3, 7, 4, 9 в дерево 2-3-4:

Будет ли раскол, как это (желтый), или (зеленый), как показано здесь:

Действительно ли они действительны?

Answer 1

Зеленый. Вам нужно рассмотреть шаги алгоритма. Посмотрите на the wikipedia page для шагов ввода. Ключевой частью является разделение 4-узла (который имеет 3 значения), перемещая среднее значение до уровня, прежде чем рассматривать следующую вставку.

1. Insert 3 into blank. Result: 3   (a 2-node) 
2. Insert 7.   Result: 3 - 7  (a 3-node) 
3. Insert 4.   Result: 3 - 4 - 7 (a 4-node) 
5. Insert 9. There is already a 4-node, so this must be split. 
    The split will be to move 4 up a level, and 3 and 7 are now child nodes of 4 
    (like your green diagram). 9 is then added next to the 7.