Красно-чёрное дерево. Свойства, принципы организации, механизм вставки.

Понятие красно-черного дерева Красно-черное дерево - это вид бинарного дерева, основной сутью которого является способность к самобалансировке. Существуют несколько видов самобалансирующихся деревьев, но в рамках данной статьи мы затронем только красно-черное дерево или (КЧД) Сбалансированность достигается за счет введения дополнительного атрибута узла дерева - ”цвета”. В каждом узле дерева помимо элемента хранится 1 бит информации о том, красный ли узел или черный, при этом это может быть не только цвет, но и любая другая информация позволяющая отличить один тип узла от другого. Например, 1 или 0, true или false и т. п. Принципы организации (свойства) КЧД: 1. Корень дерева черный. 2. Все листья, не содержащие данных, черные 3. Оба потомка каждого красного узла - черные 4. Глубина в черных узлах одинаковая для любого поддерева Основные операции выполняемые над деревом это: 1. Поиск (search) 2. Вставка элемента (insert) 3. Удаление элемента (delete) Последние две операции очевидно приводят к изменению структуры дерева, а следовательно, их результатом может стать нарушение сбалансированности дерева. Time и Space Complexity. Операции вставки, удаления и поиска для КЧД по Time Complexity составляют O(log n), где n - количество узлов в дереве, поскольку для их выполнения нам нужно дойти до нужного узла, на каждом шаге отметая одно из поддеревьев. В случае, когда вставка или удаление привели к нарушению свойств КЧД, необходимо выполнить перебалансировку. Балансировка состоит из 2-ух операций: перекраска 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) состоит из 2-ух этапов и заключается в том, чтобы сначала привести дерево к первому состоянию, а затем также потянуть первый узел вниз: Если посмотреть на данный рисунок, то можно заметить, что мы просто переносим нижний узел наверх, делая его ”новым” дедушкой, а ”бывшего” дедушку делаем либо левым либо правым потомком. Пример: При усложненной 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. Наглядно это выглядит так: Разберем поподробнее исправление ситуации для каждого из 4-ех возможных случаев. Случай № 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