Trabajo

ARBOL ROJO NEGRO
1) CONCEPTOS:
A) Definición:
Un árbol rojo negro es un tipo abstracto de datos, concretamente es un árbol binario de búsqueda equilibrado.
Un árbol binario de búsqueda auto- balanceable o equilibrado es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento.
Podemos recordarque: Los árboles AVL están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n). esto permite que al insertar o eliminar algúnnodo, el árbol siga siendo balanceado o equilibrado.
Un árbol rojo-negro es un árbol binario de búsqueda en el que cada nodo almacena un bit adicional de información llamado color, el cual puede ser rojo o negro. Sobre este atributo de color se aplican restricciones que resultan en un árbol en el que ningún camino de la raíz a una hoja es más de dos veces más largo que cualquier otro, lo cualsignifica que el árbol es balanceado.
Cada nodo de un árbol rojo negro contiene la siguiente información: color, dato, hijo izquierdo, hijo derecho y padre. Si un hijo o el padre de un nodo no existe, el apuntador correspondiente contiene el valor NULO, el cual consideraremos como un nodo cuyo color es negro. En lo sucesivo nos referiremos a los nodos distintos a las hojas (NULO) como nodos internosdel árbol y a las hojas y al padre de la raíz como nodos externos.

De su creación podemos decir:
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.

B) Terminología:
El árbol rojo negro es un tipo especial de árbol binario,utilizado en informática para organizar información compuesta por datos comparables, como son los números.

C) Características y propiedades:
* Todo nodo es o bien rojo o bien negro.
* La raíz es de color negra
* Un nodo rojo puede tener solo hijos negros.
* Todas las hojas son negras (las hojas son los hijos nulos).
* Cada camino simple desde un nodo a un nodo hijo descendientecontiene el mismo número de nodos negros, ya sea contando siempre los nodos negros nulos o bien no contándolos nunca. También es llamada “propiedad del camino” y por tanto el camino no puede tener dos rojos seguidos.
* El camino largo desde la raíz hasta una hoja no es más largo que 2 veces el camino más corto desde la raíz del árbol hasta una hija en dicho árbol. El resultado es que dichoárbol esta aproximadamente equilibrado.

En muchas presentaciones de estructuras arbóreas de datos, es posible para un nodo tener solo un hijo y las hojas contienen información. Es posible presentar los árboles rojo-negros en este paradigma, pero cambian algunas de las propiedades y se complican los algoritmos. Se utiliza el término “hojas nulas”, porque no contienen información y simplementesirven para indicar dónde el árbol acaba, como se mostró antes. Habitualmente estos nodos son omitidos en las representaciones, lo cual no lo hace ver como realmente se describe teóricamente. Como consecuencia de esto todos los nodos internos tienen dos hijos, aunque uno o ambos nodos podrían ser una hoja nula.
Otra explicación que se da del árbol rojo-negro es la de tratarlo como un árbol binario debúsqueda cuyas aristas, en lugar de nodos, son coloreadas de color rojo o negro.

2) IMPORTANCIA DEL USO DE ÁRBOLES ROJO NEGROS:

* Los árboles rojo-negros ofrecen un peor caso con tiempo garantizado para la inserción, el borrado y la búsqueda. No es esto únicamente lo que los hace valiosos en aplicaciones sensibles al tiempo como las aplicaciones en tiempo real, sino que además son...