Red-Black Tree

Un tipo diferente de árbol binario de búsqueda

Nota : Este articulo estará explicado en español pero al ser un método de programación tiene conceptos o definiciones en inglés.

Para hablar de los Red-Black tree, un tipo de los árboles binarios de búsqueda, tenemos que tener bien definido que es un árbol binario de búsqueda tiene diferentes características.

• Están ordenados.
• Cada nodo tiene dos hijos (izquierdo y derecho), las hojas insertadas como NULL son hijos.
• Los hijos izquierdos de un nodo son menores.
• Los hijos derechos de un nodo son mayores.

Para profundizarte en arboles binarios de búsqueda te recomiendo este artículo.

Así mismo es bueno saber la relación que tienen los nodos al formar un árbol, ya sea padre, abuelo, tío, etc.

Un Red-Black tree es un árbol donde un bit extra define el color del nodo ya sea rojo o negro. Éste cuenta con unas reglas extra o nuevas para poder ser programado. Sirve para implementar arrays asociativos, como para recorrerlo de forma ordenada, son apreciados para la construcción de bloques en otras estructuras de datos que garantizan un peor caso, en la inserción y el borrado son mucho más eficientes que los arboles AVL. La versión persistente del árbol rojo-negro requiere un espacio O(log n) para cada inserción o borrado, además del tiempo.

Nuevas reglas:

• Un nodo es rojo o negro.
• La raíz y los NULL son negros.

Este punto puede causar un poco de ruido, ya que hay algunos autores que mencionan que las hojas son las que deben ir negras y otros que los NULL son los negros, ya que personalmente yo entiendo a las hojas como el último nodo y no los NULL. por ello me guié con este autor que dice que las hojas NULL son las negras.

• No hay dos nodos rojos consecutivos.
• Cada ruta desde un nodo hacia cualquier hoja, tiene el mismo número de nodos negros.

Una característica muy importante de los Red-Black tree es que sus tiempo de complejidad de 0(Log n)

Rotaciones

Al momento que en un Red-Black tree eliminas o insertas un nodo, éste hace una serie de rotaciones para que este árbol siempre mantenga su excelente tiempo de complejidad. Un Red-Black tree tiene una altura de 0(Log n), por lo tanto reordena constantemente sus subárboles, estos movimientos no afectan el orden de los elementos. Se dice que tiene la regla que los arboles largos van arriba y los cortos abajo (larger subtrees up, smaller subtrees down (Sambol, 2016)). Acá las reglas puntuales.

1. Alteran la estructura del árbol reordenando los subárboles.
2. Su punto principal es mantener una altura de 0(Log n).
3. No afectan el orden de los elementos, no rompen las reglas principales del árbol.

Te dejo un ejemplo de pseudocódigo, que he encontrado en una de mis referencias, con comentarios míos.

//Rotación izquierda
leftRotation(T, X){ // T es el árbol y X es el nodo a rotar
y = x.right;      // establecer y que es el hijo derecho de x
x.right = y.left; //vuelve el subárbol izquierdo de y en el subárbol derecho de x
if (y.left != T.nill){ // si el hijo derecho de y es diferente de NULL
    y.left.p = x;      //igualar x a el hijo izquierdo de y
}
y.p = x.p; //Enlazar el padre de x a y
if (x.p == T.nill){  //si x tiene padre por lo tanto no es la raíz del árbol.
    T.root = y;        //si no tiene padre es la raíz, por eso ponemos a y, o sea su hijo derecho de raíz
}else if(x == x.p.left){ //si el izquierdo de padre de x es x, hay que cambiarlo
     x.p.left = y;          //por lo tanto el izquierdo del padre de x va a ser y
}else{
     x.p.right = y;       //si no va a ser el derecho del padre de x
}
y.left = x; //pone x a la izquierda de y
x.p = y; //el padre de x es y
}

Inserción

Para insertar un nuevo nodo hay que ser muy cuidadosos. En un Red-Black tree al tener tantas reglas es muy fácil romperlas, te dejo la mejor estrategia para hacerlo.

1. Insertar nuevo nodo en rojo.
2. Cambiar color y rotar nodos para arreglar.

Existen cuatro métodos principales para poder hacer la inserción de nuevos nodos, cuando el padre es rojo, ya que cuando el padre es negro la regla de dos rojos consecutivos no es violada.

1. Cuando el nuevo nodo es la root del árbol. O sea que el árbol no existía.

2. Cuando el tío de un nuevo nodo es rojo. En este caso tanto el padre, tío y abuelo cambian de color.

3. Cuando el tío de un nuevo nodo es negro y el nuevo nodo, el padre y el abuelo hacen un triangulo. En este caso se hace una rotación.

4. Cuando el tío de un nuevo nodo es negro y el nuevo nodo, el padre y el abuelo hacen una línea. En este caso se hace una rotación.

Te dejo un ejemplo de pseudocódigo, que he encontrado en una de mis referencias, con comentarios míos.

//metodo que inserta un nuevo nodo en rojo 
RB-Insert (T, z){ //T es el árbol y z es el nuevo nodo
y = T.NULL  
x = T.root  //x es la raíz del árbol
while (x != T.NILL){  //mientras x sea diferente de NULL
  y = x;              // y va a ser igual a x
//Este procedimiento va a buscar si z va a la derecha o izquierda de la raíz
  if (z.key < x.key){ 
    x = x.left;
  }else{
    x = x.rigth;
  }
}
z.p = y; // el padre de z es y
if (y == T.NULL){    //checa si el padre de z existe de lo contrario z va a ser la raíz
  T.root = z;
}else if(z.key < y.key){  //si z es menor que y este se va a ir a la izquierda
  y.left = z;
}else{
  y.rigth = z;          //si z es mayor que y este se va a ir a la derecha
}
//apuntas  los apuntadores de z a NULL y le das el color rojo 
z.left = T.NULL;      
z.rigth = T.NULL;
z.color = RED;
RB-insertFix(T,z);  //mandas a llamar el metodo que va a arreglar las violaciones
}
//metodo que arregla las violaciones
RB-insertFix(T,z){
while (z.p.color == RED){  //mientras el color del padre de z es rojo 
    if (z.p == z.p.left){   
      y = z.p.p.rigth;      //y es el abuelo de z
      if(y.color == RED){   //si el abuelo de z es rojo
        z.p.color = BLACK;        //resuelve el caso 2
        y.color = BLACK;         
        z.p.p.color = RED;        
        z = z.p.p;                
      }else if(z == z.p.rigth){
        z = z.p                   //resuelve el caso 3
        leftRotation(T,z);        
      }
      z.p.color = BLACK;          //resuelve el caso 4
      z.p.p.color = RED;          
      rigthRotation(T,z);         
    }else{
      T.root.color = BLACK;       //resuelve el caso 1
    }
  }
}

Los Red-Black tree son muy extensos y, como todo en la vida, siempre hay algo nuevo que aprender de ellos. Espero que mi forma de verlos te haya ayudado a disfrutar el tema. (:

Referencias

Red/Black Tree

Este de arriba te lleva a una pagina para ver los procesos de inserción, eliminación, búsqueda e impresión de los Red-Black tree de forma muy visual.

Data Structures and Algorithms: Red-Black Trees

Clase RBTree (red-black tree) - Delphi - Demonak

Red-Black Tree | Set 1 (Introduction) - GeeksforGeeks

The Performance of Concurrent Red-Black Tree Algorithms

Todas las fotos y GIF utilizados en este artículo son de mi propia autoría utilizando la herramienta Canva.