Arboles rojo - negros

Universidad Blas Pascal
Algoritmos y Estructuras de Datos I

Trabajo Práctico 3

Tema: ÁRBOLES ROJO NEGROS

Alumno: FOCO, Denis.

Profesor: FRITELLI, Valerio.

Informe: Árboles Rojo - Negro

Abstract: Definiciones y conceptos. Propiedades. Algoritmos de inserción, búsqueda y borrado. Ventajas. Bibliografía.

• Definiciones y Conceptos.

Los árboles rojo negros, sonestructuras de datos abstractas basadas en árboles binarios de búsqueda balanceados, donde estos pueden organizar información compuesta por datos comparables (por Ej: números o claves, etc). Originalmente fueron creados por Rudolf Bayer en 1972, que le dio en nombre de “Árboles-B” binarios simétricos, pero tomaron su nombre moderno recién en 1978 en un trabajo realizado por: Leo J. Guibas y RobertSedgewick.
Tienen características propias, que los diferencian de otras estructuras de datos conocidas. En este tipo de árboles, las hojas no son muy importantes, ya que ellas no guardan información, solamente contienen un NULL y para ahorrar memoria, existe el nodo SENTINELA (NILL), el cual hace de hoja para todas las ramas del árbol.

• Propiedades

Cada nodo de un árbol rojo negro, agregaa su estructura de datos, un atributo adicional, llamado color. Por lo cual cada nodo, además de los ya conocidos atributos que posee, puede ser ROJO o NEGRO. Además de los requisitos impuestos a los árboles binarios de búsqueda convencionales, se deben satisfacer los siguientes para tener un árbol rojo-negro válido:

1. Todo nodo es rojo o negro.
2. La raíz es negra.
3. Toda hoja(NULL) es negra.
4. Propiedad del rojo: si un nodo es rojo, entonces sus dos hijos son negros.
5. Propiedad del camino: para cada nodo, todas las rutas de un nodo a las hojas, contienen el mismo número de nodos negros.  Al número de nodos negros de cada camino, que es constante para todos los caminos, se le denomina “Altura negra del árbol”, y por tanto el camino no puede tener dos rojosseguidos.
6. El camino más 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 a una hoja en dicho árbol. El resultado es que dicho árbol está aproximadamente equilibrado.

Ejemplo: Estructura de un árbol rojo negro.

Class ArbolRojoNegro
{
static class Nodo
{
Comparable clave;
Nodo izq;
Nodo der;Nodo padre;
Boolean color; // atributo adicional
}
private static final boolean NEGRO = false;
private static final boolean ROJO = true;
private static final Nodo NULO;
static
{
NULO = new Node();
NULO.clave = null;
NULO.padre = NULO;
NULO.izq = NULO;
NULO.der = NULO;
NULO.color = NEGRO;
}
}

• Operaciones

Las operaciones deinserción y eliminación de un árbol binario de búsqueda, si se aplican a un árbol rojo negro pueden modificar las propiedades enumeradas anteriormente.
Para restaurar estas propiedades es necesario cambiar el color de algunos nodos así como también la estructura de los punteros.
La estructura de los punteros se cambia mediante rotación, la cual es una operación que preserva las propiedades deun árbol binario de búsqueda. Existen dos tipos de rotaciones: a la izquierda y a la derecha.

[pic]

Otro tipo común de operaciones que podemos encontrar en los árboles rojo negro, al igual que en los de búsqueda binaria, es la búsqueda. Este tipo de operación consiste en posicionarnos en la raíz (si es que no es nula), y a partir de allí, si la clave/numero/objeto que estamos buscando esmenor a esta, movernos hacia la izquierda, y explorar el subárbol izquierdo, hasta llegar a nodo que posee el dato que buscamos, en caso de encontrarlo, retornamos el valor, en caso contrario descenderemos hasta una rama en donde su nodo será una hoja (null), por lo tanto no habremos encontrado el dato a buscar, por lo que la rutina devolverá un NULL. En caso de que la clave/numero/objeto fuera...