При обычном добавлении элемента в дерево процедурой tree_ins (см. таблицу 2), которая осуществляет эту операцию за время O(logn) RB-баланс нарушается. Поэтому следует выполнять ряд действий для его восстановления. Для этого мы будем использовать «вращения», смысл которых ясен из рис 1.
Рис. 1. Цифры рядом со стрелками соответствуют номерам строк процедур таблицы 3.
Как мы видим, правое и левое вращения симметричны (см. таблицу 3 и рис. 4, 5 в приложении), а время выполнения есть O(1).
Собственно добавление элемента осуществляется с помощью процедуры tree_ins, а балансировка дерева – основным кодом процедуры rb_ins (см. таблицу 4). После выполнения строк 1, 2 наше дерево соответствует всем RB свойствам, кроме 3-го: у x – красной вершины может быть родитель красного цвета. На другие свойства вставка красной вершины не влияет.
В цикле рассматриваются 3 случая, каждый из которых распадается на пару симметричных, и определяются логической переменной b. Основной цикл конечен, так как вершина x каждую итерацию основного цикла поднимается не менее чем на один уровень, время выполнения сравнимо с O(logn).
Для уменьшения количества граничных случаев мы считаем, что корень у RB-дерева всегда черный. Поэтому вершина x^.p^.p^.l существует.
Все возможные случаи, возникающие в ходе выполнения процедуры, наглядно иллюстрируются
Loading ...