Червоно-чорне дерево
Червоно-чорне дерево (англ. red-black tree, англ. RB tree) — в інформатиці — різновид самозбалансованого бінарного дерева пошуку, вершини якого мають додаткові властивості (RB-властивості), зокрема «колір» (червоний або чорний). Ці біти кольору використовуються для забезпечення того, щоб дерево залишалося приблизно збалансованим при виконанні операцій вставки та видалення.[2]
| Червоно-чорне дерево | ||
|---|---|---|
| Тип | дерево | |
| Винайдено | 1972 | |
| Винайшли | Рудольф Байєр | |
| Обчислювальна складність у записі великого О | ||
| Середня | Найгірша | |
| Простір | O(n) | O(n) |
| Пошук | O(log n)[1] | O(log n)[1] |
| Вставляння | O(log n)[1] | O(log n)[1] |
| Видалення | O(log n)[1] | O(log n)[1] |
Червоно-чорні дерева — різновид збалансованих дерев, в яких за допомогою спеціальних трансформацій гарантується, що висота дерева h не буде перевищувати O(log n). Зважаючи на те, що час виконання основних операцій на бінарних деревах (пошук, видалення, додавання елементу) є O(h), ці структури даних на практиці є набагато ефективнішими, аніж звичайні бінарні дерева пошуку.
RB-властивості
Бінарне дерево називається червоно-чорним, якщо воно має такі властивості:
- кожна вершина або червона, або чорна
- корінь дерева — чорний
- кожний лист (NIL) — чорний
- якщо вершина червона, обидві її дочірні вершини чорні (інакше, батько червоної вершини — чорний)
- усі прості шляхи від будь-якої вершини до листів мають однакову кількість чорних вершин
Такі властивості надають червоно-чорному дереву додаткового обмеження: найдовший шлях з кореня до будь-якого листа перевищує найкоротший шлях не більше ніж вдвічі. В цьому сенсі таке дерево можна назвати збалансованим. Зважаючи на те, що час виконання основних операцій з бінарними деревами пошуку залежить від висоти, таке обмеження гарантує їхню ефективність в найгіршому випадку, чого звичайні бінарні дерева гарантувати не можуть.
Для того, щоби зрозуміти, чому перелічені властивості забезпечують існування такого обмеження, зазначимо, що в червоно-чорному дереві, відповідно до властивості 4 не існує такого шляху, на якому б зустрілись дві червоні вершини підряд. Найкоротший шлях складається з усіх чорних вершин, а в найдовшому червоні та чорні вершини чергуються. З врахуванням властивості 5, отримуємо, що глибина будь-яких двох листів відрізняється не більше ніж вдвічі.
В деяких зображеннях червоно-чорних дерев, NIL-листки не наводяться, тому що вони не містять корисної інформації, але їхнє існування необхідне для забезпечення усіх властивостей.
Основні операції
Операції, які не пов'язані з модифікацією RB-дерева, не потребують коректив і повністю аналогічні відповідним операціям для звичайних бінарних дерев пошуку. Разом з тим, додавання або видалення елементу з червоно-чорного дерева може призвести до порушення RB-властивостей. Відновлення цих властивостей після модифікації дерева потребує порівняно невеликої кількості (O(log n)) операцій зі зміни кольору вершин та не більше як трьох операцій повороту (дві при доданні елементу). Це залишає часові параметри операцій додавання та видалення в межах O(log n), але ускладнює відповідні алгоритми.
Вставка елементу
Процедура починається аналогічно вставці елементу в бінарне дерево пошуку та фарбування її у червоний колір. Подальші дії залежать від кольорів сусідніх вершин. Зазначимо, що:
- властивість 2 завжди зберігається
- властивість 3 порушується тільки при вставці червоної вершини, перефарбуванні чорної вершини в червону або обертанні
- властивість 4 порушується тільки при вставці чорної вершини, перефарбуванні червоної вершини в чорну або обертанні
На допоміжних діаграмах, вершина, яка додається, позначена N, первісний батько цієї вершини позначений P, батько вершини P («дідусь» N) позначений G. «Дядько» N (тобто вершина, яка має спільного з P батька — G) позначений як U. Розглянемо такі випадки:
Випадок 1: Нова вершина знаходиться в корені дерева. В такому випадку необхідно пофарбувати її в чорний колір для забезпечення властивості 1. Очевидно, що властивість 5 при цьому залишається справедливою.
Випадок 2: Батько нової вершини є чорним. Властивість 3 не порушена. В цьому випадку дерево є коректним. Властивість 5 також зберігається, адже червона вершина додається на місце чорного листа і це не змінює кількості чорних вершин на цьому шляху.
 Діаграма для випадку 3 Випадок 3: Батько та дядько доданої вершини є червоними. Тоді ми можемо перефарбувати їх обох в чорний, а також перефарбувати дідуся в червоний. Тепер наша червона вершина має чорного батька. Завдяки тому, що будь-який шлях через батька чи дядька повинен проходити і через дідуся, кількість чорних вершин на шляху залишається незмінною. Однак батько дідуся (тобто прадідусь) може бути червоною вершиною, як тепер і дідусь. Якщо це так, слід повторити цю операцію рекурсивно. |
Зауваження: В наступних випадках ми припускаємо, вершина P є лівою дитиною G. Якщо P — права дитина, ліво та право в аналізі наступних випадків слід поміняти місцями.
 Діаграма для випадку 4 Випадок 4: Батько є червоним, але дядько — чорний. До того ж, нова вершина — права дитина свого батька, і батько в свою чергу ліва дитина свого батька. В такому випадку, ми можемо провести лівий поворот, внаслідок якого нова вершина та її батько поміняються ролями. Подальші дії з колишнім батьком проводяться відповідно до випадку 5. Зважаючи на те, що нова вершина та її батько є червоними, операція повороту не змінює умови 4. |
 Діаграма для випадку 5 Випадок 5: Батько є червоним, але дядько чорний. До того ж, нова вершина — ліва дитина свого батька, і батько є лівою дитиною свого батька. В такому випадку ми проводимо правий поворот навколо дідуся. В результаті колишній батько тепер є батьком і нової вершини, і свого колишнього дідуся. Ми знаємо, що колишній дідусь є чорним, інакше би батько не був червоним. Тепер варто поміняти місцями кольори колишнього батька та дідуся, і тепер дерево виконує властивість 3. Легко бачити, що властивість 4 також залишається незмінною. |
Примітки
- James Paton. Red-Black Trees.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Red–Black Trees. Introduction to Algorithms (вид. second). MIT Press. с. 273–301. ISBN 0-262-03293-7.