Arbol_Rojinegro.h

Ir a la documentación de este archivo.

#ifndef Rojinegro_h
#define Rojinegro_h  ///< Evita inclusión múltiple de \c "Arbol_Rojinegro.h"
#include "Bin_Tree.h"    

/**
Clase Arbol_RojiNegro:
        -Un árbol rojo-negro resulta de la representación de un árbol 2-3-4 mediante 
         un árbol binario.      
        -Cada nodo de un árbol rojo negro contiene la siguiente información: 
         color, valor, hijo izquierdo, hijo derecho y padre. 
        -Si un hijo o el padre de un nodo no existe, el apuntador correspondiente
         contiene el valor NULL, el cual consideraremos como un nodo cuyo color es negro. 
        -En lo sucesivo nos referiremos a los nodos distintos a las hojas (NULL) como 
         nodos internos del árbol y a las hojas y al padre de la raíz como nodos externos.

Todo árbol Rojinegro satisface las siguientes propiedades:
        -Todo nodo es rojo o negro
        -La raíz es negra
        -Toda hoja (NULL) es negra.
        -Si un nodo es rojo, entonces sus dos hijos son negros.
        -Para cada nodo, todas las rutas de un nodo a las hojas (NULLs) contienen el mismo 
         número de nodos negros. El número de nodos negros en esta ruta se conoce 
         como altura-negra del nodo.
*/
template <class T>
class Arbol_Rojinegro : public Bin_Tree <T> {
public:
        Arbol_Rojinegro() :  Bin_Tree() {}///Constructor.
        Arbol_Rojinegro( Bin_Tree & o) : Bin_Tree(o){}
        Arbol_Rojinegro( const T& val) : Bin_Tree (val) {}///Constructor a partir de un valor.
        ~Arbol_Rojinegro() {}  ///Destructor.
        bool color;  /// guarda el color.

};


/**
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.
*/
template <class T>
void rotarIzq (Arbol_Rojinegro<T>& x , Arbol_Rojinegro<T>& raiz ){
        Arbol_Rojinegro<T> nulo;  /// para realizar comparaciones nulas
        Arbol_Rojinegro<T> y = x.right();
        x.right() = y.left();
        y.left().padre() = x;
        y.padre() = x.padre();
        if (Comp(x.padre(),nulo))               { raiz = y;     }
        else if ( Comp(x , x.padre().left())){ x.padre().left()  = y;  }
        else                                                    { x.padre().right() = y;  }
        y.left()  = x;
        x.padre() = y;
}// fin de rotar izquierda

/**
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.
*/
template <class T>
void rotarDer (Arbol_Rojinegro<T>& y , Arbol_Rojinegro<T>& raiz ){
        Arbol_Rojinegro<T> nulo;  /// para realizar comparaciones nulas
        Arbol_Rojinegro<T> x = y.right();
        y.right() = x.left();
        x.left().padre() = y;
        x.padre() = y.padre();
        if (Comp(y.padre(),nulo))               { raiz = x;     }
        else if ( Comp(y , y.padre().left())){ y.padre().left()  = x;  }
        else                                                    { y.padre().right() = x;  }
        x.left()  = y;
        y.padre() = x;
}//fin de rotar derecha


/**
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.
*/
template <class T>
void insercion( Arbol_Rojinegro<T> & root , const T&  val ) {
        
        if ( root.isEmpty() ) { 
                 root.changeRoot(val); 
                 root.color = true;             //lo pinto de negro
                 return;}//Si esta vacio entonces meto el arbol z de raiz general.
        Arbol_Rojinegro<T> raiz(root) ;
        Arbol_Rojinegro<T> nulo ; /// arbol vacio.
        //Arbol_Rojinegro<T> raiz (L) ; /// copia del arbol enviado
        Arbol_Rojinegro<T> z (val);
        
        while ( ! raiz.isEmpty() ) {
        if ( val < raiz.dato() ) {
            if ( raiz.left().isEmpty() ) {
                raiz.makeLeftChild( z );
                z.left() = z.right() = nulo;
                                z.color = false; /// o sea es rojo.
                                corregirInsercion(z , raiz); //corrige los colores.
                                return;
            }
            else {
                raiz = raiz.right();
                                z.left() = z.right() = nulo;
                                z.color = false; /// o sea es rojo.
                                corregirInsercion(z , raiz); //corrige los colores.
                        }
        }
        else if ( val > raiz.dato() ) {
            if ( raiz.right().isEmpty() ) {
                raiz.makeRightChild( z );
                z.left() = z.right() = nulo;
                                z.color = false; /// o sea es rojo.
                                corregirInsercion(z , raiz); //corrige los colores.
                                return;
            }
            else {
                raiz = raiz.right();
                                z.left() = z.right() = nulo;
                                z.color = false; /// o sea es rojo.
                                corregirInsercion(z , raiz); //corrige los colores.                     
            }
        }
        }       
}//fin de insercion

