Árbol rojo-negro. Propiedades, principios de organización, mecanismo de inserción.

El concepto de árbol rojo -negro Un árbol rojo-negro es un tipo de árbol binario, cuya esencia principal es la capacidad de autoequilibrarse. Hay varios tipos de árboles autoequilibrados, pero en este artículo solo tocaremos el árbol rojo-negro o (RCB). El equilibrio se logra introduciendo un atributo adicional del nodo del árbol: el "color". Cada nodo del árbol, además del elemento, almacena 1 bit de información sobre si el nodo es rojo o negro, y esta puede ser no sólo el color, sino también cualquier otra información que permita distinguir un tipo de nodo de otro. Por ejemplo, 1 o 0, verdadero o falso, etc. Principios de organización (propiedades) del KChD: 1. La raíz del árbol es negra . 2. Todas las hojas que no contienen datos son negras 3. Ambos hijos de cada nodo rojo son negros 4. La profundidad en los nodos negros es la misma para cualquier subárbol Las principales operaciones que se realizan en un árbol son: 1. Buscar 2. Insertar un elemento 3 Eliminar un elemento (eliminar) Las dos últimas operaciones obviamente conducen a un cambio en la estructura del árbol y, por lo tanto, su resultado puede ser un desequilibrio en el árbol. Complejidad temporal y espacial. Las operaciones de inserción, borrado y búsqueda para el QCD Time Complexity son O(log n) , donde n es el número de nodos del árbol, ya que para realizarlas necesitamos llegar al nodo deseado, descartando uno de los subárboles de cada uno. paso. En el caso de que la inserción o eliminación conduzca a una violación de las propiedades del CCH, es necesario realizar un reequilibrio. El equilibrio consta de dos operaciones: recolorear O(1) y rotar O(1). Cada operación de balanceo lleva un tiempo constante, ya que consiste en reescribir los enlaces de los elementos hijo y padre, así como información sobre su color. Sin embargo, al insertar o eliminar un elemento, puede surgir una situación en la que sea necesario equilibrar el árbol desde el nodo más bajo hasta la raíz. Dado que se garantiza que la altura máxima de un CCH que consta de n nodos no sea superior a 2log(n + 1), en el peor de los casos, el reequilibrio puede requerir operaciones log(n). El costo de memoria de la inserción es O(1) , ya que solo implica crear un nuevo nodo; las operaciones de equilibrio y repintado no requieren memoria adicional. ¿Cómo saber si un árbol está desequilibrado? Para KChD, se encuentra en un estado de equilibrio si se cumplen todas sus propiedades descritas anteriormente. Hay 4 tipos de estados de desequilibrio: 1. Desequilibrio izquierda-izquierda (LL) 2. Desequilibrio derecha-derecha (RR) 3. Desequilibrio izquierda-derecha (LR) 4. Desequilibrio derecha-izquierda (RL) Los dos primeros estados también son llamado lineal (línea), ya que visualmente se puede representar como una rama recta inclinada hacia un lado. Los dos restantes se llaman triángulos . Para equilibrar el CCH, es necesario realizar manipulaciones llamadas rotaciones. Para equilibrar estos 4 tipos, se utilizan 2 tipos de rotaciones: 1. Para LL y RR 2. Para LR y RL El primer tipo es tirar del primer nodo hacia abajo para que el medio quede en la parte superior. Visualmente, esto se puede representar como si los nodos fueran en realidad nodos de una cuerda que cuelga de un clavo: La rotación en sí se ve así: En una rotación LL complicada, cuando los nodos también tienen descendientes, el principio sigue siendo el mismo, pero el derecho El hijo del nodo, que se convierte en padre, se convierte en el hijo izquierdo/derecho del nodo que se extrae . Ejemplo: El segundo tipo (LR,RL) consta de 2 etapas y consiste en primero llevar el árbol al primer estado y luego también bajar el primer nodo: si observa esta figura, notará que simplemente nos estamos moviendo . el nodo inferior al superior , convirtiéndolo en el "nuevo" abuelo y haciendo que el "antiguo" abuelo sea un hijo izquierdo o derecho. Ejemplo: con una rotación LR/RL complicada, cuando los nodos también tienen descendientes, el principio sigue siendo el mismo, pero los antiguos descendientes del "nuevo" padre ocupan los lugares vacantes de los descendientes de los nodos secundarios. Ejemplo: Código de programa de un árbol rojo-negro Hablamos de la teoría, ahora veamos cómo se organiza el dispositivo CNC en el lenguaje de programación JAVA. La mecánica del árbol rojo-negro se utiliza, en particular, en la implementación de TreeMap , pero para mayor claridad usaremos código más simplificado. Todo comienza inicializando un campo estático privado VACÍO de tipo Nodo, que representa un nodo vacío. Los descendientes de EMPTY también son EMPTY. Nos resultará útil a la hora de insertar un elemento, ya que todas las hojas (representadas como NIL en la primera figura) se inicializan mediante este campo al insertarlo.

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

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

La estructura de clases contiene referencias al nodo actual actual , al padre del nodo actual principal , al abuelo del nodo actual grand , al bisabuelo del nodo actual grand y un puntero a la raíz del encabezado del árbol .

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;
   }

