Árbol rojo-negro
Keywords: Árbol rojo-negro, 1972, B-Árbol, Ciencias de la computación, Estructura de datos, Árbol AVL, Árbol de búsqueda binario auto-balanceable
Un Árbol rojo-negro es un tipo de Árbol de búsqueda binario 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 más larga de la raíz a una hoja no es más larga que el doble del largo de la más corta. Esto significa que el árbol está 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 árbol 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 repintando hacia arriba hasta llegar 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,
Para bajar un programa en java con su código fuente del manejo completo de arboles RedBlack bajarlo desde aqui. Descargar Programa Red-black