Implementacion de la clase Arbol_Rojinegro: Referencia del Archivo Arbol

Ir al código fuente de este archivo.


Clases
class	Arbol_Rojinegro< T >
	Clase Arbol_RojiNegro: -Un árbol rojo-negro resulta de la representación de un árbol 2-3-4 mediante un árbol binario. Más...
Definiciones
#define	Rojinegro_h
	Evita inclusión múltiple de `"Arbol_Rojinegro.h"`.
Funciones
template<class T>
void	rotarIzq (Arbol_Rojinegro< T > &x, Arbol_Rojinegro< T > &raiz)
	Rotaciones de la clase Arbol_Rojinegro: -Las operaciones de inserción y eliminación de un árbol binario de búsqueda, si se aplican a un árbol rojinegro pueden modificar ls propiedades basicas que debe cumplir la clase Arbol_Rojinegro.
template<class T>
void	rotarDer (Arbol_Rojinegro< T > &y, Arbol_Rojinegro< T > &raiz)
	Rotaciones de la clase Arbol_Rojinegro: -Las operaciones de inserción y eliminación de un árbol binario de búsqueda, si se aplican a un árbol rojinegro pueden modificar ls propiedades basicas que debe cumplir la clase Arbol_Rojinegro.
template<class T>
void	insercion (Arbol_Rojinegro< T > &root, const T &val)
	Inserción de un elemento en un arbol rojinegro: -La inserción de un nodo en un árbol rojo-negro con n elementos puede realizarse en un tiempo O(lg n).
template<class T>
void	corregirInsercion (Arbol_Rojinegro< T > &z, Arbol_Rojinegro< T > &raiz)
	Para estudiar cómo funciona la funcion "corregirInsercion" que permite restaurar las propiedades de árbol rojo-negro examinaremos el código en tres partes: -inicialización.
template<class T>
Bin_Tree< T >	busca_nodo (Bin_Tree< T > &root, const T &val)
	Funcion para buscar un nodo en el arbol.
template<class T>
void	borrado (Arbol_Rojinegro< T > &root, const T &val)
	Eliminación de un elemento en el arbol rojinegro: La elminación de un nodo en un árbol rojo-negro con n elementos puede realizarse en un tiempo O(lg n).
template<class T>
void	corregirEliminar (Arbol_Rojinegro< T > &x, Arbol_Rojinegro< T > &root)
	A continuación examinaremos cómo el procedimiento "corregirEliminar" restaura las propiedades de árbol rojo-negro:.

Documentación de las definiciones

#define Rojinegro_h

Evita inclusión múltiple de "Arbol_Rojinegro.h".

Definición en la línea 2 del archivo Arbol_Rojinegro.h.

Documentación de las funciones

template<class T>

void rotarIzq	(	Arbol_Rojinegro< T > &	x,
		Arbol_Rojinegro< T > &	raiz
	)

Rotaciones de la clase Arbol_Rojinegro: -Las operaciones de inserción y eliminación de un árbol binario de búsqueda, si se aplican a un árbol rojinegro pueden modificar ls propiedades basicas que debe cumplir la clase Arbol_Rojinegro.

-Para restaurar estas propiedades es necesario cambiar el color de algunos nodos así como también la estructura de los apuntadores. -La estructura de los apuntadores se cambia mediante rotación, la cual es una operación que preserva las propiedades de un árbol binario de búsqueda. -Existen dos tipos de rotaciones: a la izquierda y a la derecha.

para realizar comparaciones nulas

Definición en la línea 49 del archivo Arbol_Rojinegro.h.

template<class T>

void rotarDer	(	Arbol_Rojinegro< T > &	y,
		Arbol_Rojinegro< T > &	raiz
	)

para realizar comparaciones nulas

Definición en la línea 74 del archivo Arbol_Rojinegro.h.

template<class T>

void insercion	(	Arbol_Rojinegro< T > &	root,
		const T &	val
	)

Inserción de un elemento en un arbol rojinegro: -La inserción de un nodo en un árbol rojo-negro con n elementos puede realizarse en un tiempo O(lg n).

-Se usara una versión modificada de la rutina de inserción en un árbol binario de búsqueda ordinario (version de orderedInsert de la clase Bin_Tree).

Puede observarse que el código es casi igual a la rutina de inserción en un árbol binario de búsqueda normal, salvo por tres diferencias fundamentales:

1=> En lugar de usar el null ordinario, utilizamos un booleano al cual vamos a definir como true (verdadero) cuando el nodo de color negro.
2=> Se establece el color del nodo z a insertar como rojo, o sea false.
3=> Se invoca a la rutina corregirInserción(z) para restaurar las propiedades de árbol rojinegro.

