arboles red-black

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 unAVL.
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 sucolor. 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. Laestructura 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 nodospueden 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 formadasó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
queno 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 decualquier 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...