Red-black tree. Properties, principles of organization, insertion mechanism.

The concept of a red -black tree A red-black tree is a type of binary tree, the main essence of which is the ability to self-balance. There are several types of self-balancing trees, but in this article we will only touch on the red-black tree or (RCB). Balance is achieved by introducing an additional attribute of the tree node - “color”. Each tree node, in addition to the element, stores 1 bit of information about whether the node is red or black, and this can be not only the color, but also any other information that allows one to distinguish one type of node from another. For example, 1 or 0, true or false, etc. Principles of organization (properties) of the KChD: 1. The root of the tree is black . 2. All leaves that do not contain data are black 3. Both children of each red node are black 4. The depth in black nodes is the same for any subtree The main operations performed on a tree are: 1. Search 2. Insert an element 3 Deleting an element (delete) The last two operations obviously lead to a change in the structure of the tree, and therefore, their result may be an imbalance in the tree. Time and Space Complexity. The insertion, deletion and search operations for the Time Complexity QCD are O(log n) , where n is the number of nodes in the tree, since to perform them we need to get to the desired node, discarding one of the subtrees at each step. In the case where insertion or deletion leads to a violation of the properties of the CCH, it is necessary to perform rebalancing. Balancing consists of two operations: recoloring O(1) and rotation O(1). Each balancing operation takes constant time, since it consists of rewriting the links of child and parent elements, as well as information about their color. However, when inserting or deleting an element, a situation may arise in which the tree needs to be balanced from the lowest node all the way to the root. Since it is guaranteed that the maximum height of a CCH consisting of n nodes is no more than 2log(n + 1), then in the worst case, rebalancing can take log(n) - operations. The memory cost of insertion is O(1) since it only involves creating a new node; balancing and repainting operations do not require additional memory. How can you tell if a tree is out of balance? For KChD, it is in a state of balance if all its properties described earlier are met. There are 4 types of imbalance states: 1. Left-left imbalance (LL) 2. Right-right imbalance (RR) 3. Left-right imbalance (LR) 4. Right-left imbalance (RL) The first two states are also called linear (Line ), since visually it can be represented as a straight branch skewed to one side. The remaining two are called triangles . To bring the CCH into a state of balance, it is necessary to perform manipulations on it called rotations. To balance these 4 types, 2 types of rotations are used: 1. For LL and RR 2. For LR and RL The first type is to pull the first node down so that the middle is at the top. Visually, this can be represented as if the nodes were really nodes on a rope that hangs on a nail: The rotation itself looks like this: With a complicated LL rotation, when nodes also have descendants, the principle remains the same, but the right child of the node, which becomes parent, becomes the left/right child of the node being pulled . Example: The second type (LR,RL) consists of 2 stages and consists in first bringing the tree to the first state, and then also pulling the first node down: If you look at this figure, you will notice that we are simply moving the bottom node to the top , making it the “new” grandfather, and making the “former” grandfather either a left or right child. Example: With a complicated LR/RL rotation, when nodes also have descendants, the principle remains the same, but the former descendants of the “new” parent take the vacated places of the descendants of the child nodes. Example: Program code of a red -black tree We talked about the theory, now let’s see how the CNC device is organized in the JAVA programming language. The red-black tree mechanics are used, in particular, in the TreeMap implementation , but for clarity we will use more simplified code. It all starts by initializing a private static field EMPTY of type Node, which represents an empty node. The descendants of EMPTY are also EMPTY. It will be useful to us when inserting an element, since all sheets (represented as NIL in the first figure) are initialized by this field upon insertion.

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

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

The class structure contains references to the current node current , the parent of the current node parent , the grandfather of the current node grand , the great-grandfather of the current node great , and a pointer to the root of the tree 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;
   }

