Довідка та теорія
Червоно-чорне дерево — це двійкове дерево пошуку, де
кожен вузол несе один додатковий біт кольору. П'ять
правил тримають його збалансованим, тож пошук, вставка та
видалення — усі O(log n).
П'ять властивостей
- Кожен вузол червоний або чорний.
- Корінь чорний.
- Кожен листок (NIL) чорний.
- Червоний вузол не має червоного нащадка.
- Кожен шлях від вузла до його листків має однакову кількість чорних вузлів — чорну висоту.
Виправлення після вставки
Новий ключ додається як червоний листок. Якщо його батько теж червоний — маємо порушення. Якщо дядько червоний, ми перефарбовуємо батька, дядька й діда та йдемо вгору. Якщо дядько чорний, ми обертаємо (ліворуч і/або праворуч) та перефарбовуємо, щоб виправити локально.
Обертання
Ліве обертання піднімає правого нащадка вузла над
ним; праве обертання піднімає лівого нащадка. Кожне
— це перестановка вказівників за O(1), що зберігає
порядок ключів, змінюючи форму.
Межа висоти
Дерево з n ключами має висоту щонайбільше
2·log₂(n+1). Дивіться, як показник висоти слідує за
log₂(n) під час вставки.
Як працює ця симуляція
Це справжнє червоно-чорне дерево, а не записана анімація. Кожен ключ,
який ви вводите, вставляється за справжнім правилом двійкового дерева
пошуку, фарбується червоним, а потім виправляється стандартним циклом
insert-fixup: він перевіряє колір дядька нового
вузла та або перефарбовує батька, дядька й діда, або виконує одне чи
два обертання з подальшим перефарбуванням. Корінь наприкінці
завжди стає чорним. Видалення використовує відповідний
delete-fixup, усуваючи тимчасову «подвійно-чорну» вагу
перефарбуванням та обертаннями.
Як читати полотно
Вузли малюються червоними або чорними відповідно до їхнього біта
кольору, ребра з'єднують батьків із нащадками, а кожен вузол
підписаний своїм ключем. Панель статистики показує живу
кількість вузлів, чорну висоту (за визначенням сталу на
кожному шляху), фактичну висоту дерева поруч із
log₂(n) та скільки обертань і перефарбувань знадобилося
останній операції. Використовуйте Випадковий, щоб швидко
додавати ключі й дивитися, як структура балансується.
Поширені запитання
Що таке червоно-чорне дерево?
Червоно-чорне дерево — це самобалансивне двійкове дерево пошуку. Кожен вузол несе один додатковий біт кольору, червоний або чорний, а набір правил кольору тримає найдовший шлях від кореня до листка не більше ніж удвічі довшим за найкоротший, гарантуючи O(log n) пошук, вставку та видалення.
Які властивості червоно-чорного дерева?
Кожен вузол червоний або чорний; корінь чорний; кожен листок (NIL-сторож) чорний; червоний вузол ніколи не має червоного нащадка; і кожен шлях від вузла до його листків-нащадків містить однакову кількість чорних вузлів (чорну висоту).
Що таке чорна висота?
Чорна висота вузла — це кількість чорних вузлів на будь-якому шляху від цього вузла до листка, не рахуючи сам вузол. Оскільки кожен такий шлях має однакову кількість, дерево лишається приблизно збалансованим.
Як вставка тримає дерево збалансованим?
Новий ключ вставляється як червоний листок за звичайним правилом двійкового дерева пошуку, потім цикл виправлення усуває будь-яке порушення червоний-червоний. Залежно від кольору вузла-дядька він або перефарбовує батька, дядька й діда, або виконує одне чи два обертання з перефарбуванням, а потім продовжує вгору до кореня, який зрештою стає чорним.
Що таке обертання?
Обертання — це локальна перебудова, що змінює кілька зв'язків батько-нащадок, щоб опустити одне піддерево й підняти інше, зберігаючи послідовність ключів за порядком обходу. Ліве обертання піднімає правого нащадка вузла над ним; праве обертання піднімає лівого нащадка. Обертання виконуються за O(1).
Чому перефарбування замість постійних обертань?
Коли дядько нового вузла теж червоний, просте перевертання кольорів батька, дядька й діда усуває локальний конфлікт червоний-червоний без переміщення жодних вказівників, а потім зсуває можливий новий конфлікт на два рівні вгору. Обертання потрібні лише тоді, коли дядько чорний.
Наскільки високим може стати червоно-чорне дерево?
Червоно-чорне дерево з n ключами має висоту щонайбільше 2·log2(n+1). Симуляція показує фактичну висоту поруч із log2(n), тож ви бачите, як реальна висота слідує за логарифмом у міру додавання ключів.
Чим червоно-чорне дерево відрізняється від AVL-дерева?
Обидва є самобалансивними ДДП з операціями O(log n). AVL-дерева тримають суворіший баланс висоти, тож вони трохи швидші для пошуку, але роблять більше обертань під час вставки й видалення. Червоно-чорні дерева балансуються слабкіше з меншою кількістю обертань, тому вони лежать в основі багатьох мап стандартних бібліотек і ядра Linux.
Де червоно-чорні дерева застосовують на практиці?
Вони лежать в основі впорядкованих асоціативних контейнерів, як-от C++ std::map і std::set, Java TreeMap і TreeSet, а також планувальника Completely Fair Scheduler та багатьох інших структур усередині ядра Linux.
Що відбувається під час видалення?
Видалення вилучає ключ за стандартною процедурою ДДП, потім, якщо було вилучено чорний вузол, запускається виправлення, що зсуває додаткову «подвійно-чорну» вагу вгору деревом, усуваючи її перефарбуванням та обертаннями, доки не буде відновлено властивість однакової чорної висоти.
Чи зберігаються дублікати ключів?
Ні. Ця симуляція ігнорує повторні вставки вже наявного ключа, тож дерево містить лише унікальні ключі, як у типовій реалізації множини.