Download Cap. 12. Árboles coloreados. Red Black Trees

1
Capítulo 12.
Árboles coloreados. Red black.
Si las claves siempre ingresan ordenadas en forma aleatoria, puede emplearse un árbol binario
de búsqueda. Sin embargo si por momentos se producen ingresos de claves en orden, debe
escogerse una estructura que pueda rebalancear dinámicamente el árbol. El árbol coloreado,
como se verá, tiene un criterio de balance un tanto más relajado que un AVL.
Por esta razón, si los datos ingresan preponderantemente ordenados el árbol AVL tiene un mejor
comportamiento que el red-black, ya que tiene una altura menor.
Si los datos son accesados mayormente en forma secuencial, el árbol desplegado, splay, tiene un
mejor comportamiento que los anteriores.
12.1. Propiedades de los árboles coloreados.
Se agrega a cada nodo un dato que indica su color. Existen reglas que deben cumplirse para
asignar el color a cada nodo, de tal modo que una trayectoria cualquiera desde un nodo a una
hoja no sea mayor que el doble del largo de cualquier otra. Esto asegura que el árbol coloreado
se mantenga más o menos balanceado, asegurando un costo logarítmico para las operaciones en
peor caso.
Propiedades:
1. Cualquier nodo es rojo o negro.
2. Cualquier descendiente de hoja se considera negro. (Los nodos externos, son negros; éstos no
son nodos con información.) La raíz debe ser negra.
3. Si un nodo es rojo, sus hijos son negros. No hay dos rojos adyacentes.
4. Cualquier trayecto desde un nodo hacia una hoja contiene el mismo número de nodos negros.
La Figura 15.1 muestra los nodos con valores 4, 7, 12 y 20 de color rojo. La estructura cumple
las propiedades anteriores.
9
15
4
2
5
12
20
7
Figura 12.1 Árbol de búsqueda binaria coloreado.
Profesor Leopoldo Silva Bijit
26-05-2008
2
Estructuras de Datos y Algoritmos
Una buena interpretación de los nodos rojos en un árbol coloreado, es dibujarlos en un nivel
horizontal, de este modo se refleja que no alteran las alturas negras de los nodos. Esto se
muestra en la Figura 12.2, para el árbol coloreado de la Figura 12.1. En la representación con
rojos en nivel horizontal, debe cuidarse que cada nodo tenga dos hijos, para que el árbol sea
binario.
También puede verse, con esta representación, que en un árbol coloreado todas las hojas tienen
la misma altura. El árbol coloreado es un caso particular de un B-Tree, en los cuales los nodos
pueden almacenar varias claves.
4
2
9
5
7
12
15
20
Figura 12.1a Árbol coloreado con rojos horizontales.
Debido a la presencia de nodos rojos, al menos la mitad de los nodos de un trayecto de un nodo
hasta las hojas deben ser negros.
La trayectoria más larga, una que alterna entre nodos rojos y negros, es sólo el doble del largo
de la trayectoria más corta, la formada sólo por nodos negros.
Figura 12.2 Trayectos en peor caso.
Luego de insertar desde el 1 hasta el 14, que es un peor caso de árbol binario de búsqueda, en el
árbol coloreado que se muestra en la Figura 12.2, el trayecto más largo es de 6 nodos por la vía
más larga y de tres nodos por la más corta.
En la Figura 12.2, puede comprobarse que las alturas negras de todos los nodos son iguales, y
que no hay dos rojos adyacentes; además la raíz es negra, cumpliendo todas las propiedades.
Profesor Leopoldo Silva Bijit
26-05-2008
Árboles coloreados
3
12.2. Complejidad en árboles coloreados.
En un árbol coloreado, con n nodos internos, debe cumplirse que la altura h es a lo más:
h 2log(n 1)
Se define la función altura negra de un nodo x, bh(x), como el número de nodos negros de
cualquier trayectoria desde x hasta una hoja, no contando el nodo x.
Se desea probar, mediante inducción, que un subárbol, que parte en el nodo x, contiene a lo
menos 2bh(x)-1 nodos internos.
Si x es un nodo externo, entonces bh(x) = 0, y el número de nodos internos es: 20-1=0.
Si x es una hoja, entonces bh(x) = 1, y el número de nodos internos es: 21-1=1.
Si x tiene alto h, los nodos hijos de x, tienen altura (h-1).
Si el hijo es rojo tiene altura negra: bh(x), igual a la del padre
Si el hijo es negro tiene altura negra: bh(x)-1, ya que no se cuenta el nodo negro.
Considerando verdadera la proposición para el número de nodos internos del subárbol que
comienza en x; los subárboles de los hijos de x, deben entonces tener a lo menos: 2bh(x)-1-1
nodos internos.
Para obtener el número de nodos internos del subárbol que comienza en x, sumamos los nodos
internos de los subárboles hijos, más el nodo interno x, se obtiene:
n >= (2bh(x)-1-1) + (2bh(x)-1-1) + 1 = 2(2bh(x)-1) - 1=2bh(x)-1
Lo cual demuestra la proposición inicial.
Pero en un árbol coloreado al menos la mitad de los nodos de un trayecto de un nodo hasta las
hojas deben ser negros, entonces si h es la altura de un árbol, que comienza en x, se tiene que:
bh( x)
h
2
Entonces, reemplazando en la expresión de n, en función de bh(x), la cota para bh(x), se obtiene:
n 2bh( x) 1 2h / 2 1
Despejando h, se logra:
h 2log(n 1)
(log(n))
Debe notarse que ésta es la complejidad de peor caso.
Al insertar o descartar nodos en un árbol coloreado, pueden violarse las propiedades que los
definen; y para mantenerlo coloreado, como se verá más adelante, deben cambiarse los colores
Profesor Leopoldo Silva Bijit
26-05-2008
4
Estructuras de Datos y Algoritmos
de algunos nodos y también posiblemente efectuar rotaciones. Esto se refleja en un costo
adicional para las funciones de inserción y descarte en un árbol binario de búsqueda.
Para un árbol AVL, la cota para la altura resulta menor que en árbol coloreado:
hAVL
1, 4404 log(n)
(log(n))
La Figura 12.2a, muestra la complejidad del árbol coloreado, respecto del AVL, y puede
observarse que son muy similares. Pero las operaciones se realizan en menor tiempo, en un
árbol coloreado.
En un árbol binario de búsqueda, en promedio, si las claves llegan aleatoriamente, se tiene la
(log(n)) . Pero ésta se incrementa hasta n, en el peor caso.
altura: hBST 1,3863log( n)
coloreado
AVL
Bst promedio
balanceado
Figura 12.2a. Comparación de complejidades. Red-Black, AVL, Balanceado.
12.3. Análisis de inserción.
La inserción de un nuevo nodo siempre se realiza como descendiente de una hoja. Se inserta el
nuevo nodo con color rojo, ya que esto no altera las alturas negras de los trayectos. Cuando la
hoja donde se insertará el nuevo nodo es roja, se pierde la propiedad de ser un árbol coloreado,
ya que se producen dos nodos rojos adyacentes.
Si se inserta un nodo con color rojo, y si el árbol estaba vacío, debe cambiarse a negro para
mantener la propiedad de que la raíz sea negra.
Si se inserta un nodo en la raíz, como ésta es negra, se mantienen las propiedades de los árboles
coloreados.
En caso de inserción en árboles de mayores niveles, la inserción de un rojo en una hoja roja
requiere efectuar modificaciones para preservar las propiedades, en algunos casos bastará una
Profesor Leopoldo Silva Bijit
26-05-2008
Árboles coloreados
5
recoloración y en otros deben efectuarse rotaciones. A medida que se van efectuando estas
modificaciones puede que en el ascenso hacia la raíz se vuelva a producir la situación de dos
rojos adyacentes. Estudiaremos los diferentes casos que se producen y las soluciones propuestas
para mantener las propiedades.
Lo primero que observamos es que cuando se produce un doble rojo, el abuelo del nodo rojo
insertado o del rojo que asciende debe ser negro, a este último nodo lo denominaremos con x, en
los diagramas. Esto es así ya que antes de la inserción el árbol era coloreado, y por lo tanto no
pueden tenerse tres rojos adyacentes. La segunda consideración es que las alturas negras del
nodo denominado abuelo deben ser iguales antes y después de la inserción; esto se ilustrará en
los diagramas, colocando nodos negros de tal modo de reflejar las alturas negras iguales. Se
prefiere esta representación a la de mostrar subárboles descendientes con especificaciones de
alturas negras. Una tercera consideración es que el tío del nodo rojo que asciende puede ser
negro o rojo, y que deberán analizarse ambos casos.
Se ilustran en la Figura 12.3, alturas negras del abuelo iguales a dos (más la altura negra de los
descendientes, que no se muestran), se muestra el tío de color negro.
Dicho de otra forma, el diagrama insinúa que las alturas negras del tío y de los hijos negros de
los nodos rojos deben ser iguales, y menores en una unidad a la altura negra del abuelo.
abuelo
abuelo
tío
tío
x
x
Figura 12.3 Dobles rojos en inserción.
Existen dos casos adicionales, que son las imágenes especulares de las mostradas en la Figura
12.3, y que corresponden a los casos en que el nodo x es insertado como descendiente derecho
del nodo abuelo.
Existen dos situaciones que deben analizarse: una corresponde a tío rojo, la otra a tío negro.
12.3.1. Recoloración. Cuando el tío es rojo.
Si en la Figura 12.4 a la izquierda, se cambian los colores del abuelo, el padre y el tío, se
mantienen las alturas negras del nodo abuelo hacia abajo, y no se tienen dos rojos adyacentes.
Sin embargo es necesario seguir la revisión ascendente debido a que el cambio de color del
abuelo podría producir nuevamente un doble rojo en el trayecto hacia la raíz. Es decir debe
volver a repetirse el proceso ascendiendo el puntero x a la posición del abuelo.
Si los cambios se propagarán hasta el caso en que el abuelo es la raíz, debería cambiarse el color
de ésta, pero se mantendrían altura negras iguales; en este caso aumenta la altura negra del
árbol.
Profesor Leopoldo Silva Bijit
26-05-2008
6
Estructuras de Datos y Algoritmos
abuelo
padre
abuelo
padre
tío
x
tío
x
Figura 12.4 Recoloración en inserción. Tío rojo.
Cuando el nodo denominado x es descendiente derecho del padre, se soluciona de igual forma.
12.3.2. Rotaciones. Cuando el tío es negro.
Se ilustra el caso en que el padre y el nodo x son descendientes izquierdos del nodo abuelo. Si se
cambian colores al padre y al abuelo, se disuelve el doble rojo. Sin embargo se altera la altura
negra del subárbol derecho del abuelo, como se muestra en la Figura 12.5, disminuye su cuenta
en uno.
abuelo
padre
abuelo
tío
x
padre
tío
x
Figura 12.5 Recoloración con tío negro, no quedan dos rojos adyacentes.
Si se efectúa una rotación a la derecha de la pareja padre-abuelo, en la Figura 12.5 a la derecha
se tiene la Figura 12.6 derecha.
A partir del nodo padre hacia abajo se mantienen los largos negros de los subárboles y además
no se puede volver a producir un doble rojo en el trayecto de ascenso hacia la raíz, ya que el
nodo, denominado padre, en la Figura 12.6 derecha, es negro. Nótese que en la Figura 12.6 a la
derecha, se han conservado los nombres originales para los nodos: padre, abuelo y tío; sin
embargo luego de la rotación éstos nombres pierden su significado original. También puede
observarse que luego de la rotación el sub-árbol, cuya raíz es el padre, queda más balanceado.
Esta situación da por terminada la revisión ascendente.
abuelo
padre
tío
padre
abuelo
x
x
tío
Figura 12.6 Rotación derecha, preserva altura negras.
Profesor Leopoldo Silva Bijit
26-05-2008
Árboles coloreados
7
Aún resta analizar el caso en que el doble rojo se produce como hijo derecho de un padre rojo
descendiente de un abuelo negro (y con tío negro). Lo cual se ilustra en la Figura 12.7.
abuelo
padre
abuelo
tío
x
tío
padre
x
Figura 12.7. Rotación izquierda, par padre-x.
Antes de producirse este doble rojo, ya sea por inserción o por revisión ascendente, las alturas
negras del padre (del abuelo y sus ancestros) eran iguales. La rotación izquierda del par xpadre, respecto al padre, no altera esas cuentas. La Figura 12.7 a la derecha, es el caso analizado
antes, que se muestra en la Figura 12.5; para el cual ya se obtuvo una solución, pero cambiando
el puntero x a la posición ocupada finalmente por el padre.
Los casos en que el nodo x es agregado como descendiente del subárbol derecho del abuelo son
situaciones con simetría especular a los tratados.
Un caso particular es cuando el tío no existe, es decir cuando es un nodo externo; en este caso se
considera tío de color negro.
Esto completa el análisis de la inserción en un árbol coloreado.
12.4. Análisis de la operación descartar.
Deben analizarse tres casos, que el nodo que se desea descartar tenga dos descendientes, uno
solo o ninguno.
Cuando se borra un nodo rojo se mantienen las propiedades de los árboles coloreados. Ya que
no cambian las alturas negras de los nodos.
12.4.1. Dos descendientes.
Cuando se borra un nodo apuntado por t, que tiene los dos subárboles descendientes, se elige el
mayor descendiente del subárbol izquierdo (I) o el menor descendiente del subárbol derecho (D)
y se cambian los datos del nodo que será eliminado con el seleccionado. Si el nodo seleccionado
(I o D) es rojo, no puede tener descendientes y será una hoja; estos casos se muestran en la
Figura 12.8.
Profesor Leopoldo Silva Bijit
26-05-2008
8
Estructuras de Datos y Algoritmos
t
t
I D
D
I
Figura 12.8. Nodo seleccionado para ser descartado es hoja roja.
Si el nodo seleccionado es negro, sólo puede tener un hijo rojo ya que el árbol es coloreado,
antes del descarte. Situación que se muestra en la Figura 12.9.
t
t
I D
I
D
Figura 12.9. Nodo seleccionado para ser descartado es nodo negro con hijo rojo.
Luego de copiar los datos del nodo seleccionado en el nodo apuntado por t, se procede a
descartar el seleccionado; el cual debe ser una hoja roja o un nodo negro con sólo un hijo que
debe ser rojo. Estos casos se analizan a continuación.
12.4.2. Un descendiente.
Cuando se descarta un nodo t con un solo hijo, se presentan tres casos, que se ilustran en la
Figura 12.10, cuando t tiene hijo izquierdo y es un descendiente izquierdo. Debe notarse que el
nodo t debe ser negro, y que su único hijo debe ser rojo.
t
t
t
Figura 12.10 Descartar nodo negro con un hijo rojo.
Se preservan las propiedades de los árboles coloreados si se liga el hijo de t, con el padre de
éste; y se le cambia el color a negro, para mantener iguales alturas negras, y no tener dos rojos
adyacentes. Igual solución se aplica si el hijo de t es descendiente derecho.
Las soluciones se muestran en la Figura 12.10a.
t
t
t
Figura 12.10a Descartar nodo negro con un hijo rojo.
Profesor Leopoldo Silva Bijit
26-05-2008
Árboles coloreados
9
Si t es descendiente derecho, la solución es la especular de la analizada.
12.4.3. El nodo a descartar es una hoja. Sin descendientes.
En este caso se presentan cinco situaciones, que se ilustran en la Figura 12.11.
t
t
t
t
t
Figura 12.11 Descartar hoja.
Cuando el padre es rojo, éste debe tener dos hijos negros. Luego de borrar el nodo hay que
cambiar el color del padre y del tío; esto preserva iguales alturas negras.
Cuando el nodo para descartar es rojo, hay dos casos: con hermano nulo o con hermano rojo.
Ambos casos no requieren modificaciones, y sólo es preciso borrar el nodo.
Cuando el nodo y su padre son negros se tienen dos casos, con hermano negro o rojo. En este
último caso, luego de borrar el nodo el árbol deja de ser coloreado, ya que disminuye la altura
negra del subárbol izquierdo; se soluciona rotando a la izquierda, el par padre-hermano, y
cambiando de rojo a negro el color del nuevo padre, para igualar las alturas negras. Lo cual se
muestra en la Figura 12.12. En este caso, como el hermano es rojo, el padre necesariamente
debe ser negro.
t
Figura 12.12 Descartar hoja negra con hermano rojo.
El último caso que debe analizarse es el de hijo, padre y hermano de colores negros. Si se
elimina la hoja y se cambia a color rojo el huérfano, se produce una disminución de la altura
negra del nodo padre, denominado x, en la Figura 12.13, lo cual hará perder al árbol sus
propiedades. Nótese que de x hacia abajo el árbol es coloreado.
x
t
Figura 12.13 Descartar hoja negra con padre y hermano negro.
La altura negra de x es bh(x)=0, si no se cuenta el nodo externo; y uno si se cuenta el nodo
externo.
Profesor Leopoldo Silva Bijit
26-05-2008
10
Estructuras de Datos y Algoritmos
Para corregir el balance de alturas negras debe efectuarse una revisión ascendente.
12.4.4. Balance de alturas negras en descarte. Caso doble negro.
Sea x un puntero al subárbol coloreado, que disminuyó su altura negra, y desde el cual debe
revisarse hacia arriba para mantener la propiedad de iguales alturas negras de los subárboles. La
raíz de este subárbol es negra.
Si x es la raíz debe detenerse la revisión.
a) Hermano rojo.
Si x tiene padre y el hermano h es rojo, el padre debe ser negro. La Figura 12.14, a la izquierda,
ilustra este caso, cuando x es descendiente izquierdo.
x
h
h
x
h
x
h
Figura 12.14 Hermano rojo, padre negro.
Si la altura negra de x es bh(x), las alturas negras de los subárboles descendientes del hermano
rojo son iguales a bh(x)+1. Esto se ilustra con dos descendientes negros en los subárboles de h.
Si el árbol era coloreado, antes del descarte, necesariamente x tiene padre, hermano y
descendientes.
Si se cambia el color del padre y del hermano se tiene el resultado que se muestra en la Figura
12.14, al centro. Luego rotando a la izquierda el par padre-hermano, se obtiene la situación
mostrada a la derecha de la Figura 12.14, en la cual se ha reposicionado h, apuntado al hermano
actual de x.
Tanto el actual abuelo como el padre de x, siguen desbalanceados. El objetivo de esta
transformación es lograr que x tenga un hermano negro. Que es el siguiente caso que se estudia.
b) Hermano negro.
Si el hermano es negro, el padre puede ser rojo o negro. Lo cual se representará por un signo de
interrogación al lado del nodo.
En esta situación se tienen tres casos que analizar: Una es si ambos hijos del hermano son
negros; la segunda es si el hijo derecho del hermano es negro y el izquierdo es rojo; y la tercera
es que el hijo derecho del hermano sea rojo, pudiendo ser rojo o negro el hijo izquierdo del
hermano.
b1) Sobrinos negros.
Si x y su hermano son negros, los subárboles descendientes de h, tienen altura negra igual a
bh(x)+1, lo cual se insinúa con un descendiente, en la Figura 12.15. Esto es así, ya que
originalmente se borró un descendiente negro de x, cuando el árbol era coloreado.
Profesor Leopoldo Silva Bijit
26-05-2008
Árboles coloreados
11
Si se cambia el color del hermano a rojo, y se mueve x, apuntando al padre, se tendrá que desde
el nuevo x hacia abajo el árbol es coloreado. Además se fuerza a negro el padre original de x,
para evitar un posible doble rojo.
?
x
x
h
h
x
Figura 12.15 Hermano negro y sobrinos negros.
Luego de esta transformación la altura negra del nuevo x, aumenta en uno; y se debe seguir
revisando en forma ascendente hacia la raíz. No es necesario continuar, si el nuevo x es la raíz.
b2) Sobrino derecho negro, sobrino izquierdo rojo.
Como x y su hermano son negros, el padre de x puede ser rojo o negro. Nuevamente los
descendientes de h, deben tener alturas negras: bh(x)+1.
?
h
x
h
x
?
h
h
?
h
x
h
h
Figura 12.16 Hermano y sobrino derecho negros.
Primero se cambian los colores del hermano negro y del sobrino rojo, esto se muestra en el
medio de la Figura 12.16. Luego se rota a la derecha el par hermano-sobrino derecho, lo cual se
muestra a la derecha en la Figura 12.16, en la cual se mueve h, para apuntar al nuevo hermano
de x. Esta transformación conduce al caso siguiente, en la que el sobrino derecho es rojo.
b3) Sobrino derecho rojo, sobrino izquierdo negro.
El padre de x, puede ser rojo o negro. Se procede a copiar el color del padre en el hermano, y
pintar de negro al padre y al sobrino rojo, resultado que se muestra al centro de la Figura 12.17.
x
?
h
h
x
?
h
?
h
h
x
Figura 12.17 Hermano negro, sobrino derecho rojo.
Profesor Leopoldo Silva Bijit
26-05-2008
h
12
Estructuras de Datos y Algoritmos
Luego se rota a la izquierda el par padre-hermano, resultando la ilustración a la derecha de la
Figura 12.17. En ésta se ha logrado reestablecer las alturas negras de todos los nodos desde h
hacia abajo. No es preciso continuar la revisión ascendente, y el árbol completo es coloreado.
Si h queda apuntando a la raíz, debe forzarse el color negro en ese nodo.
El caso en que ambos sobrinos son rojos, se trata de igual forma que el caso b3).
x
?
h
h
Figura 12.18 Hermano negro, sobrinos rojos.
Esto completa el análisis del descarte de un nodo.
12.5. Estructura de datos y funciones básicas.
12.5.1. Estructura de datos.
Si las operaciones de inserción y descarte se implementan en forma recursiva, la ruta de
búsqueda queda almacenada en el stack, es decir se disponen de las referencias al padre y al
abuelo. Después de un retorno de una función que tiene como argumento un nodo apuntado por
t; se tiene ahora en t, el puntero al padre del anterior. De esta forma es posible definir un nodo
con sólo dos punteros, el izquierdo y el derecho, además del color.
Sin embargo si las exigencias de espacio no son fundamentales la elección de una estructura que
adicionalmente mantenga un puntero al padre del nodo, presenta ventajas en la velocidad de
ejecución de las operaciones. Además las funciones resultan iterativas, y no se produce un gran
espacio del stack, para almacenar los argumentos de las funciones recursivas.
typedef struct nn {
/* RB-Tree */
int color;
/* Solo puede ser Rojo o Negro */
int clave;
/* clave entera */
struct nn *left, *right, *padre; /* tres punteros */
} nodo, *pnodo;
12.5.2. Crea un nodo para inserción.
Se inicia el nodo con color rojo.
#define
RED
0
#define
BLACK
1
Profesor Leopoldo Silva Bijit
26-05-2008
Árboles coloreados
13
pnodo CreaNodo(int valor)
{ pnodo t = (pnodo) malloc(sizeof(nodo));
if (t != NULL)
{ t->color=RED; t->clave=valor;
t->left=NULL; t->right=NULL; t->padre=NULL;
}
return t;
}
12.5.3. Sucesor.
El diseño del sucesor es simple si se dispone de un puntero al padre.
pnodo sucesor(pnodo x)
{ pnodo y;
if (x->right!=NULL)
{
/* Si hay subárbol derecho desciende por la izquierda en éste,
** hasta encontrar nodo sin descendiente izquierdo.
*/
for (y=x->right; y->left!=NULL; y=y->left);
}
else
{
/* Ascender hasta encontrar nodo que esté a la izquierda de su padre
** ( o la raíz) entonces retornar el padre.
*/
for(y=x->padre; y!=NULL && x==y->right; x=y, y=y->padre );
}
return(y);
}
12.5.4. Predecesor.
Basta cambiar left por right, y viceversa, en el código del sucesor.
pnodo predecesor(pnodo x)
{ pnodo y;
if (x->left!=NULL) for (y=x->left; y->right!=NULL; y=y->right);
else
{ y=x->padre;
while(y!=NULL && x==y->left){x=y; y=y->padre;}
}
return(y);
}
Profesor Leopoldo Silva Bijit
26-05-2008
14
Estructuras de Datos y Algoritmos
12.5.5. Rotación a la izquierda.
Se pasa la raíz del árbol por referencia. Esto en caso que el nodo Y, se convierta en la nueva
raíz.
/*
** Rotación izquierda con padre
**
**
X
lrot(X)
--->
Y
**
/ \
/ \
**
A
Y
<--rrot(Y)
X
C
**
/ \
/ \
**
B
C
A
B
** Se asume que x o y no son nulos
*/
void lrot(pnodo * raiz, pnodo x)
{ pnodo y;
//assert(x!=NULL);
//assert(x->right!=NULL);
y=x->right; /* y es el hijo derecho de x */
/* Pega subárbol izquierdo de y, como subárbol derecho de x.*/
x->right = y->left;
/* Si B no es nulo, el padre de B ahora es x */
if (y->left != NULL) y->left->padre = x;
/* Padre de y es el padre de x */
y->padre = x->padre;
if (x->padre == NULL) *raiz=y; /* Si x es la raíz, la deja apuntando a y */
/* Si x era descendiente izquierdo, pega y por la izquierda */
else if (x == x->padre->left) {x->padre->left=y;}
else {x->padre->right=y;} //sino por la derecha
y->left=x; /* Al nodo y le pega x */
x->padre = y; /* Le pega el padre a x */
}
Profesor Leopoldo Silva Bijit
26-05-2008
Árboles coloreados
15
12.5.6. Rotación a la izquierda.
Es el código especular del anterior.
/*
** Rotación derecha con padre
**
**
X
rrot(X)
**
/ \
**
Y
C
<--**
/ \
**
A
B
**
**
** Se asume que x o y no son nulos
*/
--->
lrot(Y)
Y
/ \
A
X
/ \
B
C
void rrot(pnodo * raiz, pnodo x)
{ pnodo y;
//assert(x!=NULL);
//assert(x->left!=NULL);
y=x->left; /* y es el hijo izquierdo de x */
/* Pega subárbol derecho de y, como subárbol izquierdo de x.*/
x->left = y->right;
/* Si B no es nulo, el padre de B ahora es x */
if (y->right != NULL) y->right->padre = x;
/* Padre de y es el padre de x */
y->padre = x->padre;
if (x->padre == NULL)
*raiz=y;/* Si x es la raíz, la deja apuntando a y */
/* Si x era descendiente derecho, pega y por la derecha */
else if (x == x->padre->right) {x->padre->right=y;} else {x->padre->left=y;}
y->right=x; /* Al nodo y le pega x */
x->padre = y; /* Le pega el padre a x */
}
12.5.7. Comenta errores en inserción y descarte.
void Error(int tipo, int clave)
{
if (tipo==1)
printf("Error en inserción. No se pudo crear Nodo\n");
else if (tipo==2)
Profesor Leopoldo Silva Bijit
26-05-2008
16
Estructuras de Datos y Algoritmos
printf("Error en inserción. Clave duplicada=%d!\n", clave);
else if (tipo==3)
printf("Error en descarte. Clave no encontrada!\n");
else printf("Error en tipo=%d!\n", tipo);
}
12.5.8. Calcula altura negra.
//revisa que se cumpla largos de negros de subárboles iguales, de cada nodo.
//Retorna -1 si hay error; sino entrega la altura negra, la función black height, bh(x).
int bh(pnodo x)
{
int nleft, nright;
if (x==NULL) return(1); //cuenta el descendiente de hoja como negro.
nleft=bh(x->left);
nright=bh(x->right);
//si hay error al retornar de los llamados recursivos
if (nleft==-1 || nright==-1) return(-1); //propaga el error
if (nleft != nright)
{
printf("Negros del izquierdo=%d difieren de los del derecho=%d, clave=%d\n",
nleft, nright, x->clave);
return(-1);
}
if (x->color == BLACK)
{
nleft++; //acumula los negros en nleft
}
return(nleft);
}
12.5.9. Revisa propiedades de árbol coloreado.
int RevisaPropiedades(pnodo x)
{ int bhl=1,bhr=1;
if (x==NULL) {printf("Árbol vacío\n"); return (1);}
if (x->left==NULL && x->right==NULL)
{
if(x->color!=BLACK) printf("Raíz no es negra\n"); return(1);
}
if (x->left!=NULL && x->right==NULL)
if(x->color!=BLACK && x->left->color!=RED)
{
printf("Nodo con solo hijo izquierdo no es negro ni tiene hijo rojo\n"); return(1);
Profesor Leopoldo Silva Bijit
26-05-2008
Árboles coloreados
17
}
if (x->right!=NULL && x->left==NULL)
if(x->color!=BLACK && x->right->color!=RED)
{
printf("Nodo con solo hijo derecho no es negro ni tiene hijo rojo\n"); return(1);
}
if (x->color==RED)
{ //revisar
if (x->left->color!=BLACK && x->right->color!=BLACK)
{
printf("Rojo con dos hijos que no son negros, x=%d\n", x->clave); return(1);
}
}
if (x->left != NULL)
{
if (x->left->padre != x)
{
printf("Hijo izquierdo de x no apunta al padre, x=%d", x->clave);
return(1);
}
bhl=bh(x->left);
if (bhl==-1)
{ printf("Subárbol izquierdo no es coloreado\n");
return(1);
}
}
if (x->right != NULL)
{
if (x->right->padre != x)
{
printf("Hijo derecho de x no apunta al padre, x=%d", x->clave);
return(1);
}
bhr=bh(x->right);
if (bhr==-1)
{ printf("Subárbol derecho no es coloreado\n");
return(1);
}
}
if(bhl!=bhr)
{
printf("Arbol no es coloreado. l=%d r=%d\n",bhl,bhr);
return(1);
}
return(0); //si cumple propiedades.
}
Profesor Leopoldo Silva Bijit
26-05-2008
18
Estructuras de Datos y Algoritmos
12.6. Inserción.
La codificación resulta sencilla si se ha efectuado previamente el análisis detallado de los
diferentes casos, desarrollado en 12.3.
Se pasa por referencia el árbol.
pnodo insertar(pnodo *tree, pnodo nuevo)
{
pnodo y=NULL;
pnodo x=*tree;
if (nuevo==NULL) {Error(1,0); return (NULL);}
//Busca posición para insertar.
while(x!=NULL)
{ y = x;
if (nuevo->clave < x->clave) x=x->left;
else if (nuevo->clave > x->clave) x=x->right;
else {Error(2, nuevo->clave); return(NULL);}
}
//y apunta al padre del lugar de inserción.
//malloc no pudo crear nodo
//clave duplicada
nuevo->padre=y;
if (y == NULL) {*tree=nuevo; nuevo->color=BLACK; return(nuevo);}
else if (nuevo->clave < y->clave) y->left=nuevo;
else y->right=nuevo;
/*Código adicional para preservar las propiedades de árbol coloreado*/
x=nuevo;
while ( (x->padre!=NULL) && ( x->padre->color==RED) ) //doble rojo
{ if ( x->padre==x->padre->padre->left) //como la raíz es negra, existe el abuelo de x
//si x es descendiente izquierdo del abuelo.
{ y=x->padre->padre->right; // y apunta al tío
if ((y!=NULL)&&(y->color==RED)) // solo recoloración.
{ x->padre->color=BLACK;
y->color=BLACK; //pinta NEGRO al tío y al padre
x->padre->padre->color=RED; //el abuelo que era negro, cambia de color
x=x->padre->padre; //debe seguir revisando ascendentemente
}
else //Debe reestructurarse mediante rotaciones. Si y es nulo o y apunta a negro.
{
if (x==x->padre->right) { x= x->padre; lrot(tree,x);}
x->padre->color=BLACK;
x->padre->padre->color=RED;
rrot(tree, x->padre->padre);
}
Profesor Leopoldo Silva Bijit
26-05-2008
Árboles coloreados
19
}
else //Código especular. Si x es descendiente derecho del abuelo.
{ y=x->padre->padre->left; // y apunta al tío
if ((y!=NULL)&& (y->color==RED)) // solo recoloración.
{ x->padre->color=BLACK;
y->color=BLACK; //pinta al tío
x->padre->padre->color=RED; //el abuelo que era negro, cambia de color
x=x->padre->padre; //debe seguir revisando
}
else //Debe reestructurarse mediante rotaciones
{
if (x==x->padre->left) { x= x->padre; rrot(tree,x);}
x->padre->color=BLACK;
x->padre->padre->color=RED;
lrot(tree, x->padre->padre);
}
}
}
(*tree)->color=BLACK; //pinta la raíz negra
return (nuevo);
}
12.7. Descarte.
Para marcar con x la raíz de un subárbol, que disminuyó su altura negra, se emplea un nodo
externo, de color negro, para almacenar un puntero al padre de éste, cuando el nodo que debe
ser descartado es negro y es una hoja. Se pasa como argumento, a la función que restaura las
propiedades de un árbol coloreado, en caso de descartar un nodo negro, si el nodo x es un
centinela (nodo externo); de esta forma antes de modificar el puntero x, se podrá escribir el
valor nulo en el padre de x.
/* Descarta nodo z, liberando el espacio*/
//z no debe ser NULL
void descarta(pnodo *rootp, pnodo z)
{
nodo externo; int centinela=0;
pnodo x, y;
if(z==NULL) Error(3,0);
if (z->left == NULL || z->right == NULL) y=z; //un hijo u hoja
else y=sucesor(z);
//Si hay hijo rojo, lo pega; si es hoja: y->right es nulo, y también x.
if (y->left != NULL) x=y->left; else x=y->right;
if(y->color==BLACK)
{ //y es negro.
if (x==NULL) {centinela=1; x=&externo; x->color=BLACK;}
Profesor Leopoldo Silva Bijit
26-05-2008
20
Estructuras de Datos y Algoritmos
//y es hoja; x es nodo externo.
x->padre = y->padre; //si y tiene hijo rojo, o si y es hoja
}
if (y->padre == NULL)
{ if(centinela) *rootp=NULL; else *rootp=x;}
else if (y==y->padre->left) y->padre->left = x;
else y->padre->right = x;
if (y!=z) { z->clave =y->clave; }
if (y->color == BLACK) delete_fix(rootp, x, centinela);
free(y);
}
/* Reestablece propiedades árbol coloreado luego de un descarte */
void delete_fix(pnodo *rootp, pnodo x, int esexterno)
{
pnodo w;
while (x!=*rootp && x->color==BLACK)
{
if (x==x->padre->left) //x es descendiente izquierdo
{
w=x->padre->right; //w es el hermano
if (w->color==RED)
{
w->color=BLACK;
x->padre->color=RED;
lrot(rootp, x->padre);
w=x->padre->right;
}
//ahora el hermano es negro.
if ( (w->left==NULL || w->left->color==BLACK)
//nodo externo o interno
&& (w->right==NULL || w->right->color==BLACK) )
{
w->color=RED;//ambos sobrinos negros
if(esexterno)
{x->padre->left=NULL; esexterno=0;}
x=x->padre; //cambia x. Asciende un nivel y sigue balanceando.
}
else
{
//uno o ambos sobrinos son rojos
if (w->right==NULL || w->right->color == BLACK)
//externo o interno
Profesor Leopoldo Silva Bijit
26-05-2008
Árboles coloreados
21
{
//sobrino derecho negro
w->left->color=BLACK;
w->color=RED;
rrot(rootp, w);
w=x->padre->right;
}
//ahora el sobrino derecho es rojo
w->color=x->padre->color;
x->padre->color = BLACK;
w->right->color = BLACK;
lrot(rootp, x->padre);
if(esexterno)
{x->padre->left=NULL; esexterno=0;}
x=*rootp; //lleva x a la raiz, se sale del lazo
}
}
else //código especular del if
{
//x es descendiente derecho.
w=x->padre->left;
if (w->color==RED)
{
w->color=BLACK;
x->padre->color=RED;
rrot(rootp, x->padre);
w=x->padre->left;
}
if ( (w->right==NULL || w->right->color==BLACK)
&& (w->left==NULL || w->left->color==BLACK))
{
w->color=RED;
if(esexterno)
{x->padre->right=NULL; esexterno=0;}
x=x->padre;
}
else
{
if (w->left==NULL || w->left->color == BLACK)
{
w->right->color=BLACK;
w->color=RED;
lrot(rootp, w);
w=x->padre->left;
}
w->color=x->padre->color;
x->padre->color = BLACK;
Profesor Leopoldo Silva Bijit
26-05-2008
22
Estructuras de Datos y Algoritmos
w->left->color = BLACK;
rrot(rootp, x->padre);
if(esexterno)
{x->padre->right=NULL; esexterno=0;}
x=*rootp;
}
}
}
//Al salir del while: x es la raíz o es rojo. Si es la raíz la pinta negra.
x->color=BLACK; //corrige caso con un solo hijo rojo
}
12.8. Test de las operaciones.
La inserción ascendente, genera el árbol coloreado, que se muestra en la Figura 12.2.
#define N 14
pnodo arbol=NULL;
int main(void)
{ int i;
printf("Insertando ascendente\n");
for(i=1;i<=N;i++)
{insertar(&arbol, CreaNodo(i));
printf("%d->", i);
//prtinorder(arbol,0); putchar('\n');
RevisaPropiedades(arbol);}
printf("\nDescartando\n");
for(i=1;i<=N;i++)
{descarta(&arbol, buscar(&arbol,i ));
printf("%d",i);
RevisaPropiedades(arbol);
}
printf("Insertando descendente\n");
for(i=N;i>0;i--)
{insertar(&arbol, CreaNodo(i));
printf("%d->",i);
//prtinorder(arbol,0); putchar('\n');
RevisaPropiedades(arbol);
}
printf("\nDescartando\n");
for(i=N;i>0;i--)
{descarta(&arbol, buscar(&arbol,i ));
Profesor Leopoldo Silva Bijit
26-05-2008
Árboles coloreados
23
printf("%d",i);
RevisaPropiedades(arbol);
}
return(0);
}
Profesor Leopoldo Silva Bijit
26-05-2008
24
Estructuras de Datos y Algoritmos
Referencias.
R. Bayer. “Symmetric binary B-trees: Data structure and maintenance algorithms.”
Acta Informatica 1:290-306, 1972.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. “Introduction
to Algorithms”, Second Edition. MIT Press and McGraw-Hill, 2001.
Profesor Leopoldo Silva Bijit
26-05-2008
Árboles coloreados
25
Índice general.
CAPÍTULO 12. .......................................................................................................................................... 1
ÁRBOLES COLOREADOS. RED BLACK. ........................................................................................... 1
12.1. PROPIEDADES DE LOS ÁRBOLES COLOREADOS. ................................................................................ 1
12.2. COMPLEJIDAD EN ÁRBOLES COLOREADOS. ...................................................................................... 3
12.3. ANÁLISIS DE INSERCIÓN. ................................................................................................................. 4
12.3.1. Recoloración. Cuando el tío es rojo. ....................................................................................... 5
12.3.2. Rotaciones. Cuando el tío es negro. ........................................................................................ 6
12.4. ANÁLISIS DE LA OPERACIÓN DESCARTAR......................................................................................... 7
12.4.1. Dos descendientes. .................................................................................................................. 7
12.4.2. Un descendiente. ..................................................................................................................... 8
12.4.3. El nodo a descartar es una hoja. Sin descendientes. ............................................................... 9
12.4.4. Balance de alturas negras en descarte. Caso doble negro. ................................................... 10
a) Hermano rojo. ............................................................................................................................................ 10
b) Hermano negro. ......................................................................................................................................... 10
b1) Sobrinos negros. ................................................................................................................................. 10
b2) Sobrino derecho negro, sobrino izquierdo rojo. .................................................................................. 11
b3) Sobrino derecho rojo, sobrino izquierdo negro. .................................................................................. 11
12.5. ESTRUCTURA DE DATOS Y FUNCIONES BÁSICAS. ............................................................................ 12
12.5.1. Estructura de datos. ............................................................................................................. 12
12.5.2. Crea un nodo para inserción. ................................................................................................ 12
12.5.3. Sucesor. ................................................................................................................................. 13
12.5.4. Predecesor. ............................................................................................................................ 13
12.5.5. Rotación a la izquierda. ........................................................................................................ 14
12.5.6. Rotación a la izquierda. ........................................................................................................ 15
12.5.7. Comenta errores en inserción y descarte. ............................................................................. 15
12.5.8. Calcula altura negra. ............................................................................................................ 16
12.5.9. Revisa propiedades de árbol coloreado. ............................................................................... 16
12.6. INSERCIÓN. .................................................................................................................................... 18
12.7. DESCARTE. .................................................................................................................................... 19
12.8. TEST DE LAS OPERACIONES. ........................................................................................................... 22
REFERENCIAS. ........................................................................................................................................ 24
ÍNDICE GENERAL. ................................................................................................................................... 25
ÍNDICE DE FIGURAS................................................................................................................................. 26
Profesor Leopoldo Silva Bijit
26-05-2008
26
Estructuras de Datos y Algoritmos
Índice de figuras.
FIGURA 12.1 ÁRBOL DE BÚSQUEDA BINARIA COLOREADO. ...........................................................................1
FIGURA 12.1A ÁRBOL COLOREADO CON ROJOS HORIZONTALES. ...................................................................2
FIGURA 12.2 TRAYECTOS EN PEOR CASO. .....................................................................................................2
FIGURA 12.2A. COMPARACIÓN DE COMPLEJIDADES. RED-BLACK, AVL, BALANCEADO. .............................4
FIGURA 12.3 DOBLES ROJOS EN INSERCIÓN. .................................................................................................5
FIGURA 12.4 RECOLORACIÓN EN INSERCIÓN. TÍO ROJO. ...............................................................................6
FIGURA 12.5 RECOLORACIÓN CON TÍO NEGRO, NO QUEDAN DOS ROJOS ADYACENTES..................................6
FIGURA 12.6 ROTACIÓN DERECHA, PRESERVA ALTURA NEGRAS...................................................................6
FIGURA 12.7. ROTACIÓN IZQUIERDA, PAR PADRE-X. .....................................................................................7
FIGURA 12.8. NODO SELECCIONADO PARA SER DESCARTADO ES HOJA ROJA. ...............................................8
FIGURA 12.9. NODO SELECCIONADO PARA SER DESCARTADO ES NODO NEGRO CON HIJO ROJO. ....................8
FIGURA 12.10 DESCARTAR NODO NEGRO CON UN HIJO ROJO. .......................................................................8
FIGURA 12.10A DESCARTAR NODO NEGRO CON UN HIJO ROJO. .....................................................................8
FIGURA 12.11 DESCARTAR HOJA. .................................................................................................................9
FIGURA 12.12 DESCARTAR HOJA NEGRA CON HERMANO ROJO. ....................................................................9
FIGURA 12.13 DESCARTAR HOJA NEGRA CON PADRE Y HERMANO NEGRO. ...................................................9
FIGURA 12.14 HERMANO ROJO, PADRE NEGRO. ..........................................................................................10
FIGURA 12.15 HERMANO NEGRO Y SOBRINOS NEGROS. ..............................................................................11
FIGURA 12.16 HERMANO Y SOBRINO DERECHO NEGROS. ............................................................................11
FIGURA 12.17 HERMANO NEGRO, SOBRINO DERECHO ROJO. .......................................................................11
FIGURA 12.18 HERMANO NEGRO, SOBRINOS ROJOS. ...................................................................................12
Profesor Leopoldo Silva Bijit
26-05-2008