When created, headers are initialized to the minimum value Integer.MIN_VALUE so that any element will always be greater than it, and its children will always be an empty EMPTY element. All elements will always be larger than the header, so the first insertion always occurs to the right of the header. Thus, the right child of header always points to the root of the tree, therefore, if header.right == EMPTY , then the tree is empty . Actually, the most interesting thing is inserting an element . The strategy for inserting an element into the KCHD is as follows: 1. Insert a node and color it red . 2. If the insertion led to a violation of the properties of the CCH, then repaint the parent, uncle or grandfather and rotate the nodes to bring the tree back into a state of balance. There are 4 main scenarios that can happen when inserting an element, for convenience let's call this inserted element as Z: 1. Z = root (the element being inserted is the root of the tree) 2. Z.uncle = red (the uncle of the element being inserted is red ) 3. Z .uncle = black (Line). The uncle of the inserted element is black and after inserting the element the tree became unbalanced in the form of LL or RR. 4. Z.uncle = black (triangle). The uncle of the inserted element is black and after inserting the element the tree became unbalanced in the form of RL or LR. Visually it looks like this: Let’s look in more detail at correcting the situation for each of the 4 possible cases. Case No. 1 . We just paint the root black. Case No. 2. We paint the grandfather red , and the uncle black. If the grandfather of the node is the root, then the color of the grandfather is again painted black. Case No. 3 . We carry out rotation according to type No. 1, that is, we pull the grandfather’s knot down. “A” takes the place of “B”, and then we recolor the “former” grandfather node red and the parent node black . Case No. 4 . It is the most difficult because it consists of several stages. First, we carry out rotation according to type No. 2, which leads us to the state described in case No. 3, that is, we have performed a rotation, but the tree is still in a state of imbalance, since the descendant of node “Z” (node ​​“A”) is red . That is, now node “A” violates the properties of the CCH and rotation will be carried out relative to its parent nodes, which are: grandfather - node “B”, parent - node “Z”. We perform the rotation again, and then repaint the “former” grandfather red and the parent black . Let's get back to the code. insert() method

public void insert(int item) {
//        Сохраняем ссылку на header в current, parent и grand
        current = parent = grand = header;
//        Инициализируем все пустые элементы дерева (листы NIL) числом, которое мы хотим вставить
        EMPTY.element = item;
//        Итерируемся в цикле до тех пор, пока meaning текущего element не станет равно добавляемому (item)
        while (current.element != item) {
//        Изменяем значения 4 ссылок в цикле для итерации в глубину дерева
//        (прадеда на деда, деда на отца, отца на текущий узел)
            great = grand;
            grand = parent;
            parent = current;
//        текущий узел на его правого or левого сына в зависимости от того,
//        больше ли текущий элемент добавляемого or меньше,
//        то есть идем в левое поддерево, если меньше, or в правое, если больше
            current = item > current.element ? current.right : current.left;
//          На каждой итерации проверяем левый сын текущего element и правый сын текущего element красные
            if (current.left.color == Color.RED && current.right.color == Color.RED) {
//           Если да, то вызываем метод для исправления и переориентации дерева относительно текущего element
//           Который записан в current на текущей итерации
                reorient(item);
            }
        }
/*  При выходе из цикла проверяем, является ли current узел пустым листом.
    Если meaning добавляемого числа оказалось равно текущему узлу,
    но при этом мы не дошли до листа (current != Empty),
    значит в дереве уже существует узел с добавляемым meaningм и мы просто выходим из метода.
    Cобственно поэтому при каждом входе в метод, мы перезаписываем ссылки на корневой узел.*/
        if (current != EMPTY) {
            return;
        }
//      Если мы все же дошли до пустого листа, создаем новый узел и инициализируем его потомков пустыми листами
        current = new Node(item, EMPTY, EMPTY);
//      Проверяем, Howим сыном будет являться текущий узел, левым or правым
        if (item < parent.element) {
            parent.left = current;
        } else {
            parent.right = current;
        }
//      красим текущий узел в красный, его листы в чёрный, а также осуществляем перебалансировку
//      в случаях, если parent оказался красным
        reorient(item);
    }