Nótese que una vez insertado y marcado como rojo el nodo z (justo antes de llamar a corregirInsercion)se presenta la siguiente situación: -Las propiedades 1 y 3 indudablemente se cumplen, ya que los hijos del nuevo nodo rojo insertado son true(negros) y por lo tanto son negros. -La propiedad 5 se cumple debido a que no se ha insertado ningún nodo negro y por lo tanto todas las rutas de la raíz a las hojas siguen teniendo el mismo número de hijos negros. -Las únicas propiedades que podrían ser violadas son la 2, que requiere que la raíz sea negra y la 4, que dice que un nodo rojo no puede tener nigún hijo rojo. Ambas violaciones se deben a que el nuevo nodo es rojo. -La propiedad 2 se viola si z es la raíz y la 4 si el padre de z es rojo.

arbol vacio.

o sea es rojo.

Definición en la línea 116 del archivo Arbol_Rojinegro.h.

template<class T>

void corregirInsercion	(	Arbol_Rojinegro< T > &	z,
		Arbol_Rojinegro< T > &	raiz
	)

Para estudiar cómo funciona la funcion "corregirInsercion" que permite restaurar las propiedades de árbol rojo-negro examinaremos el código en tres partes: -inicialización.

-terminación. -mantenimiento.

Inicialización: Antes de la primera iteración, comenzamos con un árbol rojo-negro sin violaciones y añadimos un nodo rojo z. Si hay una violación a la propiedad 2 (raíz negra), entonces la raíz roja tiene que ser el nodo recién añadido z, el cual sería el único nodo interno del árbol. Debido a que tanto el padre como los hijos de z son false, el cual es negro, noy hay violación de la propiedad 4. Así, esta sería la única violación en el árbol. Si hay una violación de la propiedad 4, entonces, considerando que los hijos del nodo z son true (negros) y que el árbol no tenía violaciones antes de la inserción de z, la violación tiene que ser porque tanto z como z:padre son rojos. Es imposible que haya alguna otra violación de las propiedades.

Terminación: Cuando el ciclo termina, lo hace porque z:padre es negro. Así, no hay violación de la propiedad 4 al terminar el ciclo. La única propiedad que podría fallar es la propiedad 2, la cual es restaurada en la ultima instruccion de la funcion.

Mantenimiento: Hay seis casos a considerar dentro del ciclo while, pero tres de ellos son simétricos; dependiendo de si z:padre es un hijo izquierdo o un hijo derecho del abuelo de z (z:padre:padre). Se explicara la primera posibilidad: Nótese que z:padre:padre existe, ya que la condición del ciclo es que z:padre sea rojo y por lo tanto z:padre no puede ser la raíz. El primero de los tres casos a considerar se diferencia de los casos 2 y 3 por el color del tío de z (z:padre:padre:der). Si el tío (y) es rojo entonces se ejecuta el caso 1. De otro modo se transfiere el control a los casos 2 y 3. En los tres casos el abuelo de z (z:padre:padre) es negro, puesto que el padre z:padre es rojo y la propiedad 4 sólo puede ser violada entre z y z:padre.

-Caso 1: El tío de z (y) es rojo El caso 1 se ejecuta cuando tanto z:padre e y son rojos. Puesto que z:padre:padre es negro, se pueden colorear z:padre e y como negros, corrigiendo así el problema de que z y z:padre sean ambos rojos, y colorear z:padre:padre como rojo, manteniendo de esta manera la propiedad 5. Luego se repite el ciclo con z:padra:padre como el nuevo nodo z. Nótese que si al fnal del ciclo la raíz queda roja, la violación es corregida en la ultima instruccion;

-Caso 2: El tío de z (y) es negro y z es el hijo derecho de su padre. En el caso 2 z es el hijo derecho de z:padre. En este caso se procede simplemente a realizar una rotación a la izquierda para transformar el problema en el caso 3. Al terminar la rotación se considerará z al antiguo z:padre que fue rotado.

-Caso 3: El tío de z (y) es negro y z es el hijo izquierdo de su padre. En el caso 3 tanto z como z:padre son rojos y z:padre:padre es negro. La acción a realizar en este caso consiste en hacer negro a z:padre y rojo a z:padre:padre y realizar una rotación a la derecha de z:padre:padre. Como z y z:padre originalmente eran rojos, la rotación realizada no introduce una violación de la propiedad 5 ya que la altura-negra de los nodos no resulta afectada y como ya no quedan nodos rojos consecutivos el procedimiento está terminado.

Definición en la línea 219 del archivo Arbol_Rojinegro.h.

template<class T>

Bin_Tree<T> busca_nodo	(	Bin_Tree< T > &	root,
		const T &	val
	)

Funcion para buscar un nodo en el arbol.

Definición en la línea 282 del archivo Arbol_Rojinegro.h.

template<class T>

void borrado	(	Arbol_Rojinegro< T > &	root,
		const T &	val
	)

Eliminación de un elemento en el arbol rojinegro: La elminación de un nodo en un árbol rojo-negro con n elementos puede realizarse en un tiempo O(lg n).

Puede observarse que el código es casi igual a la rutina de inserción en un árbol binario de búsqueda normal, salvo por las siguientes diferencias:

