Árbol rojo-negro | Serie 1 (Introducción)

Introducción:

Un árbol rojo-negro es una especie de árbol de búsqueda binario autoequilibrado en el que cada Node tiene un bit adicional, y ese bit a menudo se interpreta como el color (rojo o negro). Estos colores se utilizan para garantizar que el árbol permanezca equilibrado durante las inserciones y eliminaciones. Aunque el equilibrio del árbol no es perfecto, es lo suficientemente bueno para reducir el tiempo de búsqueda y mantenerlo alrededor del tiempo O(log n), donde n es el número total de elementos en el árbol. Este árbol fue inventado en 1972 por Rudolf Bayer. 

Debe tenerse en cuenta que como cada Node requiere solo 1 bit de espacio para almacenar la información de color, estos tipos de árboles muestran huellas de memoria idénticas al árbol de búsqueda binario clásico (sin color). 

Reglas que sigue cada árbol rojo-negro: 

1. Cada Node tiene un color rojo o negro.
2. La raíz del árbol es siempre negra.
3. No hay dos Nodes rojos adyacentes (un Node rojo no puede tener un padre rojo o un hijo rojo).
4. Cada ruta desde un Node (incluida la raíz) a cualquiera de sus Nodes NULL descendientes tiene el mismo número de Nodes negros.
5. Todos los Nodes hoja son Nodes negros.

¿Por qué árboles rojos y negros?

La mayoría de las operaciones BST (p. ej., búsqueda, máximo, mínimo, inserción, eliminación, etc.) toman el tiempo O(h), donde h es la altura del BST. El costo de estas operaciones puede convertirse en O(n) para un árbol binario sesgado. Si nos aseguramos de que la altura del árbol siga siendo O(log n) después de cada inserción y eliminación, podemos garantizar un límite superior de O(log n) para todas estas operaciones. La altura de un árbol Rojo-Negro siempre es O(log n) donde n es el número de Nodes en el árbol. 

No Señor.	Algoritmo	Complejidad del tiempo
1.	Búsqueda	O (registro n)
2.	Insertar	O (registro n)
3.	Borrar	O (registro n)

“n” es el número total de elementos en el árbol rojo-negro. 

Comparación con el árbol AVL :
los árboles AVL están más equilibrados en comparación con los árboles rojo-negro, pero pueden causar más rotaciones durante la inserción y eliminación. Entonces, si su aplicación implica inserciones y eliminaciones frecuentes, entonces se deben preferir los árboles rojo-negro. Y si las inserciones y eliminaciones son menos frecuentes y la búsqueda es una operación más frecuente, entonces se debe preferir el árbol AVL al árbol rojo-negro.

¿Cómo asegura el equilibrio un árbol rojo-negro?
Un ejemplo simple para entender el equilibrio es que una string de 3 Nodes no es posible en el árbol Rojo-Negro. Podemos probar cualquier combinación de colores y ver si todos violan la propiedad del árbol rojo-negro. 

Puntos interesantes sobre Red-Black Tree:

1. La altura negra del árbol rojo-negro es el número de Nodes negros en un camino desde el Node raíz hasta un Node hoja. Los Nodes de hoja también se cuentan como Nodes negros. Entonces, un árbol rojo-negro de altura h tiene una altura negra >= h/2.
2. La altura de un árbol rojo-negro con n Nodes es h<= 2 log ₂ (n + 1).
3. Todas las hojas (NIL) son negras.
4. La profundidad de negro de un Node se define como el número de Nodes negros desde la raíz hasta ese Node, es decir, el número de ancestros negros.
5. Cada árbol rojo-negro es un caso especial de un árbol binario.

Altura negra de un árbol rojo-negro: 

La altura negra es el número de Nodes negros en un camino desde la raíz hasta una hoja. Los Nodes de hoja también se cuentan como Nodes negros. De las propiedades anteriores 3 y 4, podemos derivar que un árbol rojo-negro de altura h tiene una altura negra >= h/2 . 

El número de Nodes desde un Node hasta su hoja descendiente más lejana no es más del doble que el número de Nodes hasta la hoja descendiente más cercana.

Cada Árbol Rojo Negro con n Nodes tiene una altura <= 2Log ₂ (n+1) 
Esto se puede probar usando los siguientes hechos:

1. Para un árbol binario general, sea k el número mínimo de Nodes en todas las rutas raíz a NULL, luego n >= 2 ^k – 1 (Ej. Si k es 3, entonces n es al menos 7). Esta expresión también se puede escribir como k <= Log ₂ (n+1).
2. A partir de la propiedad 4 de los árboles rojo-negro y la afirmación anterior, podemos decir que en un árbol rojo-negro con n Nodes, hay un camino de raíz a hoja con como máximo Log ₂ (n+1) Nodes negros.
3. De las propiedades 3 y 5 de los árboles rojo-negro, podemos afirmar que el número de Nodes negros en un árbol rojo-negro es al menos ⌊ n/2 ⌋ donde n es el número total de Nodes.

De los puntos anteriores, podemos concluir el hecho de que Red Black Tree con n Nodes tiene una altura <= 2Log ₂ (n+1)

Operación de búsqueda en el árbol rojo-negro:

Como cada árbol rojo-negro es un caso especial de un árbol binario, el algoritmo de búsqueda de un árbol rojo-negro es similar al de un árbol binario.

Algoritmo:

searchElement (tree, val)
Step 1:
If tree -> data = val OR tree = NULL
    Return tree
Else
If val < data
        Return searchElement (tree -> left, val)
    Else
        Return searchElement (tree -> right, val)
    [ End of if ]
[ End of if ]

Step 2: END

Para el programa, puede consultarlo para el árbol AVL . 

Ejemplo: Buscar 11 en el siguiente árbol rojo-negro. 
 

Solución: 

1. Empezar desde la raíz.
2. Compare el elemento de inserción con la raíz, si es menor que la raíz, luego repita para la izquierda, de lo contrario repita para la derecha.
3. Si el elemento a buscar se encuentra en cualquier lugar, devuelve verdadero, de lo contrario, devuelve falso.

En esta publicación, presentamos árboles Rojo-Negro y discutimos cómo se asegura el equilibrio. La parte difícil es mantener el equilibrio cuando se agregan y eliminan claves. También hemos visto cómo buscar un elemento del árbol rojo-negro. Pronto discutiremos las operaciones de inserción y eliminación en las próximas publicaciones en el árbol Rojo-Negro.

Ejercicio:

1) ¿Es posible tener todos los Nodes negros en un árbol rojo-negro? 
2) ¿ Dibujar un árbol rojo-negro que no sea un árbol AVL en cuanto a la estructura?

Inserción y Eliminación

Inserción de árbol  
rojo-negro Eliminación de árbol rojo-negro 

Aplicaciones: 

1. La mayoría de las funciones de la biblioteca BST de autoequilibrio, como map, multiset y multimap en C++ (o paquetes java como java.util.TreeMap y java.util.TreeSet) usan Red-Black Trees.
2. Se utiliza para implementar CPU Scheduling Linux. Completely Fair Scheduler lo usa.
3.  También se utiliza en el algoritmo de agrupación en clústeres K-mean en el aprendizaje automático para reducir la complejidad del tiempo.
4.  Además, MySQL también usa el árbol rojo-negro para índices en tablas para reducir el tiempo de búsqueda e inserción.

Referencias:

• Introducción a los algoritmos 3.ª edición por Clifford Stein, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
• http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
• Conferencia en video sobre el árbol rojo y negro por Tim Roughgarden
• Video conferencia del MIT sobre el árbol rojo-negro
• Notas de la conferencia del MIT sobre el árbol rojo-negro