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

Червоно -чорне дерево - це вид бінарного дерева, основною суттю якого є здатність до самобалансування . Існують кілька видів дерев, що самобалансуються, але в рамках цієї статті ми торкнемося тільки червоно-чорне дерево або (КЧД) Збалансованість досягається за рахунок введення додаткового атрибуту вузла дерева - ”кольору”. У кожному вузлі дерева крім елемента зберігається 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, тобто тягнемо вузол дідуся вниз. ”А” займає місце ”B”, а потім перефарбовуємо вузол ”колишнього” дідуся до червоного , а батька до чорного . Випадок №4 . Є найскладнішим, оскільки складається з кількох етапів. Спочатку ми здійснюємо ротацію за видом № 2, що призводить до стану, описаного у випадку № 3, тобто ми зробабо ротацію, проте дерево, як і раніше, у стані розбалансування, оскільки нащадок вузла ”Z” (вузол ”А”) є червоним . Тобто зараз вузол ”А” порушує властивості КЧД і ротація проводитиметься щодо його батьківських вузлів, якими є: дідусь – вузол ”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),
    значит в дереве уже существует узел с добавляемым значенням и мы просто выходим из метода.
    Cобственно поэтому при каждом входе в метод, мы перезаписываем ссылки на корневой узел.*/
        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 - у ліву? Це відбувається тому, що rotatWithLeftNode має на увазі ротацію з лівим нащадком переданого вузла, rotateWithRightNode , відповідно, з правим. Напрямок повороту в назві методу не враховується . У такий спосіб здійснюється ротація і для складніших випадків. Корисні матеріали та посилання: 1. Стаття на вікі 2. Візуалізатор червоно-чорного дерева 3. Непогана стаття про КЧД 4. Питання про те, чи дійсно КЧД збалансовано 5. Програмний код КЧД, у кого немає облікового запису JavaRush 6. Відмінне відео дуже талановитого викладача (розповідається про AVL, але принцип схожий з КЧД) 7. Серія роликів про пристрій, механізм вставки та ротації Контакти автора: Телеграм Пошта: realyte95@gmail.com