Вставка элемента в 2-3-дерево

Как обычно, сначала находим место, куда необходимо вставить новый элемент, двигаясь по пути поиска, как описано выше. Пусть мы уже спустились на уровень, непосредственно предшествующий листьям, и стоим в узле node. Далее возможны два варианта действий.

Если узел node имеет два сына, то делаем новый элемент третьим, помещая его в правильном порядке среди других сыновей, и изменяем значения ключей в родителе node. Например, на рис.5.15 показано добавление элемента с ключом 18, к дереву ни рис.5.14. Больше никаких преобразований структуры не требуется, поскольку сбалансированность дерева не нарушена. Это простой случай.

Рис. 5.15 Вставка элемента 18 в 2-3 дерево.

Второй случай сложнее. Если узел node уже имеет трёх сыновей, то новый добавляемый элемент становится четвертым сыном. Но четырех сыновей ни у одного узла 2-3 дерева быть не может. Поэтому выполняется операция, называемая расщеплением. Узел node раcщепляется на два узла node и node'. Два наименьших элемента из четырёх становятся сыновьями узла node, два наибольших – сыновьями узла node'. Теперь нужно вставить узел node' среди сыновей узла p – родителя узла node. Здесь ситуация аналогичная. Если p имеет два сына, то node' становится третьим и помещается непосредственно справа от node. Если узел p уже имеет трёх сыновей, то он расщепляется на да узла p и p', узлу p приписываются два наименьших сына, узлу p' – оставшиеся. Затем вставляем узел p' среди сыновей родителя узла p и т.д.

На рис.5.16 показан первый этап вставки элемента 10 в 1-2 дерево из рис.5.15, на котором произошло расщепление узла с ключами 8 и 12 на два узла. В полученном дереве корень имеет четырех сыновей, следовательно, потребуется расщеплять корень. 

Рис.5.16. Вставка элемента 10 в 2-3 дерево — первый этап

В этой ситуации создаётся новый корень, чьими сыновьями будут два узла, полученные в результате разбиения старого корня. При этом число уровней дерева увеличивается на 1. Обратим внимание, что это единственная ситуация, когда высота дерева увеличивается, но сбалансированность не нарушается— все пути от корня до любого листа по-прежнему имеют одинаковую длину (рис.5.17).

Рис.5.17. Вставка элемента 10 в 2-3 дерево — 2 этап (расщепление корня.)

Но в данной ситуации можно было бы обойтись без расщепления корня, если выполнить еще одну операцию над 2-3 деревьями, которая называется переливанием. Так, из рис.5.16 можно догадаться, что от одного из сыновей корня (это второй сын с ключом 8) можно избавиться, передав его первого сына левому брату, а второго сына— правому брату. Это возможно, поскольку у каждого брата только по два сына. Результат показан на рис.5.18.

Рис.5.18. Вставка элемента 10 в 2-3 дерево — 2 этап (переливание узлов)

Однако при попытке вставить любое новое значение в дерево на рис. 5.18 все равно придется выполнять расщепление корня, и высота дерева увеличится на 1.

Удаление элемента из 2-3-дерева.

Если у родителя три листа, то удаление проблем не представляет. Например, из дерева на рис.5.18 можно удалить любой лист без какого-либо дополнительного преобразования структуры.

Рассмотрим случай, когда у узла два листа. Если узел является корнем, то единственный сын становится новым корнем дерева. Пусть node не является корнем. p – его родитель.

Если p имеет другого сына, расположенного слева или справа от node и имеющего трёх сыновей, то один из них становится сыном узла node. Это уже известная операция переливания.

Если сын p имеет только двух сыновей, то единственный сын узла node присоединяется к этим сыновьям, а узел node удаляется. Такая операция является обратной расщеплению и называется склеиванием. Если после этого родитель p будет иметь только одного сына, то повторяется вышеописанный процесс с заменой node на p.

Например, удалим элемент 10 из рис.5.17.

Рис.5.19. Удаление элемента 10 из 2-3 дерева из рис.5.17

В данном случае была выполнена операция переливания.

Теперь удалим из полученного дерева узел 7. Выполнив операции переливания и склеивания, получим дерево, изображенное на рис.5.20.

Рис.5.20. Удаление элемента 7 из 2-3 дерева из рис.5.19

Реализация вышеописанных операций не сложна, но трудоемка, поэтому здесь не приводится.