Червоно-чорне дерево. Властивості, принципи організації, механізми вставки

Червоно-чорне дерево – це вид бінарного дерева, основною суттю якого є здатність до самобалансування. Існують кілька видів дерев, що самобалансуються, але в рамках цієї статті ми торкнемося тільки червоно-чорного дерева (КЧД). Збалансованість досягається за рахунок введення додаткового атрибуту вузла дерева – «кольору». У кожному вузлі дерева, крім елемента, зберігається 1 біт інформації про те, чи червоний вузол, чи чорний, при цьому це може бути не тільки колір, але і будь-яка інша інформація, що дозволяє відрізнити один тип вузла від іншого. Наприклад, 1 чи 0, true чи false тощо. Принципи організації (властивості) КЧД:

1. Корінь дерева чорний.
2. Всі листя, що не містять даних, чорні.
3. Обидва нащадки кожного червоного вузла – чорні.
4. Глибина в чорних вузлах однакова для будь-якого піддерева.

Основні операції над деревом:

1. Пошук (search).
2. Вставка елемента (insert).
3. Видалення елемента (delete).

Останні дві операції явно призводять до зміни структури дерева, отже, їх результатом може бути порушення збалансованості дерева. Time та Space Complexity. Операції вставки, видалення та пошуку для КЧД по Time Complexity складають O(log n), де n – кількість вузлів у дереві, оскільки для їх виконання нам потрібно дійти до потрібного вузла, на кожному кроці відкидаючи одне з піддерев. У разі, коли вставка або видалення призвели до порушення властивостей КЧД, необхідно виконати перебалансування. Балансування складається з двох операцій: перефарбування O(1) та ротації O(1). Кожна операція балансування займає константний час, оскільки складається з перезапису посилань у дочірніх та батьківських елементах, а також інформації про їх колір. Однак при вставці або видаленні елемента може виникнути ситуація, за якої потрібно балансувати дерево від нижнього вузла аж до кореня. Оскільки гарантується, що максимальна висота КЧД, що складається з n вузлів, трохи більше 2log(n + 1), то в гіршому разі перебалансування може зайняти log(n) операцій. Витрати пам'яті для вставки становлять O(1), оскільки вона полягає у створенні нового вузла, а операції балансування і перефарбування додаткової пам'яті не вимагають. Як визначити, що дерево не в балансі? Для КЧД дерево перебуває у стані балансу, якщо дотримані його властивості, описані раніше. Існують 4 види станів розбалансування:

1. Left-left imbalance (LL).
2. Right-right imbalance (RR).
3. Left-right imbalance (LR).
4. Right-left imbalance (RL).

Перші два стани ще називають лінійними (Line), оскільки візуально їх можна подати як пряму гілку, перекошену в один бік. Два, що залишилися, називають трикутниками (Triangle). Щоб привести КЧД у стан збалансованості, необхідно виконати маніпуляції, які називаються ротаціями. Для балансування цих 4 видів застосовуються 2 види ротацій:

1. Для LL і RR.
2. Для LR і RL.

Перший вид полягає в тому, щоб потягнути перший вузол вниз так, щоб середина стала нагорі. Візуально це можна уявити так, ніби вузли дійсно були вузлами на мотузці, яка висить на цвяху:Виглядає сама ротація так:При ускладненій LL-ротації, коли вузли також мають нащадків, принцип залишається тим самим, проте правий нащадок вузла, який стає батьком, стає лівим/правим нащадком вузла, за який «тягнуть». Приклад:Другий вид (LR, RL) складається з двох етапів і полягає в тому, щоб спочатку привести дерево до першого стану, а потім потягнути перший вузол вниз:Якщо подивитися на даний малюнок, то можна помітити, що ми просто переносимо нижній вузол нагору, роблячи його «новим» дідусем, а «колишнього» дідуся робимо або лівим, або правим нащадком. Приклад:При ускладненій LR/RL-ротації, коли вузли також мають нащадків, принцип залишається тим самим, проте колишні нащадки «нового» батька стають на місця нащадків дочірніх вузлів, що звільнилися. Приклад:Програмний код червоно-чорного дерева Поговоримо про теорію, тепер подивимося, як організовано пристрій КЧД мовою програмування JAVA. Механіка червоно-чорного дерева застосовується, зокрема, у реалізації TreeMap, проте для наочності ми будемо використовувати спрощений код. Все починається з ініціалізації приватного статичного поля EMPTY типу Node, яке є порожнім вузлом. Нащадки EMPTY також є EMPTY. Воно стане в пригоді нам при вставці елемента, оскільки всі листки (на першому малюнку представлені як NIL) при вставці ініціалізуються даним полем.