Cuando se crean, los encabezados se inicializan con el valor mínimo Integer.MIN_VALUE para que cualquier elemento siempre sea mayor que él y sus hijos siempre serán un elemento VACÍO. Todos los elementos siempre serán más grandes que el encabezado, por lo que la primera inserción siempre ocurre a la derecha del encabezado. Por lo tanto, el hijo derecho del encabezado siempre apunta a la raíz del árbol, por lo tanto, si header.right == EMPTY , entonces el árbol está vacío . En realidad lo más interesante es insertar un elemento . La estrategia para insertar un elemento en el KCHD es la siguiente: 1. Insertar un nodo y colorearlo de rojo . 2. Si la inserción provocó una violación de las propiedades del CCH, vuelva a pintar al padre, tío o abuelo y gire los nodos para que el árbol vuelva a estar en equilibrio. Hay 4 escenarios principales que pueden suceder al insertar un elemento, por conveniencia llamaremos a este elemento insertado como Z: 1. Z = raíz (el elemento que se inserta es la raíz del árbol) 2. Z.uncle = red (el tío del elemento que se está insertando es rojo ) 3. Z .uncle = negro (Línea). El tío del elemento insertado es negro y luego de insertar el elemento el árbol se desequilibró en forma de LL o RR. 4. Z.tío = negro (triángulo). El tío del elemento insertado es negro y luego de insertar el elemento el árbol se desequilibró en forma de RL o LR. Visualmente se ve así: veamos con más detalle cómo corregir la situación para cada uno de los 4 casos posibles. Caso No. 1 . Solo pintamos la raíz de negro Caso No. 2. Pintamos al abuelo de rojo y al tío de negro. Si el abuelo del nodo es la raíz, entonces el color del abuelo vuelve a pintarse de negro. Caso No. 3 . Realizamos la rotación según el tipo nº 1, es decir, tiramos del nudo del abuelo hacia abajo. "A" toma el lugar de "B", y luego cambiamos el color del "antiguo" nodo abuelo a rojo y el nodo padre a negro . Caso No. 4 . Es el más difícil porque consta de varias etapas. Primero realizamos la rotación según el tipo N° 2, lo que nos lleva al estado descrito en el caso N° 3, es decir, hemos realizado una rotación, pero el árbol aún está en estado de desequilibrio, ya que el descendiente de el nodo “Z” (nodo “A”) es rojo . Es decir, ahora el nodo "A" viola las propiedades del CCH y la rotación se realizará en relación con sus nodos padres, que son: abuelo - nodo "B", padre - nodo "Z". Realizamos la rotación nuevamente y luego volvemos a pintar el "antiguo" abuelo de rojo y el padre de negro . Volvamos al código. método insertar()

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

La parte más difícil ocurre en el método reorient() . Este método se ocupa de colorear nodos, así como de realizar rotaciones, para lo cual dentro del cuerpo se refiere al método -> rotar(int elemento, Nodo padre) , que a su vez llama al método rotarConLeftNode(Nodo elemento) o rotarConDerechoNodo(Nodo elemento) método, dependiendo de si el valor del elemento agregado es menor o mayor que el valor del hijo izquierdo o derecho del abuelo, es decir, el padre del elemento actual. Código de método:

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

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

El método turn(int item, Node parent) se ejecutará de manera diferente dependiendo de lo que se pasó como parámetro principal , genial como en el segundo tipo de equilibrio o grandioso como en el primer tipo de equilibrio. Código de método:

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

Los métodos rotarWithLeftNode(elemento de nodo) y rotarWithRightNode(elemento de nodo) realizan las siguientes acciones:

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

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

Veámoslos con claridad. Para el primer tipo, cuando no ingresamos la condición (item < grand.element != item < parent.element) , la rotación se verá así: Para el segundo tipo, cuando pasamos el parámetro grand (abuelo) al parámetro, la rotación se verá así: Tenga en cuenta que el nodo principal se ha sobrescrito y ahora apunta a nuestro archivo . Dado que el árbol aún no está en equilibrio después de completar la rotación, volvemos a realizar la rotación según el primer tipo , como en la imagen anterior. Puede surgir la pregunta: ¿por qué, cuando se llama al método rotarWithLeftNode , en realidad giramos los nodos hacia la derecha y cuando rotamosConRightNode , hacia la izquierda? Esto se debe a que rotatWithLeftNode implica rotación con el hijo izquierdo del nodo pasado, turnWithRightNode , respectivamente, con el derecho. El sentido de rotación no se tiene en cuenta en el nombre del método . De esta sencilla forma también se realiza la rotación para casos más complejos. Materiales y enlaces útiles: 1. Artículo Wiki 2. Visualizador de árbol rojo-negro 3. Buen artículo sobre KChD 4. Pregunta sobre si KChD está realmente equilibrado 5. Código del programa KChD, quién no tiene una cuenta JavaRush 6. Excelente video de un profesor muy talentoso (habla de AVL, pero el principio es similar al de KChD) 7. Una serie de videos sobre el dispositivo, el mecanismo de inserción y rotación Contactos del autor: Telegram Mail: realyte95@gmail.com