Червоно-чорне дерево — Вікіпедія
Червоно-чорне дерево | ||
---|---|---|
Тип | дерево | |
Винайдено | 1972 | |
Винайшли | Рудольф Байєр[en] | |
Обчислювальна складність у записі великого О | ||
Середня | Найгірша | |
Простір | 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] |
![](http://upload.wikimedia.org/wikipedia/uk/0/0a/RB-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B0_%D0%BC%D0%B0%D0%BB%D0%B5%D0%BD%D1%8C%D0%BA%D1%96_%D0%BF%D1%80%D0%B8%D0%BA%D0%BB%D0%B0%D0%B4%D0%B8.png)
Червоно-чорне дерево (англ. red-black tree, англ. RB tree) — в інформатиці — різновид самозбалансованого бінарного дерева пошуку, вершини якого мають додаткові властивості (RB-властивості), зокрема «колір» (червоний або чорний). Ці біти кольору використовуються для забезпечення того, щоб дерево залишалося приблизно збалансованим при виконанні операцій вставки та видалення.[2]
Червоно-чорні дерева — різновид збалансованих дерев, в яких за допомогою спеціальних трансформацій гарантується, що висота дерева h не буде перевищувати O(log n). Зважаючи на те, що час виконання основних операцій на бінарних деревах (пошук, видалення, додавання елементу) є O(h), ці структури даних на практиці є набагато ефективнішими, аніж звичайні бінарні дерева пошуку.
Бінарне дерево називається червоно-чорним, якщо воно має такі властивості:
- кожна вершина або червона, або чорна
- корінь дерева — чорний
- кожний лист (NIL) — чорний
- якщо вершина червона, обидві її дочірні вершини чорні (інакше, батько червоної вершини — чорний)
- усі прості шляхи від будь-якої вершини до листів мають однакову кількість чорних вершин
![Червоно-чорне дерево](http://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/450px-Red-black_tree_example.svg.png)
Такі властивості надають червоно-чорному дереву додаткового обмеження: найдовший шлях з кореня до будь-якого листа перевищує найкоротший шлях не більше ніж вдвічі. В цьому сенсі таке дерево можна назвати збалансованим. Зважаючи на те, що час виконання основних операцій з бінарними деревами пошуку залежить від висоти, таке обмеження гарантує їхню ефективність в найгіршому випадку, чого звичайні бінарні дерева гарантувати не можуть.
Для того, щоби зрозуміти, чому перелічені властивості забезпечують існування такого обмеження, зазначимо, що в червоно-чорному дереві, відповідно до властивості 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 також зберігається, адже червона вершина додається на місце чорного листа і це не змінює кількості чорних вершин на цьому шляху.
Зауваження: В наступних випадках ми припускаємо, вершина P є лівою дитиною G. Якщо P — права дитина, ліво та право в аналізі наступних випадків слід поміняти місцями.
- ↑ а б в г д е James Paton. Red-Black Trees. Архів оригіналу за 27 травня 2018. Процитовано 21 травня 2018.
- ↑ Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 13. Червоно-чорні дерева. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
![]() | Це незавершена стаття про структури даних. Ви можете допомогти проєкту, виправивши або дописавши її. |
![]() | Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. (січень 2008) |