Page 54 - 6110

для забезпечення властивості 1. Очевидно, що властивість 5 при
цьому залишається справедливою.
Приклад 2 (рис.11.7): Батько нової вершини є чорним.
Властивість 3 не порушена. В цьому випадку дерево є коректним.
Властивість 5 також зберігається, адже червона вершина додається
на місце чорного листа і це не змінює кількості чорних вершин на
цьому шляху.

Рисунок 11.7 – Проведення змін в бінарному червоно-чорному дереві

Приклад 3: Батько та дядько доданої вершини є червоними.
Тоді ми можемо перефарбувати їх обох в чорний, а також
перефарбувати дідуся в червоний. Тепер наша червона вершина має
чорного батька. Завдяки тому, що будь-який шлях через батька чи
дядька повинен проходити і через дідуся, кількість чорних вершин
на шляху залишається незмінною. Однак батько дідуся (тобто
прадідусь) може бути червоною вершиною, як тепер і дідусь. Якщо
це так, слід повторити цю операцію рекурсивно.
В наступних випадках ми припускаємо, вершина P є лівою
дитиною G. Якщо P - права дитина, ліво та право в аналізі
наступних випадків слід поміняти місцями.
Приклад 4 (рис.11.8): батько є червоним, але дядько - чорний.
До того ж, нова вершина - права дитина свого батька, і батько в
свою чергу ліва дитина свого батька. В такому випадку, ми можемо
провести лівий поворот, внаслідок якого нова вершина та її батько
поміняються ролями. Подальші дії з бувшим батьком проводяться
відповідно до випадку 5. Зважаючи на те, що нова вершина та її
батько є червоними, операція повороту не змінює умови 4.

53