UK 
EnglishТипова
Polski🌲 Червоно-чорне дерево — самобалансивне ДДП
Вставляйте й видаляйте ключі в червоно-чорному дереві та спостерігайте, як перефарбування й повороти тримають його збалансованим. Кожен шлях має однакову чорну висоту, тож пошук, вставка й видалення лишаються O(log n).
Схожі симуляції
Про червоно-чорне дерево
Червоно-чорне дерево — це самобалансивне двійкове дерево пошуку, запроваджене Рудольфом Байєром (1972) і пізніше назване Леонідасом Гібасом і Робертом Седжвіком (1978). Воно підтримує чотири колірні інваріанти: корінь чорний; жоден червоний вузол не має червоного батька; кожен шлях від будь-якого вузла до нульового листка містить однакову кількість чорних вузлів (чорну висоту); а нульові листки вважаються чорними. Ці правила гарантують, що висота дерева ніколи не перевищує 2·log2(n+1), забезпечуючи O(log n) у найгіршому випадку для пошуку, вставки й видалення. Червоно-чорні дерева лежать в основі стандартних контейнерів map/set у C++ (std::map), Java (TreeMap) і повністю справедливого планувальника (CFS) Linux.
Ця симуляція дозволяє вставляти або видаляти ключі по одному, спостерігаючи, як кожен крок перефарбування та кожен лівий/правий поворот анімуються в реальному часі. Лічильник висоти порівнює поточну висоту червоно-чорного дерева з еквівалентним незбалансованим ДДП, щоб показати практичну користь інваріантів.
Часті запитання
Які чотири інваріанти червоно-чорного дерева?
1) Кожен вузол — червоний або чорний. 2) Корінь — чорний. 3) Кожен нульовий (листовий) вузол — чорний. 4) Якщо вузол червоний, обидва його нащадки чорні (жодних двох послідовних червоних вузлів на жодному шляху). Додатково, 5) усі шляхи від будь-якого вузла до його нульових листків-нащадків проходять через однакову кількість чорних вузлів — це і є властивість чорної висоти, що забезпечує баланс.
Скільки поворотів може вимагати одна вставка?
Щонайбільше два повороти на одну вставку, плюс O(log n) операцій перефарбування, що поширюються вгору. Натомість AVL-дерево може вимагати O(log n) поворотів після вставки (хоча на практиці в середньому менше). Для видалення червоно-чорному дереву може знадобитися щонайбільше три повороти. Ця обмежена кількість поворотів робить червоно-чорні дерева привабливими в системах, де повороти дорогі, як-от персистентні чи функціональні структури даних.
Як червоно-чорне дерево порівнюється з AVL-деревом?
AVL-дерева підтримують суворіший баланс висоти (різниця висот піддерев ≤ 1), що дає трохи швидший пошук у середньому. Червоно-чорні дерева допускають співвідношення висот до 2:1 між найдовшим і найкоротшим шляхами, що дозволяє швидші вставки й видалення завдяки меншій кількості поворотів. У навантаженнях з інтенсивним записом (бази даних, планувальники ОС) зазвичай віддають перевагу червоно-чорним деревам; у таблицях пошуку з інтенсивним читанням AVL-дерева можуть бути швидшими.
Що таке лівий поворот і коли він застосовується?
Лівий поворот навколо вузла x робить правого нащадка x, вузол y, новим коренем піддерева, переміщуючи x вниз у ліве піддерево y, а колишнє ліве піддерево y стає новим правим піддеревом x. Він застосовується, коли дерево має перекіс праворуч — зокрема під час вставки, коли новий червоний вузол є правим нащадком правого нащадка (випадок «право-право» у виправленні після вставки).
Чому властивість чорної висоти гарантує висоту O(log n)?
Нехай bh(x) — чорна висота вузла x. За правилом відсутності послідовних червоних вузлів щонайбільше половина вузлів на будь-якому шляху від кореня до листка може бути червоною, тож фактична висота h ≤ 2·bh(корінь). Піддерево з коренем у будь-якому вузлі з чорною висотою k містить щонайменше 2k−1 внутрішніх вузлів, тож n ≥ 2bh−1, звідки bh ≤ log2(n+1) і h ≤ 2·log2(n+1).
Як червоно-чорні дерева використовуються в ядрі Linux?
Повністю справедливий планувальник (CFS) Linux зберігає процеси, готові до виконання, у червоно-чорному дереві, ключем якого є віртуальний час виконання, тож процес із найменшим часом виконання (наступний для запуску) можна знайти за O(log n). Менеджер пам'яті ядра використовує червоно-чорні дерева для відстеження областей віртуальної пам'яті (VMA) кожного процесу, а підсистема epoll використовує їх для ефективного керування файловими дескрипторами.
Що таке 2-3-4-дерево і як воно пов'язане з червоно-чорним деревом?
2-3-4-дерево (або B-дерево порядку 4) зберігає 1–3 ключі на вузол із 2–4 нащадками, підтримуючи ідеальний баланс. Кожне 2-3-4-дерево точно відображається на червоно-чорне дерево: 2-вузол стає одним чорним вузлом; 3-вузол стає чорним вузлом із червоним нащадком; 4-вузол стає чорним вузлом із двома червоними нащадками. Ця відповідність дає альтернативний доказ коректності червоно-чорного дерева і лежить в основі варіанту LLRB (лівоспрямоване червоно-чорне дерево).
Що таке лівоспрямоване червоно-чорне дерево (LLRB)?
Варіант LLRB, популяризований Робертом Седжвіком (2008), додає обмеження, що червоні зв'язки завжди спрямовані ліворуч (червоний вузол завжди є лівим нащадком). Це скорочує кількість структурних випадків, які потрібно обробляти під час вставки й видалення, приблизно з 6–8 до 3, що дає реалізації приблизно у 50 рядків коду проти 200+ для стандартного формулювання Кормена-Лейзерсона-Рівеста. TreeMap у Java використовує стандартне формулювання; деякі бібліотеки функціональних мов надають перевагу LLRB.
Чи можна зробити червоно-чорні дерева персистентними?
Так. Оскільки кожна вставка чи видалення змінює лише O(log n) вузлів (уздовж шляху від кореня до зачепленого листка), персистентне червоно-чорне дерево можна створити копіюванням шляху: дублюючи лише O(log n) вузлів, що змінюються, і спільно використовуючи решту. Це дає O(log n) часу й простору на операцію з повною історією версій і використовується в персистентних функціональних структурах даних, таких як відсортовані карти Clojure.
Як відбувається видалення в червоно-чорному дереві?
Видалення спочатку виконує стандартне видалення з ДДП (замінюючи вузол його наступником в порядку обходу, якщо він має двох нащадків). Якщо видалений вузол або його заміна були червоними, порушення чорної висоти не виникає. Якщо видаляється чорний вузол, дефіцит «подвійної чорноти» поширюється вгору й вирішується шістьома випадками аналізу кольору сусіда та кольору його нащадків, кожен з яких або перебудовує піддерево поворотами й перефарбуванням, або переносить дефіцит вище. Досить щонайбільше трьох поворотів.