The hardest part happens in the reorient() method . This method deals with coloring nodes, as well as performing rotations, for which inside the body it refers to the -> rotate(int item, Node parent) method , which in turn calls the rotateWithLeftNode(Node element) or rotateWithRightNode(Node element) method , depending depending on whether the value of the added element is less than or greater than the value of the left or right child of the grandfather, that is, the parent of the current element. Method code:

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;
//          Если текущий элемент левее родителя, но правее деда or наоборот, то вызываем ротацию для родителя.
//          То есть фактически определяем, Howого вида балансировку применить первого or второго
            if (item < grand.element != item < parent.element) {
//          Если второго, то сначала передаем дедушку текущего element и осуществляем поворот влево or вправо,
//          одновременно изменяя ссылку на parent, в результате родителем станет сам current
                parent = rotate(item, grand);
            }
//          Осуществляем ротацию первого вида. Поскольку в результате такого поворота дедушка станет потомком родителя
//          текущего element, то нам нужно перезаписать ссылку на нашего родителя у прадедушки, поэтому мы и передаем
//          ссылку именно на прадеда. Если прадеда в нашем маленьком дереве еще нет, то на него будет указывать HEAD

//          Если балансировка идет по первому виду, то current'ом станет родитель текущего current
//          Если по второму, то current'ом будет сам вставляемый элемент, на него же будет храниться link в parent
            current = rotate(item, great);
//          красим текущий узел в чёрный
            current.color = Color.BLACK;
        }
//      красим корень в черный, если в результате ротаций, например, How в сценарии № 2 дедушкой оказался корень
//      который мы ранее покрасor в красный
        header.right.color = Color.BLACK;
    }

The rotate(int item, Node parent) method will be executed differently depending on what was passed as the parent parameter , great as in the second type of balancing, or grand as in the first type of balancing. Method code:

private Node rotate(int item, Node parent) {
        // Проверяем в Howом поддереве относительно grand/great узла находится текущий элемент
//        Если меньше, значит, гарантированно в левом, если больше - в правом
        if (item < parent.element) {
//          Получаем ссылку на родителя левого поддерева
            Node node = parent.left;
//          Проверяем Howим образом выполнить ротацию - справа
//          если вставляемый элемент больше, чем элемент родителя,
//          or слева, если вставляемый элемент меньше
            Node resultNode = item < node.element ? rotateWithLeftNode(node) : rotateWithRightNode(node);
//          присваиеваем переданному дедушке or прадедушке ссылку на узел, который стал новым родителем
            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;
        }
    }

The rotateWithLeftNode(Node element) and rotateWithRightNode(Node element) methods perform the following actions:

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

private Node rotateWithRightNode(Node element) {
//      Получаем ссылку на правого потомка передаваемого в параметр element.
//      Действия аналогичны
        Node right = element.right;
        element.right = right.left;
        right.left = element;
        return right;
    }

Let's look at them clearly. For the first type, when we do not enter the condition (item < grand.element != item < parent.element) , the rotation will look like this: For the second type, when we pass the grand (grandfather) parameter to the parameter, the rotation will look like this: Please note that the parent node has been overwritten and now points to our current . Since the tree is still not in balance after the completed rotation, we again perform rotation according to the first type , as in the previous picture. The question may arise: why, when the rotateWithLeftNode method is called , do we actually rotate the nodes to the right, and when rotateWithRightNode - to the left? This is because rotatWithLeftNode implies rotation with the left child of the passed node, rotateWithRightNode , respectively, with the right one. The direction of rotation is not taken into account in the method name . In this simple way, rotation is also carried out for more complex cases. Useful materials and links: 1. Wiki article 2. Red-black tree visualizer 3. Nice article about KChD 4. Question about whether KChD is really balanced 5. KChD program code, who doesn’t have a JavaRush account 6. Excellent video by a very talented teacher (talks about AVL, but the principle is similar to KChD) 7. A series of videos about the device, insertion and rotation mechanism Author's contacts: Telegram Mail: realyte95@gmail.com