Árbol rojo-negro

Un Árbol rojo-negro es un tipo de Árbol de búsqueda auto-balanceable, una estructura de datos usada en ciencias de la computación. Fue inventada en 1972 por Rudolf Bayer quien los llamó "B-Árboles binarios simétricos"

Un Árbol rojo-negro es un árbol binario en el que cada nodo tiene un color como atributo extra, ya sea rojo o negro. El color de los nodos asegura que la trayectoria mas larga de la raíz a una hoja no es mas larga que el doble del largo de la más corta. Esto significa que el árbol esta fuertemente balanceado.

Un Árbol rojo-negro debe satisfacer estas propiedades:

• La raíz es negra
• Todas las hojas son negras
• Los nodos rojos solo pueden tener hijos negros
• Todos los caminos de un nodo a sus hojas contienen el mismo número de nodos negros

Una fuente común de confusión con estas propiedades es que se asume que todos los hijos en el árbol son hojas nulas, que no contienen datos y solo sirven para indicar donde termina el árbol. Estos nodos son a menudo omitidos en los dibujos, resultando en arboles que parecen contradictorios a los anteriores principios, pero que realmente no lo son.

Cuando los nodos son removidos o borrados, el arbol debe ser transformado para mantener estas propiedades. Esto se hace repintando o rodando los nodos.

Los nuevos nodos se insertan normalmente con el color rojo. Si el nodo padre es negro, el árbol todavia es válido. Si el nodo padre es rojo y existe un nodo tio rojo, entonces ellos deben ser repintados de negro. y el nodo abuelo debe ser repintado de rojo (Puede ser necesario continuar rapintando hacia arriba hasta llagar a la raíz). Cuando queda un nodo rojo con padre rojo se efectua una rotación. Si la raíz termina roja, ésta debe ser repintada de negro.

Vea tambien: Árbol AVL, B-Árbol, Árbol splay,