En el post anterior, discutimos la introducción a los Árboles Rojo-Negro. En este post, se discute la inserción. En la inserción de árboles AVL, usamos la rotación como herramienta para hacer el balance después de la inserción. En el árbol Red-Black, utilizamos dos herramientas para hacer el balanceo.
- Recoloración
- Rotación
La recoloración es el cambio de color del nodo, es decir, si es rojo se cambia a negro y viceversa. Hay que tener en cuenta que el color del nodo NULL es siempre negro. Además, siempre intentamos recolorear primero, si el recoloreado no funciona, entonces pasamos a la rotación. A continuación se detalla el algoritmo. Los algoritmos tienen principalmente dos casos dependiendo del color del tío. Si el tío es de color rojo, hacemos recolorear. Si el tío es negro, hacemos rotaciones y/o recoloraciones.
La representación con la que vamos a trabajar es:
Esta representación se basa en X
Lógica:
Primero hay que insertar el nodo de forma similar a la de un árbol binario y asignarle un color rojo. Ahora, si el nodo es un nodo raíz entonces cambia su color a negro, pero si no lo es entonces comprueba el color del nodo padre. Si su color es negro, no cambies el color, pero si no lo es, es decir, es rojo, comprueba el color del tío del nodo. Si el tío del nodo tiene un color rojo entonces cambia el color del padre y del tío del nodo a negro y el del abuelo a color rojo y repite el mismo proceso para él (es decir, el abuelo).
Pero, si el tío del nodo tiene color negro entonces hay 4 casos posibles:
- Caso izquierdo (rotación LL):
- Caso derecho (rotación LR):
- Caso Derecha (rotación RR):
- Caso Izquierda (rotación RL):
Ahora, después de estas rotaciones, si los colores de los nodos no coinciden entonces recoloréalos.
Algoritmo:
Deja que x sea el nuevo nodo insertado.
- Realiza la inserción BST estándar y haz que el color de los nuevos nodos insertados sea ROJO.
- Si x es la raíz, cambia el color de x a NEGRO (la altura del árbol completo aumenta en 1).
- Haz lo siguiente si el color del padre de x no es NEGRO y x no es la raíz.
a) Si el tío de x es ROJO (El abuelo debe haber sido negro desde la propiedad 4)
(i) Cambiar el color del padre y del tío como NEGRO.
(ii) Cambia el color del abuelo como ROJO.
(iii) Cambiar x = el abuelo de x, repetir los pasos 2 y 3 para la nueva x.b) Si el tío de x es NEGRO, entonces puede haber cuatro configuraciones para x el padre de x (p) y el abuelo de x (g) (Esto es similar al árbol AVL)
(i) Caso izquierdo (p es hijo izquierdo de g y x es hijo izquierdo de p)
(ii) Caso izquierdo derecho (p es hijo izquierdo de g y x es hijo derecho de p)
(iii) Caso derecho derecho (Espejo del caso i)
(iv) Caso izquierdo derecho (Espejo del caso ii)
Ejemplo: Creación de un árbol rojo-negro con los elementos 3, 21, 32 y 17 en un árbol vacío.
Solución:
Cuando se inserta el primer elemento se inserta como nodo raíz y como nodo raíz tiene color negro por lo que adquiere el color negro.
El nuevo elemento se inserta siempre con color rojo y como 21 > 3 por lo que pasa a formar parte del subárbol derecho del nodo raíz.
Ahora, al insertar 32 vemos que hay un par padre-hijo de color rojo que viola la regla del árbol rojo-negro por lo que tenemos que rotarlo. Además, vemos las condiciones de la rotación RR (considerando el nodo nulo del nodo raíz como negro) por lo que después de la rotación como el nodo raíz no puede ser Rojo por lo que tenemos que realizar el recoloreado en el árbol dando como resultado el árbol mostrado arriba.
Ahora cuando insertamos el nuevo elemento vuelven a aparecer el nodo padre y el nodo hijo con color rojo y aquí tenemos que recolorearlos. Vemos que tanto el nodo padre como el nodo tío tienen color rojo así que simplemente cambiamos su color a negro y cambiamos el color del abuelo a rojo. Ahora, como el abuelo es el nodo raíz, volvemos a cambiar su color a negro dando como resultado el árbol mostrado arriba.
Estructura del árbol final:
El árbol final se verá así
Por favor, refiérase a C Program for Red Black Tree Insertion para la implementación completa del algoritmo anterior.
Árbol Rojo-Negro | Set 3 (Delete)