public class RedBlackTree {
    private static final Node EMPTY = new Node(0);

    static {
        EMPTY.left = EMPTY;
        EMPTY.right = EMPTY;
    }

У структурі класу є посилання на поточний вузол current, батька поточного вузла parent, дідуся поточного вузла grand, прадідуся поточного вузла great, а також покажчик на корінь дерева header.

protected Node current;
   private Node parent;
   private Node grand;
   private Node great;
   private Node header;

   public RedBlackTree() {
       header = new Node(Integer.MIN_VALUE);
       header.left = EMPTY;
       header.right = EMPTY;
   }

При створенні header ініціалізується мінімальним значенням Integer.MIN_VALUE так, що будь-який елемент завжди буде більшим за нього, а його нащадки – порожнім елементом EMPTY. Всі елементи завжди будуть більшими за header, тому перша вставка завжди відбувається праворуч від header. Таким чином, правий син header завжди вказує на корінь дерева, отже, якщо header.right == EMPTY, то дерево порожнє. Власне, найцікавіше – вставка елемента. Стратегія вставки елемента в КЧД полягає в наступному:

1. Вставити вузол і пофарбувати його в червоний.
2. Якщо вставка призвела до порушення властивостей КЧД, то перефарбувати батька, дядька або дідуся і зробити ротацію вузлів, щоб знову привести дерево до балансу.

Існують 4 основні сценарії, які можуть відбутися при вставці елемента. Для зручності назвемо елемент, що вставляється, Z:

1. Z = root (елемент, що вставляється, є коренем дерева).
2. Z.uncle = red (дядько елемента, що вставляється, є червоним).
3. Z.uncle = black (Line). Дядько елемента, що вставляється, є чорним, і після вставки елемента дерево стало розбалансованим на вигляд LL або RR.
4. Z.uncle = black (Triangle). Дядько елемента, що вставляється, є чорним, і після вставки елемента дерево стало розбалансованим на вигляд RL або LR.

Наочно це виглядає так:Розберемо детальніше виправлення ситуації для кожного з чотирьох можливих випадків. Випадок №1. Просто фарбуємо корінь у чорний.Випадок № 2. Фарбуємо дідуся у червоний, а дядька – у чорний. Якщо дідусь вузла є коренем, то колір дідуся знову змінюємо на чорний.Випадок №3. Здійснюємо ротацію за схемою №1, тобто тягнемо вузол дідуся вниз. «A» займає місце «B», а потім перефарбовуємо вузол «колишнього» дідуся у червоний, а батька – у чорний.Випадок №4. Є найскладнішим, оскільки складається з кількох етапів. Спочатку ми здійснюємо ротацію за схемою №2, що призводить до стану, описаного у випадку №3, тобто ми зробимо ротацію, проте дерево, як і раніше, перебуває у стані розбалансування, оскільки нащадок вузла «Z» (вузол «A») є червоним. Тобто зараз вузол «A» порушує властивості КЧД, і ротація проводитиметься щодо його батьківських вузлів, якими є: дідусь – вузол «B», батько – вузол «Z». Знову робимо ротацію, а потім перефарбовуємо «колишнього» дідуся у червоний, а батька – у чорний.Повернемося до коду. Метод insert()

public void insert(int item) {
//        Зберігаємо посилання на header у current, parent і grand
        current = parent = grand = header;
//        Ініціалізуємо всі порожні елементи дерева (листки NIL) числом, яке хочемо вставити
        EMPTY.element = item;
//        Ітеруємося в циклі доти, доки значення поточного елемента не стане рівним елементу, що додається (item)
        while (current.element != item) {
//        Змінюємо значення 4 посилань у циклі для ітерації вглиб дерева
//        (прадіда на дідуся, дідуся на батька, батька на поточний вузол)
            great = grand;
            grand = parent;
            parent = current;
//        Замінюємо поточний вузол на його правого або лівого нащадка залежно від того,
//        чи є поточний елемент більшим за той, що додається, чи меншим,
//        тобто переходимо в ліве піддерево, якщо менше, або в праве, якщо більше
            current = item > current.element ? current.right : current.left;
//        На кожній ітерації перевіряємо, чи лівий і правий нащадки поточного елемента є червоними
            if (current.left.color == Color.RED && current.right.color == Color.RED) {
//        Якщо так, викликаємо метод для виправлення та переорієнтації дерева відносно поточного елемента,
//        який збережений у current на поточній ітерації
                reorient(item);
            }
        }
/*  Після виходу з циклу перевіряємо, чи є current порожнім листком.
    Якщо значення числа, що додається, виявилося рівним поточному вузлу,
    але при цьому ми не дійшли до листка (current != EMPTY),
    значить, у дереві вже існує вузол із таким значенням, і ми просто виходимо з методу.
    Саме тому при кожному вході в метод ми заново записуємо посилання на кореневий вузол. */
        if (current != EMPTY) {
            return;
        }
//      Якщо ми все ж дійшли до порожнього листка, створюємо новий вузол та ініціалізуємо його нащадків порожніми листками
        current = new Node(item, EMPTY, EMPTY);
//      Перевіряємо, лівим чи правим нащадком буде поточний вузол
        if (item < parent.element) {
            parent.left = current;
        } else {
            parent.right = current;
        }
//      Фарбуємо поточний вузол у червоний, його листки – у чорний,
//      а також виконуємо перебалансування, якщо parent виявився червоним
        reorient(item);
    }

Найважча частина відбувається у методі reorient(). Цей метод займається забарвленням вузлів і виконанням ротацій, для чого всередині тіла відсилає до методу -> rotate(int item, Node parent), який, своєю чергою, викликає метод rotateWithLeftNode(Node element) чи rotateWithRightNode(Node element), залежно від того, значення елемента, що додається, менше або більше за значення лівого або правого нащадка дідуся, тобто батька поточного елемента. Код методу:

protected void reorient(int item) {
//      Спочатку фарбуємо поточний вузол, до якого ми дійшли в методі insert, у червоний, а його нащадків – у чорний
        current.color = Color.RED;
        current.left.color = Color.BLACK;
        current.right.color = Color.BLACK;
//      Якщо колір батька current виявляється червоним, то необхідно виконати ротацію вузлів
        if (parent.color == Color.RED) {
//          Фарбуємо дідуся у червоний
            grand.color = Color.RED;
//          Якщо поточний елемент розташований лівіше батька, але правіше дідуся, або навпаки, то викликаємо ротацію для батька.
//          Тобто фактично визначаємо, який вид балансування потрібно застосувати: перший чи другий
            if (item < grand.element != item < parent.element) {
//          Якщо другий, то спочатку передаємо дідуся поточного елемента та виконуємо поворот ліворуч або праворуч,
//          одночасно змінюючи посилання на parent, у результаті чого батьком стане сам current
                parent = rotate(item, grand);
            }
//          Виконуємо ротацію першого виду. Оскільки в результаті такого повороту дідусь стане нащадком батька
//          поточного елемента, нам потрібно перезаписати посилання на нашого батька у прадідуся, тому й передаємо
//          посилання саме на прадідуся. Якщо прадідуся в нашому маленькому дереві ще немає, то на нього вказуватиме HEAD

//          Якщо балансування відбувається за першим видом, то current стане батьком поточного current
//          Якщо за другим, то current буде самим елементом, що вставляється, і на нього ж зберігатиметься посилання в parent
            current = rotate(item, great);
//          Фарбуємо поточний вузол у чорний
            current.color = Color.BLACK;
        }
//      Фарбуємо корінь у чорний, якщо в результаті ротацій, наприклад, як у сценарії №2, дідусем виявився корінь,
//      який ми раніше пофарбували у червоний
        header.right.color = Color.BLACK;
    }

Метод rotate(int item, Node parent) буде виконуватися по-різному залежно від того, що передано як параметр parent: прадідуся (great) при балансуванні другого виду або дідуся (grand) при балансуванні першого виду. Код методу:

private Node rotate(int item, Node parent) {
        // Перевіряємо, в якому піддереві відносно вузла grand/great знаходиться поточний елемент
//        Якщо менший, значить гарантовано в лівому, якщо більший – у правому
        if (item < parent.element) {
//          Отримуємо посилання на батька лівого піддерева
            Node node = parent.left;
//          Перевіряємо, яким чином виконати ротацію – праворуч,
//          якщо елемент, що вставляється, більший за елемент батька,
//          або ліворуч, якщо елемент, що вставляється, менший
            Node resultNode = item < node.element ? rotateWithLeftNode(node) : rotateWithRightNode(node);
//          Присвоюємо переданому дідусеві або прадідусеві посилання на вузол, який став новим батьком
            parent.left = resultNode;
            return parent.left;
        } else {
//          Отримуємо посилання на батька правого піддерева
            Node node = parent.right;
//          Виконуємо аналогічні дії, але для правого піддерева
            Node resultNode = item < node.element ? rotateWithLeftNode(node) : rotateWithRightNode(node);
            parent.right = resultNode;
            return parent.right;
        }
    }

Методи rotateWithLeftNode(Node element) і rotateWithRightNode(Node element) виконують такі дії:

private Node rotateWithLeftNode(Node element) {
//      Переданим елементом може бути або батько вузла current, або його дідусь
//      Отримуємо посилання на лівого нащадка елемента, переданого як параметр.
        Node left = element.left;
//      Призначаємо поточному елементу нового лівого нащадка.
//      Новим нащадком стає правий нащадок лівого нащадка
        element.left = left.right;
//      Правий нащадок лівого нащадка тепер посилається на елемент, переданий як параметр (дідуся або прадідуся),
//      тобто дідусь або прадідусь стає його правим нащадком
        left.right = element;
//      Повертаємо лівого нащадка переданого вузла
        return left;
    }

private Node rotateWithRightNode(Node element) {
//      Отримуємо посилання на правого нащадка елемента, переданого як параметр.
//      Дії аналогічні
        Node right = element.right;
        element.right = right.left;
        right.left = element;
        return right;
    }

Розберемо їх наочно. Для першого виду, коли в умову (item < grand.element != item < parent.element) ми не заходимо, ротація виглядатиме так:Для другого виду, коли ми передаємо в параметр grand (дідуся), ротація виглядатиме так:Зверніть увагу, що вузол parent перезаписався і тепер він вказує на наш current. Так як дерево після виконаної ротації все одно не перебуває в стані балансу, знову виконуємо ротацію за першим типом, як на попередній картинці. Може виникнути питання: а чому, коли викликається метод rotateWithLeftNode, ми фактично повертаємо вузли в правий бік, а коли rotateWithRightNode – у лівий? Це відбувається тому, що rotateWithLeftNode має на увазі ротацію з лівим нащадком переданого вузла, rotateWithRightNode, відповідно, – з правим. Напрямок повороту в назві методу не враховується. У такий спосіб здійснюється ротація і для складніших випадків. Корисні матеріали та посилання:

1. Стаття на вікі
2. Візуалізатор червоно-чорного дерева
3. Непогана стаття про КЧД
4. Питання про те, чи дійсно КЧД збалансоване
5. Відмінне відео дуже талановитого викладача (розповідається про AVL, але принцип схожий із КЧД)
6. Серія роликів про будову, механізм вставки та ротації

Контакти автора: Телеграм Пошта: realyte95@gmail.com