Estrutura De Datos

ÁRBOL ROJO-NEGRO

Un árbol rojo-negro es un tipo abstracto de datos. Concretamente, es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la computación. La estructura original fue creada por Rudolf Bayer en 1972, que le dio el nombre de “árboles-B binarios simétricos”, pero tomó su nombre moderno en un trabajo de Leo J. Guibas y Robert Sedgewick realizado en 1978. Es complejo, pero tiene un buen peor caso de tiempo de ejecución para sus operaciones y es eficiente en la práctica. Puede buscar, insertar y borrar en un tiempo O(log n), donde n es el número de elementos del árbol.

Sería ideal exponer la especificación algebraica completa de este tipo abstracto de datos (TAD) escrita en algún lenguaje de especificación de TADs, como podría ser Maude; sin embargo, la complejidad de la estructura hace que la especificación sea bastante ilegible, y no aporta valor considerable al lector. Por tanto, su especificación es expuesta a continuación en lenguaje humano, esquemas e implementaciones en el lenguaje de programación C.

Terminología

Un árbol rojo-negro es un tipo especial de árbol binario usado en informática para organizar información compuesta por datos comparables (por ejemplo, números). En los árboles rojo-negro las hojas no son relevantes y no contienen datos.

En los árboles rojo-negro, como en todos los árboles binarios de búsqueda, es posible moverse ordenadamente a través de los elementos de forma eficiente si hay forma de localizar el padre de cualquier nodo. El tiempo de desplazarse desde la raíz hasta una hoja a través de un árbol equilibrado que tiene la mínima altura posible es de O(log n).

Al implementar esta estructura es posible utilizar un único nodo centinela. Este cumple la función de hoja para todas las ramas del árbol. Así, todos los nodos internos que finalicen en una hoja tienen referencia a este único nodo centinela. Esto no es necesario, ya que puede hacerse una referencia nula (NIL) en el final de cada rama.

Propiedades

Un árbol rojo-negro es un árbol binario de búsqueda en el que cada nodo tiene un atributo de color cuyo valor es rojo o negro. En adelante, se dice que un nodo es rojo o negro haciendo referencia a dicho atributo.

Además de los requisitos impuestos a los árboles binarios de búsqueda convencionales, se deben satisfacer las siguientes reglas para tener un árbol rojo-negro válido:

1. Todo nodo es o bien rojo o bien negro.

2. La raíz es negra.

3. Todas las hojas (NULL) son negras.

4. Todo nodo rojo debe tener dos nodos hijos negros.

5. Cada camino desde un nodo dado a sus hojas descendientes contiene el mismo número de nodos negros.

Estas reglas producen una características producen una regla crucial para los árboles rojo-negro: el camino más largo desde la raíz hasta una hoja no es más largo que dos veces el camino más corto desde la raíz a una hoja. El resultado es que dicho árbol está aproximadamente equilibrado.

Dado que las operaciones básicas como insertar, borrar y encontrar valores tienen un peor tiempo de ejecución proporcional a la altura del árbol, esta cota superior de la altura permite a los árboles rojo-negro ser eficientes en el peor caso, a diferencia de los árboles binarios de búsqueda.

Para comprobarlo basta ver que ningún camino puede tener dos nodos rojos seguidos debido a la propiedad 4. El camino más corto posible tiene todos sus nodos negros, y el más largo alterna entre nodos rojos y negros. Dado que todos los caminos máximos tienen el mismo número de nodos negros por la propiedad 5, no hay ningún camino que pueda tener longitud mayor que el doble de la longitud de otro camino.

En muchas presentaciones de estructuras arbóreas de datos, es posible para un nodo tener solo un hijo y las hojas

...