Page 53 - 6110

Рисунок 11.6 – Бінарне червоно-чорне дерево

Операції, які не пов'язані з модифікацією RB-дерева, не
потребують коректив і повністю аналогічні відповідним операціям
для звичайних бінарних дерев пошуку. Разом з тим, додавання або
видалення елементу з червоно-чорного дерева може призвести до
порушення RB-властивостей. Відновлення цих властивостей після
модифікації дерева потребує порівняно невеликої кількості (Т(log
n)) операцій зі зміни кольору вершин та не більше як трьох операцій
повороту (дві при додаванні елементу). Це залишає часові
параметри операцій додавання та видалення в межах Т(log n), але
ускладнює відповідні алгоритми.
Процедура вставки елементу починається аналогічно вставці
елементу в бінарне дерево пошуку та фарбування його у червоний
колір. Подальші дії залежать від кольорів сусідніх вершин.
Зазначимо, що:
- властивість 2 завжди зберігається;
- властивість 3 порушується тільки при вставці червоної
вершини, перефарбуванні чорної вершини в червону або обертанні;
- властивість 4 порушується тільки при вставці чорної вершини,
перефарбувані червоної вершини в чорну або обертанні.
На допоміжних рисунках, вершина, яка додається, позначена N,
первісний батько цієї вершини позначений P, батько вершини P
(“дідусь” N) позначений G. “Дядько” N (тобто вершина, яка має
спільного з P батька - G) позначений як U. Розглянемо наступні
приклади.
Приклад 1 (рис.11.7): нова вершина знаходиться в корені
дерева. В такому випадку необхідно пофарбувати її в чорний колір

52