/**
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.
*/
template <class T>
void corregirInsercion (Arbol_Rojinegro<T>& z , Arbol_Rojinegro<T>& raiz ){
        Arbol_Rojinegro<T> padre_uno = z.padre();  
        Arbol_Rojinegro<T> padre_dos =  z.padre().padre() ;
        Arbol_Rojinegro<T> y;
        // Creo estos arboles porque no puedo usar el REP del Bin_Tree  :(  .
        
        // true = negro   y   false = rojo.
        while ( padre_uno.color == false) {
                if ( Comp (z.padre() , z.padre().padre().left()) ){
                        y = z.padre().padre().right();
                        if (y.color == false){   // o sea; si y es rojo? entonces...
                                padre_uno.color = true; // pinto de negro
                                z.padre() = padre_uno;      // asi le agrego el campo color y lo pinto negro
                                y.color = true; // pinto de negro
                                padre_dos.color = false; // pinto de rojo
                                z.padre().padre() = padre_dos;//asi le agrego el campo color y lo pinto rojo
                                z = z.padre().padre();          
                        }
                        else{
                                if (Comp (z , z.padre().right())){
                                        z = z.padre();
                                        rotarIzq(z,raiz);
                                }
                                padre_uno.color = true; // pinto de negro
                                z.padre() = padre_uno;    // asi le agrego el campo color y lo pinto negro
                                padre_dos.color = false; // pinto de rojo
                                z.padre().padre() = padre_dos; //asi le agrego el campo color y lo pinto rojo
                                rotarDer(padre_dos,raiz);
                                z.padre().padre() = padre_dos;
                        }
                }
                else {
                        y = z.padre().padre().left();
                        if (y.color == false){ // si es rojo entonces......
                                padre_uno.color = true; // pinto de negro
                                z.padre() = padre_uno;
                                y.color = true; // y es negro.
                                padre_dos = z.padre().padre();
                                padre_dos.color = false; // z.padre().padre() es rojo.
                                z.padre().padre() = padre_dos;
                                z = z.padre().padre();
                        }
                        else {
                                if (Comp( z , z.padre().left())){
                                        z = z.padre();
                                        rotarDer(z,raiz);
                                }
                                padre_uno.color = true; // pinto de negro
                                z.padre() = padre_uno;
                                padre_dos = z.padre().padre();
                                padre_dos.color = false; // pinto de rojo
                                z.padre().padre() = padre_dos;
                                rotarIzq( padre_dos , raiz);
                                z.padre().padre() = padre_dos;
                        }
                }
        }//fin del ciclo while
        raiz.color = true; // pinto la raiz de negro
}//fin de corregirInsercion


///Funcion para buscar un nodo en el arbol.
template <class T>
Bin_Tree<T> busca_nodo (Bin_Tree<T>& root ,const T& val ){

                Bin_Tree<T> raiz = root;
                if (raiz.dato() > val ){ raiz = raiz.left();}
                if (raiz.dato() < val ){ raiz = raiz.right();}
                if (raiz.dato() == val ){return * raiz;}
                else{busca_nodo(raiz,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.
*/
template <class T>
void borrado (Arbol_Rojinegro<T>& root ,const T& val ){
        if ( root.isEmpty() ) {   return;  } // porque esta vacio.
    Arbol_Rojinegro<T> raiz (root);
        Arbol_Rojinegro<T> z(busca_nodo(raiz,val));
        Arbol_Rojinegro<T> y , x;       
        if (z.left().isEmpty() && z.right().isEmpty()){
                z.erase(); // no tiene hijos, solo tiene que borrarse.
        }
        else{
                y = z;
        }
        if (y.left().isEmpty()){
                x = y.left();
        }
        else{
                x = y.right();
        }
        x.padre() = y.padre();
        if ( y.padre().isEmpty()){
                root = x;
        }
        else{ 
                if( Comp (y , y.padre().left())){
                        y.padre().left() = x;
                }
        }
        if ( Comp (y,z) == false){
                z.dato() = y.dato();//copiar datos adicionales si aplica
        }
        if ( y.color == true){
                corregirEliminar(x, 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.
*/
template <class T>
void corregirEliminar(Arbol_Rojinegro<T>& x,Arbol_Rojinegro<T>& root) {
        Arbol_Rojinegro<T> w;
        Arbol_Rojinegro<T> temp;  
        Arbol_Rojinegro<T> tmp;
        Arbol_Rojinegro<T> tempo;
        Arbol_Rojinegro<T> tempor;
        while ( Comp(x,root)==false && x.color == false) {
                if (  Comp(x,x.padre().left())) {
                        w = x.padre().right();
                        if (w.color == false) {
                                w.color = true;
                                temp = x.padre();
                                temp.color = false;
                                x.padre() = temp;
                                rotarIzq(temp,root);
                                x.padre() = temp;
                                w = x.padre().right();
                        }
                        tmp = w.left();
                        tempo = w.right();
                        if (tmp.color == true && tempo.color == true) {
                        w.color = false;
                        x = x.padre();
                        }
                        else {
                                if (tempo.color == true) {
                                        tmp.color = true;
                                        w.color = false;
                                        rotarDer(w,root);
                                        w = x.padre().right();
                                }
                                tempor = x.padre();
                                w.color = tempor.color;
                                tempor.color = true;
                                tempo.color = true;
                                rotarIzq(tempor,root);
                                x.padre() = tempor;
                                x = root;
                        }       
                } ///
                if (  Comp(x,x.padre().right())) {
                        w = x.padre().left();
                        if (w.color == false) {
                                w.color = true;
                                temp = x.padre();
                                temp.color = false;
                                x.padre() = temp;
                                rotarIzq(temp,root);
                                x.padre() = temp;
                                w = x.padre().left();
                        }
                        tmp = w.right();
                        tempo = w.left();
                        if (tmp.color == true && tempo.color == true) {
                        w.color = false;
                        x = x.padre();
                        }
                        else {
                                if (tempo.color == true) {
                                        tmp.color = true;
                                        w.color = false;
                                        rotarDer(w,root);
                                        w = x.padre().left();
                                }
                                tempor = x.padre();
                                w.color = tempor.color;
                                tempor.color = true;
                                tempo.color = true;
                                rotarIzq(tempor,root);
                                x.padre() = tempor;
                                x = root;
                        }       
                } 
        }       
        x.color = true;
}

#endif  

---