1=> En lugar de usar el null ordinario, utilizamos un booleano definido como false cuando necesitemos que la hoja tenga color negro.
2=> Se hace una asignación incondicional (en un árbol binario de búsqueda normal sólo se puede hacer esta asignación si x no es nulo). En caso de que x sea false, esta asignación facilitará la codificación de corregirEliminar().
3=> Se invoca a la rutina corregirEliminación(z)para restaurar las propiedades de árbol rojo-negro en caso de que el nodo desaparecido sea negro.

Nótese que si el nodo desaparecido es negro, pueden presentarse tres problemas:

1=> Si y era la raíz y un hijo rojo de y se convierte en la nueva raíz, se viola la propiedad 2.
2=> Si tanto x como y:padre (que también es x:padre) eran rojos, entonces se viola la propiedad 4.
3=> La remoción de y hace que cualquier ruta que previamente contenía a y ahora tenga un nodo negro menos. Por lo tanto se viola la propiedad 5. Para evitar lidiar con este problema, asumiremos que la negrura del nodo desaparecido y se le transfiere a su hijo x. El problema ahora es que x no es ni negro ni rojo (violando la propiedad 1), sino que es doble negro o rojo-negro y contribuye 2 o 1, respectivamente, al conteo de nodos negros en las rutas que lo contengan. El atributo color de x seguirá siendo false (si es rojo-negro) o true (si es negro-negro). En otras palabras, el atributo negro extra de un nodo se refleja por el hecho de que x apunte a él y no en el atributo color.

Definición en la línea 321 del archivo Arbol_Rojinegro.h.

template<class T>

void corregirEliminar	(	Arbol_Rojinegro< T > &	x,
		Arbol_Rojinegro< T > &	root
	)

A continuación examinaremos cómo el procedimiento "corregirEliminar" restaura las propiedades de árbol rojo-negro:.

Dentro del ciclo while, x siempre apunta a un nodo doble-negro distinto a la raíz. En la segunda línea determinamos si x es un hijo izquierdo de su padre x:padre. La situación cuando x es el hijo derecho es simétrica, así que nos concentraremos sólo en el primer caso.

Nótese que el propósito del ciclo while es mover el negro extra hasta que: -1=> x apunte a un nodo rojo-negro, en cuyo caso se colorea como negro (no doble) fuera del ciclo, en la última línea. -2=> x apunta a la raíz, en cuyo caso la negrura extra puede ser simplemente desaparecida o. -3=> se puedan ejecutar rotaciones y cambios de colores apropiados.

En primer lugar mantenemos un apuntador w al hermano de x. Puesto que x es doble negro, w no puede ser true; de otro modo el número de nodos negros en la ruta de x:padre a la hoja w sería menor que el número en la ruta de x:padre a x. En el código se indican cuatro casos. La idea clave en cada caso es observar que el número de nodos negros (incluyendo el negro extra de x) desde la raíz del subárbol a cada uno de sus subárboles es preservado por la transformación. Así, si la propiedad 5 se cumple antes de la transformación, también se cumple después. Lo mismo ocurre con los otros subárboles y en los otros cosas.

Posibles casos: -1=> El hermano (w) de x es rojo Como los dos hijos de w tienen que ser negros, se pueden intercambiar una rotación a la izquierda de x:padre. Después de la rotación, el hermano de x será uno de los antiguos hijos negros de w, convirtiendose así el problema en uno de los casos 2, 3 o 4. -2=>El hermano (w) de x es negro, los dos hijos de w son negros En este caso quitamos negrura tanto de x (moviendo el apuntador) como de w (convirtiéndolo en negro) y movemos la negrura al padre de ambos (haciendo que x apunte ahora x:padre). Después de esto, el ciclo se repite, a menos que la negrura extra se haya movido a la raíz del árbol, de donde se puede desaparecer sin problemas. -3=> El hermano (w) de x es negro, el hijo izquierdo de w es rojo y el hijo derecho de w es negro En este caso se pueden intercambiar los colores de w y su hijo izquierdo w:izq y luego ejecutar un rotación a la derecha de w sin violar las propiedades. Esto no nos permite desaparecer la negrura extra de x, pero nos permite transformar el problema al Caso 4, que resolvimos previamente. -4=> El hermano (w) de x es negro y el hijo derecho de w es rojo En este caso intercambiando algunos colores (haciendo que w tenga el color del padre y que w:padre y w:der sean negros) y haciendo una rotación a la izquierda podemos eliminar la negrura extra de x sin violar ninguna de las propiedades de árbol rojo negro. Nótese que por la manera en que se asignaron los colores es imposible que se viole la propiedad 4 ya que aunque w podría convertirse en rojo, su hijo derecho se convierte en negro. El hijo izquierdo de w es potencialmente rojo, pero su nuevo padre después de la rotación será w:padre el cual previamente había se había coloreado de negro. Finalmente, podría ser que w quede rojo y que quede como raíz del árbol, pero fuera del ciclo se corrige esta situación.

Definición en la línea 407 del archivo Arbol_Rojinegro.h.

Referencia del Archivo Arbol_Rojinegro.h

Clases

Definiciones

Funciones

Documentación de las definiciones

Documentación de las funciones