Page 55 - 6110
P. 55
Рисунок 11.8 – Проведення змін в бінарному червоно-чорному дереві
Приклад 5 (рис.11.9): батько є червоним, але дядько чорний.
До того ж, нова вершина - ліва дитина свого батька, і батько є лівою
дитиною свого батька. В такому випадку ми проводимо правий
поворот навколо дідуся. В результаті бувший батько тепер є
батьком і нової вершини, і свого бувшого дідуся. Ми знаємо, що
бувший дідусь є чорним, інакше б батько не був червоним. Тепер
слід поміняти місцями кольори бувшого батька та дідуся, і тепер
дерево виконує властивість 3. Легко бачити, що властивість 4 також
залишається незмінною.
Рисунок 11.9 – Проведення змін в бінарному червоно-чорному дереві
54
