Árbol rojo-negro
De Wikipedia, la enciclopedia libre
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. Esto asegura que las operaciones de inserción, eliminación y búsqueda tomen un tiempo O(logn).
Un Árbol rojo-negro debe satisfacer estas propiedades:
- La raíz es negra
- Todas las hojas son negras
- Los nodos rojos sólo 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 sólo sirven para indicar donde termina el árbol. Estos nodos son a menudo omitidos en los dibujos, resultando en árboles 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 rotando los nodos.
[editar] Inserción
En el caso de la inserción, a lo más se realiza una rotación, en contraste con otros árboles balanceados, como por ejemplo, el árbol AVL.
Los nuevos nodos se insertan normalmente con el color rojo. Entonces puede ocurrir que:
- Si el nodo padre es negro, el árbol todavía es válido.
- Si el nodo padre es rojo y existe un nodo tío 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 efectúa una rotación. Si la raíz termina roja, ésta debe ser repintada de negro.
Cabe notar que al hacer una inserción a lo más se va a realizar una rotación simple.
[editar] Véase también
[editar] Enlaces externos
