Червоно-чорне дерево

Матеріал з Вікіпедії — вільної енциклопедії.

ЧЕРВОНО-ЧОРНЕ ДЕРЕВО (англ. red-black tree, RB tree) - в інформатиці -- різновид бінарного дерева пошуку, вершини якого мають додаткові властивості (RB-властивості), зокрема "колір" (червоний або чорний). Червоно-чорні дерева -- різновид збалансованих дерев, в яких за допомогою спеціальних трансформацій гарантується, що висота дерева h не буде перевищувати O(log n). Зважаючи на те, що час виконання основних операцій на бінарних деревах (пошук, видалення, додавання елементу) є O(h), ці структури даних на практиці є набагато ефективнішими, аніж звичайні бінарні дерева пошуку.

[ред.] RB-властивості

Бінарне дерево називається червоно-чорним, якщо воно має наступні властивості:

1. кожна вершина або червона, або чорна
2. корень дерева -- чорний
3. кожний лист (NIL) -- чорний
4. якщо вершина червона, обидві її дитини чорні
5. усі шляхи від кореня до листів, мають однакову кількість чорних вершин

Такі властивості надають червоно-чорному дереву додаткового обмеження: найдовший шлях з кореня до будь-якого листа перевищує найкоротший шлях не більше ніж вдвічі. В цьому сенсі таке дерево можна назвати збалансованим. Зважаючи на те, що час виконання основних операцій з бінарними деревами пошуку залежить від висоти, таке обмеження гарантує їхню ефективність в найгіршому випадку, чого звичайні бінарні дерева гарантувати не можуть.

Для того, щоби зрозуміти, чому перелічені властивості забезпечують існування такого обмеження, зазначимо, що в червоно-чорному дереві, відповідно до властивості 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 також залишається незмінною.

Це незавершена стаття про комп'ютери. Ви можете допомогти проекту, виправивши або дописавши її.