UNIVERSIDAD NACIONAL DE INGENIERIA

ESTRUCTURAS DE DATOS

TEMA:

IMPLEMENTACION Y APLICACION DEARBOLES ROJO Y NEGRO

Alumno: Lara Gutierrez, LuisAntony Miranda Gil

Ariano CorderoLouiso Acllus

Profesor: Rosulo Perez

ARBOLES ROJO-NEGRO

Abstract:

El arbol rojo-negro es una estructura de dato abstracto el cual es un tipo dearbol binario de busqueda que se se encuentra equilibrado, con la peculiaridadque cada nodo posee un atributo de color, siendo estos rojo o negro. Una mejordefinicion como implementacion es la base de este trabajo.

1. Introduccion

En la actualidad existen diferentes tipos de estructuras de datos, que se pue-den utilizar segun lo que nesecitamos. Una de estas estructuras son los arboleslos cuales sirven para el ordenamiento de informacion. Los arboles son utiles ala hora de tener que acomodar datos de una manera jerarquica donde alguno deestos datos tienen mayor importancia que otros. Estos cuentan con un conjuntode nodos conectados, donde estos pueden tener mas nodos(hijos) conectados.El nodo que se encuentra de primero en el arbol se le conoce como raız. Losarboles son comunes para realizar busquedas en un conjunto de datos, ya quesu estructura es muy practicada para realizar estos algoritmos. En este artıculose podra encontrar diferentes secciones en las cuales se desarrollara el tema dearboles rojo-negro, el cual es un tipo de arbol que cuenta con las caracterısticasantes mencionadas y otras mas, propias de el que lo hacen diferente y particular.

2. Fundamento Teorico

El arbol rojo-negro es una estructura de dato abstracto el cual es un tipode arbol binario de busqueda que se se encuentra equilibrado. Suele ser utili-zado para organizar datos y es frecuentemente usados por las personas paraguardar numeros. En estos arboles las hojas no son importantes y no contieneninformacion, solo valores. En el es posible moverse de una forma ordenada yeficiente a traves de los datos, por supuesto, si existe alguna manera de localizarel padre de uno de los nodos. El tiempo que se dura en desplazarse desde laraız hasta una de las hojas del arbol, el cual, debe de estar equilibrado y tenerla mınima altura posible, serıa de O(log n) donde n es la cantidad de nodos

1

del arbol. El nombre de arbol rojo-negro se debe a los colores de sus nodos,ya que estos son de color negro o rojo. Existen una serie de propiedades queseguir a la hora de de ponerle color a cada uno de los nodos. Entre ellas estan:la raız del arbol siempre es de color negro, todas las hojas de valor NULL vande color negro (llamadas tambien nodos externos), el nodo de color rojo (llama-do tambien nodo interno) debe tener obligatoriamente dos hijos de color negro,cada camino desde cualquier nodo a sus hojas va a contener la misma canti-dad de nodos negros, y por ultimo, ningun nodo de color rojo puede tener unpadre de color rojo. Las ventajas de que este arbol sea de estos colores es quenos facilita a la hora de tener que buscar el camino mas corto para llegar dede un nodo a otro. El camino mas corto va a ser aquel que cuenta con todossus nodos de color negro, y el mas largo sera el que alterna sus nodos entrerojo y negro. Ademas, este arbol va a tener una caracterıstica muy especial yes que ningun camino va a tener mayor longitud que la del doble de otro camino.

3. Operaciones

Insercion de un nodo

La insercion de un nodo se realiza inicialmente igual que en un arbol binariode busqueda. Al nuevo nodo se le da el color rojo. De esta manera no se viola lasegunda condicion (altura negra), aunque se puede violar la primera (el padredel nodo insertado puede ser rojo). Caso Trivial: Si el padre del nodo insertadoes negro, no se realiza ningun ajuste (el arbol es correcto). En caso contrariose entra en un bucle donde x representa el nodo que se esta comprobando. xes un nodo rojo, y los casos se refieren a situaciones en que su padre existe yes tambien rojo: Cuando el padre no exista, simplemente se cambia el color dex (que es la raız) a negro y se termina el bucle, y si el padre existe y es negrose termina directamente el bucle. Dependiendo del caso, se realizaran una seriede operaciones y o bien continuara el bucle (x pasa a ser otro nodo) o bien seterminara. En cada caso se supone que el nodo que se comprueba (x) es rojo,su padre (y) existe y es rojo, y su abuelo (z) existe (no puede ser raız un nodorojo). El nodo hermano del padre se denomina tıo (t).Caso 1: Tıo rojo, nodo x izquierdo o derecho.

2

Caso 2: Tio negro, nodo x es hijo derecho.

Caso 3: Tıo negro, nodo x es hijo izquierdo.

Borrado de un nodo

La operacion se lleva a cabo de la misma manera que en los arboles binariosde busqueda:

1. Se busca el nodo a borrar (como los nodos hojas son nodos nulos, en casode existir el nodo a borrar debe tener siempre dos hijos).

2. Si es un nodo con dos hijos no nulos, se busca el mayor nodo (el mas ala derecha) de su subarbol izquierdo (lo llamamos x), se intercambia susdatos con el nodo a borrar y se pasa a borrar el nodo x. Como es el nodomas a la derecha, su hijo derecho sera nulo.

p es el nodo que se borra, x es el hijo no nulo o uno cualquiera de los hijos siambos son nulos, z es el padre del nodo borrado e y es el nodo hermano del nodoborrado. Para ajustar el arbol tras el borrado es necesario conocer los nodos x yz. El nodo x puede ser nulo (al igual que y), pero el nodo z debe existir (es decir,el caso en que se tenga que borrar el nodo raız se trata como un caso especial ?simplemente se elimina la raız y si el nuevo nodo raız es de color rojo se cambiasu color a negro). La operacion de ajuste (reestructuracion) consistira en una

3

comprobacion de los casos triviales (ver a continuacion). Si no se esta en un casotrivial se entra en un bucle, en cada iteracion x y z apuntan a nodos del arbolcon la siguiente estructura:

Los nodos z e y no son nulos y el nodo x puede serlo. Se comprueba en cualde los cinco casos no triviales estamos, se efectua la operacion adecuada y sedecide si se continua a la siguiente iteracion.

4. Aplicacion

Los arboles rojo-negro son utilizados en el kernel de Linux. El proceso de uti-lizar un arbol rojo-negro comienza al incluir ?linux / rbtree.h?. Esta es una de lasestructuras de datos del nucleo mas difıciles de utilizar, sin embargo, en el disenode una estructura de datos general para un lenguaje como C, el desarrolladorsiempre debe decidir como incluir tipos arbitrarios dentro de la estructura, y laforma de hacer comparaciones entre ellos. La persona que implemento los arbo-les rojo-negro Linux fue Andrea Arcangeli.1 Los arboles rojo-negro ofrecen unpeor caso como una estructura en tiempo real. De hecho, es muy difıcil predecirsi la base de la operacion de actualizacion se hara en equilibrio o cuanto sera sucosto, aunque a´un es posible calcular un costo de rendimiento cuando el arbolse encuentra en el peor estado de equilibrio. Los arboles rojo-negro son particu-larmente valiosos en programacion funcional, donde son una de las estructurasde datos persistentes mas comunmente utilizadas en la construccion de arreglosasociativos y conjuntos que pueden retener versiones previas tras mutaciones.La version persistente del arbol rojo-negro requiere un espacio O(log n) paracada insercion o borrado, ademas del tiempo.

4