Червоно-чорні дерева: опис, особливості

Рудольф Байєр розробив систему "червоно-чорні дерева" ще на початку 1970-х років. Назва цієї ж їй дали Л. Гимпас і Р. Седжвік.

Що за червоно-чорні дерева

Варто відзначити, що вони є одним видів самобалансирующихся двійкових дерев, що забезпечують лічильний розмір висоти від кількості вузлів і виробляють первинні та базові процеси дерева пошуку за короткий час. До таких операцій належать приєднання, виключення і підшукування сайту. Баланс забезпечується на базі доповнення атрибуту прикладного позначення сайту кольору. Це властивість бере на себе один з ймовірних концептів і позначається одним із згаданих кольорів.


Чисельність чорних одиниць на гілки від початку (кореня) до фіналу (листа) іменується чорної висотою дерева.

Виникнення терміна

Описуючи самобалансирующееся дерево пошуку в своїй роботі автори статті, ймовірно, навіть не припускали, що стануть основоположниками нового терміна. Проте доля розпорядилася так, що в друкарні були в наявності фарби всього двох кольорів. Ними і позначався кожен біт, який приєднується до наступного вузла.

Застосування

В інформатиці червоно-чорні дерева застосовуються для формування порівнянних даних, до яких можуть відноситися різноманітні витримки і частини написів або цифр. Створити можна червоно-чорне дерево на Actionscript, Python, C++ і практично будь-якому іншому мовою програмування. Це дуже просто. Червоно-чорне дерево Java також досить широко поширене.

Особливості

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


Колір сайту є виключно одним з двох вищезгаданих. Інших варіантів немає, це відображається також і в найменуванні терміна. Корінь дерева завжди повинен забарвлюватися чорним. Винятки можливі, однак таке відступ від правила додає ризик того, що зіб'ється самобалансировка дерева. Все листя мають нульове значення (NIL) і позначаються чорним кольором. Необхідно стежити, щоб два нащадка кожного червоного батьківського вузла були чорними. Будь легкий курс від конкретного вузла до всякого листового дочірнього вузла забезпечує точно рівну кількість чорних структурних одиниць. Іноді червоно-чорні дерева інтерпретують як банальних бінарних дерев пошуку. Їх відмінності визначають лише тим, що взамін певних кольорових вузлів, вищезгадані значення уквітчані ребра.

Чому обирають саме червоно-чорні дерева

Чорно-червоні дерева являють собою один з найпоширеніших варіантів самостійно балансирующихся бінарних дерев пошуку, до яких найчастіше звертаються в практичному відношенні. Чим пояснюється така популярність? Практика лінива, і це варто визнати. Все, що занадто громіздко і важко у використанні і при цьому дає порівнянно аналогічний результат при застосуванні більш простих методів, відмирає або відходить на дальній план. Така поширеність у народі червоно-чорних дерев пояснюється тим, що вони найбільш часто забезпечують оптимальну рівновагу між якістю і рівнем збалансованості і заковыристостью його підтримки.
Наприклад, якщо зіставляти їх з досконалими у ступені своєї збалансованості деревами, то може виникнути ситуація, коли спостерігається, що «ідеальні» представники накладають надто непримиренні вимоги. А в умовах втілення в життя дій виключення з дерева або розвороту занадто велику кількість часу і сил витрачається на стабілізацію потрібної в даній ситуації збалансованості.

Процеси

Процес вичитки чорно-червоних бінарних дерев практично аналогічний для всіх інших двійкових розгалужень пошуку. Це вірно, оскільки будь-чорно-червоне дерево являє собою один з приватних варіантів класичного бінарного дерева пошуку. Однак при роботі з ними слід враховувати більшу ймовірність того, що пряме виробництво дії включення або виключення даних може викликати пошкодження структури чорно-червоних дерев. Величезною перевагою є те, що для реконструкції властивостей необхідно відносно мала кількість дій, таких як зміна кольорів і менш трьох поворотів дерева. Фактично всі ці операції не займають багато часу. Приступати до виконання дії вставки або включення елемента варто з прирощення наступного вузла. Ця функція аналогічна у всіх двійкові дерева пошуку. Наступним кроком є колоризація вузла в червоний. Єдиною відмінністю можна вважати те, що якщо при виконанні вставки в бінарному дереві пошуку насамперед додаємо лист, то в чорно-червоному останні не несуть ніякої інформації. Отже, замість них додається внутрішній вузол, що приймає червоний колір і два його чорних нащадка. Подальші наші дії безпосередньо обумовлюються кольором прилеглих вузлів. Для них застосовують термін «дядько». Пряма аналогія з генеалогічним древом. Отже: Характеристика того, що все листя зберігають чорний колір, повинно реалізовуватися завжди. Послідовність того, що два похідних кожного червоного вузла зберігають чорний колір, може перерватися. Але це відбувається лише при додаванні червоного сайту, при зміні кольору чорного на червоний або при розвороті всього дерева. Також відзначимо, що послідовності від вузла до листа, що включають одне і те ж кількість чорних вузлів, можуть бути порушені. Це відбувається лише при включенні чорного вузла, зміну червоного елемента на чорний, а також у протилежній ситуації перефарбування чорного на червоний. Це ж може виконуватися і при розвороті дерева. Вивчивши все вищевикладене, нескладно розібратися, як здійснюється пошук у червоно-чорному дереві. Цікава інтерпретація такого простого поняття, як дерево, з описом його кольори - червоно-чорного або чорно-коричневого. Тепер ви обізнані і в цьому.