Bin_Tree_Lib.h

Go to the documentation of this file.

// Bin_Tree_Lib.h (c) 2007 adolfo@di-mare.com

/** \file  Bin_Tree_Lib.h
    \brief Funciones de apoyo para la clase \c Bin_Tree<E>.

    \author Adolfo Di Mare <adolfo@di-mare.com>
    \date   2007

    - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
*/

#include "Bin_Tree.h"
#include <cassert>  // assert()
#include <iostream> // cout
#include <set>

/** Retorna la longitud del camino desde \c "T" hasta la raíz del árbol.
    - Retorna la profundidad del sub-árbol respecto de su raíz.
    - La profundidad de la raíz del árbol es cero.
    - <code> [ T.isEmpty() ] ==> [ depth(T) == 0 ] </code>
    - <code> [ T.isEmpty() == true ] ==> [ height(T) == -1 ] </code>
*/
template <class E>
int depth( const Bin_Tree<E> & T ) {
    if ( T.isEmpty() ) {
        return -1;
    }
    unsigned n = 0;
    Bin_Tree<E> F = T;
    do {
        F = F.father();
        ++n;
    } while ( ! F.isEmpty() );
    return n-1;
}

/// Calcula la altura de sub-árbol.
///  - Esta función es el paso recursivo necesario para implementar \c height().
///  - Recorre recursivamente el árbol y recuerda la máxima profundidad encontrada en \c "max".
///  - \c "actual" es la profundidad del nodo actual.
template <class E>
void height_recurse( Bin_Tree<E> T, int &max, int actual ) {
    if ( T.isEmpty() ) {
        if (max < actual) {
            max = actual; // se deja el más grande de los 2
        }
    } else {
        height_recurse( T.left(),  max, actual+1 );
        height_recurse( T.right(), max, actual+1 );
    }
    return;
}

/** Retorna la altura de \c "T" o \c -1 si el árbol está vacío.
    - La altura es la distanca desde \c "T" hasta la hoja más profunda en el
      sub-árbol formado por todos los descendientes de \c "T".
    - La altura de un nodo hoja siempre es cero.
    - <code> [ T.isLeaf()  == true ] ==> [ height(T) == 0 ] </code>
    - <code> [ T.isEmpty() == true ] ==> [ height(T) == -1 ] </code>

    \code
                                     [ depth() height() ]
    a [0 4]                a               [0 4]
    |--b [1 1]             |--b            [1 1]
    |  |--f [2 0]          |  |--f         [2 0]
    |  +--h [2 0]          |  +--h         [2 0]
    +--e [1 3]             +--e            [1 3]
       |--i [2 0]             |--i         [2 0]
       +--j [2 2]             +--j         [2 2]
          |--l [3 0]             |--l      [3 0]
          +--m [3 1]             +--m      [3 1]
             |--n [4 0]             |--n   [4 0]
             +--o [4 0]             +--o   [4 0]
    \endcode */
template <class E>
inline int height( Bin_Tree<E> T ) {
    #if 1
        if( T.isEmpty() ) {
            return -1;
        }
        else {
            int hLeft  = height( T.left() );
            int hRigth = height( T.right() );
            return 1 + ( hLeft > hRigth ? hLeft : hRigth );
        }
    #else
        int actual,  max;
        max    = 0;
        actual = 0;
        height_recurse( T, max, actual );
    //  max = ( max > 0 ? max-1 : 0 );
        return max-1;
    #endif
}

/** Copia profunda de \c "other".
    - Copia todo el valor de \c "other" sobre \c "T", de forma que el nuevo valor de
      \c "*this" sea un duplicado exacto del valor de \c "other".
    - El valor anterior de \c "T" se pierde.
    - El objeto \c "other" mantiene su valor anterior.
    - Luego de la copia, cuando el valor de \c "other" cambia, el de \c "*this" no cambiará,
      y viceversa, pues la copia es una copia profunda; no es superficial.
    - Si \c "T" es \c "other" entonces su valor no cambia.
    - Después de esta operación siempre ocurre que <code> T == other </code>.
    \par Complejidad:
         O( \c T.count() ) + O( \c other.count() ).
    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc05
*/
template <class E>
void copyDeep( Bin_Tree<E>& T, const Bin_Tree<E> &other ) {
    if ( &T == &other ) {
        return; // mismo árbol ==> evita auto-copia
    }
    else if ( other.isEmpty() ) { // si el otro está vacío
        T.erase();                // yo también quedo vacío
        return;
    }
    if ( T.same(other) ) {
    //  T.erase(); // mismo valor ==> borra a "T"
    }

    Bin_Tree<E> Root( other.data() ); // nueva raíz del árbol

    if ( ! other.left().isEmpty() ) { // copia el hijo izquierdo
        Bin_Tree<E> Child;
        copyDeep( Child, other.left() );
        Root.makeLeftChild( Child );
    }

    if ( ! other.right().isEmpty() ) { // copia el hijo derecho
        Bin_Tree<E> Child;
        copyDeep( Child, other.right() );
        Root.makeRightChild( Child );
    }

    T = Root;
}

/// Compara recursivamente los árboles \c "p" y \c "q".
template <class E>
bool comp(const Bin_Tree<E>& p, const Bin_Tree<E>& q) {
    if ( p.same(q) ) {
        return true;
    }
    if ( p.isEmpty() || q.isEmpty() ) { // son diferentes...
        return false; // ...pues sólo 1 está vácio
    }
    if ( ! (p.data() == q.data()) ) {
        return false; // valor diferente en la raíz
    }
    if ( ! comp( p.left(), q.left() ) ) {
        return false; // valor diferente en el sub-árbol izquierdo
    }
    if ( ! comp( p.right(), q.right() ) ) {
        return false; // valor diferente en el sub-árbol derecho
    }

    return true; // pues nunca encontró sub-árboles diferentes
}

/// Graba el valor del árbol como hilera Lisp: \c (a (b (f) (h)) (e (i) (k (l) (m (n) (o))))).
template <class E>
std::ostream& operator << ( std::ostream & COUT , const Bin_Tree<E> & T ) {
    if ( T.isEmpty() ) {
        return COUT;
    }
    {   COUT << '(' << *T; // raíz
        if ( ! T.left().isEmpty() ) {
            COUT << ' ';
            COUT << T.left();
        }
        if ( ! T.right().isEmpty() ) {
            COUT << ' ';
            COUT << T.right();
        }
        COUT << ')';
    }
    return COUT;
}

template <class E>
inline bool operator == (const Bin_Tree<E> &p, const Bin_Tree<E> &q)
{ return comp( p , q ); }
template <class E>
inline bool operator != (const Bin_Tree<E> &p, const Bin_Tree<E> &q)
{ return !(p == q); }

/** Cuenta la cantidad de valores almacenados en el árbol.
    - Cuenta conrrectamente aún si el árbol tiene ciclos.
    - El conjunto \c "S" registra cuáles sub-árboles fueron ya contados.
    - Lo usual es invocar \c S.clear() antes de invocar esta función.

    \dontinclude test_Bin_Tree.cpp
    \skipline    test::sizeStrong()
    \until       }}
    \see         test_Bin_Tree<E>::test_sizeStrong()
*/
template <class E>
int sizeStrong( const Bin_Tree<E>& T, std::set<E*> & S ) {
    if ( T.isEmpty() )  {
        return 0;
    }
    else if ( S.find( &T.data() ) == S.end() ) {
        S.insert( &T.data() );
        return 1 + sizeStrong( T.left() , S ) + sizeStrong( T.right() , S );
    }
    else {
        return 0;
    }
}

/// Usa \c T.ok() para verificar la invariante de \c Bin_Tree<E>
template <class E>
inline bool check_ok(const Bin_Tree<E>& T) {
    return T.ok();
}

/// Agrega una copia de \c "val" al árbol binario ordenado \c "T".
/// - No agrega duplicados.
template <class E>
void orderedInsert( Bin_Tree<E> & T , const E& val ) {
//  Versión no recursiva
    if ( T.isEmpty() ) {
        T.changeRoot( val );
        return;
    }
    Bin_Tree<E> Root = T; // Root es la raíz
    Bin_Tree<E> Child ( val ); // El nuevo sub-árbol hoja a insertar
    while ( ! Root.isEmpty() ) {
        if ( val < Root.data() ) {
            if ( Root.left().isEmpty() ) {
                Root.makeLeftChild( Child );
                break;
            }
            else {
                Root = Root.left();
            }
        }
        else if ( val > Root.data() ) {
            if ( Root.right().isEmpty() ) {
                Root.makeRightChild( Child );
                break;
            }
            else {
                Root = Root.right();
            }
        }
        else {
            break;  // DUPLICADO: no hace nada
        }
    }
    return;
}

/// Agrega una copia de \c "val" al árbol binario ordenado \c "T".
/// - No agrega duplicados.
///
/// \author Carlos Andres Gonzalez Vargas <cagv26@gmail.com>
template <class E>
void orderedInsert_Recursive( Bin_Tree<E> & T , const E& val ) {
    if ( T.isEmpty() ) { // Si el arbol esta vacío
        T.changeRoot( val ); // insertar el valor en el arbol
        return;
    }
    if ( val < T.data() ){ // si el valor del arbol es menor que le valor a insertar
        if ( T.left().isEmpty() ){ // si el hijo izquierdo esta vacio
            T.makeLeftChild( Bin_Tree<E>(val) ); // inserte un nuevo subarbol con el valor a insertar
            return;
        }
        else { //si el hijo izquierdo existe
            orderedInsert( T.left(), val ); //insertese ahora con el hijo izquierdo como base
        }
    }
    else if ( val > T.data() ) {//si el valor del arbol es mayor que le valor a insertar
        if ( T.right().isEmpty() ){//si el hijo derecho esta vacio
            T.makeRightChild(Bin_Tree<E> (val)); //inserte un nuevo subarbol con el valor a insertar
            return;//regresar
        }
        else { //si el hijo derecho existe
            orderedInsert(T.right(),val);//insertese ahora con el hijo derecho como base
        }
    }
    else {
        return; // no inserta duplicados
    }
    return; //regresar
}

/* Determina si existe un reordenamiento de los hijos del árbol \c T1 que resulta en el árbol \c T2.
   - Los siguientes árboles son homomorfos:
    \code
           a                     a              a
          / \                   / \            / \
         /   \                 /   \          /   \
        b     e               e     b        e     b
       / \   / \             / \   / \      / \   / \
      f   h i   k           k   i h   f    i   k f   h
               / \         / \                / \
              l   m       m  l               m   l
                 / \     / \                / \
                n   o   o   n              n   o
    \endcode
*/
template <class E>
bool homomorfo( const Bin_Tree<E> & T1, const Bin_Tree<E> & T2 ) {
    if ( T1.isEmpty() && T2.isEmpty() ) {
        return true; // 2 árboles vacíos son homomorfos
    }
    if ( T1.isEmpty() || T2.isEmpty() ) {
        return false; // solo 1 de los 2 no está vacío
    }
    if ( T1.data() != T2.data() ) {
        return false; // valor diferente en la raíz del árbol
    }
/*          T1                     T2
           /  \                   /  \
          /    \                 /    \
    T1_paco   T1_lola      T2_paco   T2_lola
*/
    Bin_Tree<E> T1_paco = T1.left();    Bin_Tree<E> T2_paco = T2.left();
    Bin_Tree<E> T1_lola = T1.right();   Bin_Tree<E> T2_lola = T2.right();
    if ( homomorfo( T1_paco,  T2_paco ) ) {
        if ( homomorfo( T1_lola,  T2_lola ) ) {
            return true;
        } if ( homomorfo( T1_paco,  T2_lola ) ) {
            return homomorfo( T1_lola,  T2_paco );
        }
        else {
            return false;
        }
    }
    else  if ( homomorfo( T1_paco, T2_lola ) ) {
        return homomorfo( T1_lola, T2_paco );
    }
    else { // assert( !homomorfo( T1_paco,  T2_paco ) && ! homomorfo( T1_paco, T2_lola ) );
        return false;

    }
}

/** Convierte a \c "T" en su sub-árbol espejo.
    - Recursivamente, sus hijos quedan en orden inverso del
      orden en el que  aparecían originalmente en \c "T".

    \code
           a                  a
          / \                / \
         /   \              /   \
        b     e            e     b
       / \   / \          / \   / \
      f   h i   k        k   i h   f
               / \      / \
              l  m      m   l
                / \    / \
               n   o  o   n
    \endcode
*/
template <class E>
void mirror( Bin_Tree<E> T ) {
     if ( T.isEmpty() ) {
        return; // se sale si el árbol está vacío
    }
    // intercambia los hijos
    Bin_Tree<E> Left  = T.left();  // sostiene a cada hijo
    Bin_Tree<E> Right = T.right();
    T.makeLeftChild( Right ); // Pone el hijo derecho a la izquierda
    T.makeRightChild( Left ); // Pone el hijo izquierdo a la derecha
    mirror( Left  );
    mirror( Right ); // recursivamente modifica los hijos
}

// Graba en \c COUT en orden IPD el contenido del árbol binario \c "T".
template <class E>
void IPD( std::ostream & COUT, const Bin_Tree<E> & T ) {
    if ( T.isEmpty() ) {
        return; // porque ya terminó
    }
    IPD ( COUT , T.left() );
    COUT << " " << T.data();
    IPD ( COUT , T.right() );
}

/** Rota la raíz del arbol binario \c "K2" con su hijo izquierdo.
    \author Jorge Arturo Cordero Vargas <corderazo00@hotmail.com>
    \author Mark Allen Weiss
\code
              [ K2 ]                 [ K1 ]
             /      \     ====\     /      \
            /        \    ====/    /        \
      [ K1 ]         /\           /\         [ K2 ]
     /      \       /  \         /  \       /      \
    /        \     /  Z \       / X  \     /        \
   /\        /\   /______\     /______\   /\        /\
  /  \      /  \                         /  \      /  \
 / X  \    /  Y \                       / Y  \    /  Z \
/______\  /______\                     /______\  /______\
\endcode
*/
template <class E>
Bin_Tree<E> rotateWithLeftChild( Bin_Tree<E> K2 ) {
    Bin_Tree<E> K1 = K2.left();      // AvlNode k1 = k2.left;
    K2.makeLeftChild(  K1.right() ); // k2.left = k1.right;
    K1.makeRightChild( K2 );         // k1.right = k2;
    return K1;                       // return k1;
}

/** Rota la raíz del arbol binario \c "K1" con su hijo derecho.
    \author Jorge Arturo Cordero Vargas <corderazo00@hotmail.com>
    \author Mark Allen Weiss
\code
      [ K1 ]                                 [ K2 ]
     /      \             ====\             /      \
    /        \            ====/            /        \
   /\         [ K2 ]                 [ K1 ]         /\
  /  \       /      \               /      \       /  \
 / X  \     /        \             /        \     /  Z \
/______\   /\        /\           /\        /\   /______\
          /  \      /  \         /  \      /  \
         / Y  \    /  Z \       / X  \    /  Y \
        /______\  /______\     /______\  /______\
\endcode
*/
template <class E>
Bin_Tree<E> rotateWithRightChild( Bin_Tree<E> K1 ) {
    Bin_Tree<E> K2 = K1.right();     // AvlNode k2 = k1.right;
    K1.makeRightChild( K2.left() );  // k1.right = k2.left;
    K2.makeLeftChild(  K1 );         // k2.left = k1;
    return K2;                       // return k2;
}

/** Hace una rotacion doble con el hijo izquierda para el arbol binario \c "K3".
    - Primero rota el hijo izquierdo con su hijo derecho.
    - Luego \c "K3" con el nuevo hijo izquierdo.

    \author Jorge Arturo Cordero Vargas <corderazo00@hotmail.com>
    \author Mark Allen Weiss

\code
              [ K3 ]                            [ K2 ]
             /      \                          /      \
            /        \                       /          \
      [ K1 ]         /\                    /              \
     /      \       /  \  ====\      [ K1 ]                [ K3 ]
    /        \     /  D \ ====/     /      \              /      \
   /\      [ K2 ] /______\         /        \            /        \
  /  \      /  \                  /\        /\          /\        /\
 / A  \    /    \                /  \      /  \        /  \      /  \
/______\  /      \              / A  \    /  B \      / C  \    /  D \
         /\      /\            /______\  /______\    /______\  /______\
        /  \    /  \
       / B  \  /  C \
      /______\/______\         K1 <= K2 <= K3
\endcode
*/
template <class E>
Bin_Tree<E> doubleWithLeftChild( Bin_Tree<E> K3 ) {
    K3.makeLeftChild( rotateWithRightChild( K3.left() ) ) ;
        // k3.left = rotateWithRightChild( k3.left );
    return rotateWithLeftChild( K3 );
        // return rotateWithLeftChild( k3 );
}

/** Hace una rotacion doble con el hijo de la derecha para el arbol binario \c "K1".
    - Primero rota el hijo derecho con su hijo izquierdo.
    - Luego \c "K3" con el nuevo hijo derecho.

    \author Jorge Arturo Cordero Vargas <corderazo00@hotmail.com>
    \author Mark Allen Weiss

\code
      [ K1 ]                                    [ K2 ]
     /      \                                  /      \
    /        \                               /          \
   /\         [ K3 ]                       /              \
  /  \       /      \     ====\      [ K1 ]                [ K3 ]
 / A  \     /        \    ====/     /      \              /      \
/______\ [ K2 ]      /\            /        \            /        \
          /  \      /  \          /\        /\          /\        /\
         /    \    /  D \        /  \      /  \        /  \      /  \
        /      \  /______\      / A  \    /  B \      / C  \    /  D \
       /\      /\              /______\  /______\    /______\  /______\
      /  \    /  \
     / B  \  /  C \
    /______\/______\           K1 <= K2 <= K3
\endcode
*/
template <class E>
Bin_Tree<E> doubleWithRightChild( Bin_Tree<E> K1 ) {
    K1.makeRightChild( rotateWithLeftChild( K1.right() ) );
        // k1.right = rotateWithLeftChild( k1.right );
    return rotateWithRightChild( K1 );
        // return rotateWithRightChild( k1 );
}

/** Inserta el valor \c "val" en el árbol \c "T".
    - No agrega duplicados.
    - Usa inserción AVL para mantener a \c "T" balanceado.

    \author Jorge Arturo Cordero Vargas <corderazo00@hotmail.com>
    \author Mark Allen Weiss
    \date   2007
    \see http://www.cs.fiu.edu/~weiss/dsaajava/code/DataStructures/AvlTree.java
*/
template <class E>
void insertAVL( Bin_Tree<E> & T, const E & val ) {
    if ( T.isEmpty() ) {
        T.changeRoot( val );
    }
    else if ( val  < T.data() ) {
        if ( T.left().isEmpty() ) {
            T.makeLeftChild( Bin_Tree<E>(val) );
        }
        else {
            Bin_Tree<E> Left = T.left();
            insertAVL( Left , val );
            T.makeLeftChild( Left );
        }
        if ( height(T.left())-height(T.right()) == 2 ) {
            if ( val < T.left().data() ) {
                T = rotateWithLeftChild( T );
            }
            else {
                T = doubleWithLeftChild( T );
            }
        }
    }
    else if ( val > T.data() ) {
        if ( T.right().isEmpty() ) {
            T.makeRightChild( Bin_Tree<E>(val) );
        }
        else {
            Bin_Tree<E> Right = T.right();
            insertAVL( Right , val );
            T.makeRightChild( Right );
        }
        if ( height(T.right())-height(T.left()) == 2 ) {
            if ( val > T.right().data() ) {
                T = rotateWithRightChild( T );
            }
            else {
                T = doubleWithRightChild( T );
            }
        }
    }
    else {
        ;  // DUPLICADO: no hace nada
    }
    return;
/*
    El método \c insertAVL() deberá insertar en un árbol binario un valor no repetido,
    y asegurarse de que el árbol se encuentre siempre balanceado, esto es, que en
    ninguno de sus nodos la altura del subárbol derecho y la del subárbol izquierdo
    difieran en mas de 1 nivel.

    Para esto, se buscó un algoritmo en internet
    - http://www.cs.fiu.edu/~weiss/dsaajava/code/DataStructures/AvlTree.java
    que cumpliera con la especificación de la tarea. Este algoritmo se encarga de
    insertar un nodo en el árbol con insert(), y determinar, de ser necesario, el
    tipo y dirección de la rotación que se debe hacer en éste, ya sea unitaria
    con las funciones \c rotateWithLeftChild() y  \c rotateWithRightChild(), o
    dobles con \c doubleWithLeftChild() y \c doubleWithLeftChild(); para
    reestablecer el balance del árbol.
*/
}

/** \fn    template <class E> void deleteAVL( Bin_Tree<E> & T , const E& val );
    \brief Elimina el valor \c "val" del árbol \c "T".
    - Usa borrado AVL para mantener a \c "T" balanceado.
*/
template <class E>
void deleteAVL( Bin_Tree<E> & T , const E & val );

/** \fn    template <class E> void balanceAVL( Bin_Tree<E> & T );
    \brief Balancea el árbol ordenado \c "T" si está desbalanceado.
*/
template <class E>
void balanceAVL( Bin_Tree<E> & T );

/// Verifica que \c "T" es un árbol ordendao ascendentemente.
template <class E>
bool isAscending( const Bin_Tree<E> & T ) {
    if ( T.isEmpty() ) {
        return true;
    }
    if ( ! isAscending( T.left() ) ) {
        return false;
    }
    if ( ! isAscending( T.right() ) ) {
        return false;
    }
    // verifica que los hijos estén correctamente ordenados
    if ( ! T.left().isEmpty() ) {
         if ( ! ( T.left().data() <= T.data() ) ) {
              return false; // hijo izquierdo desordenado
         }
    }
    if ( ! T.right().isEmpty() ) {
         if ( ! ( T.right().data() >= T.data() ) ) {
              return false; // hijo derecho desordenado
         }
    }
    return true;
}

/// Verifica que \c "T" es un árbol balanceado AVL ascendente.
template <class E>
bool isAVL( const Bin_Tree<E> & T ) {
    if ( T.isEmpty() ) {
        return true;
    }
    if ( ! isAVL( T.left() ) ) {
        return false;
    }
    if ( ! isAVL( T.right() ) ) {
        return false;
    }

    // verifica que la altura de los hijos difiera en 1 como máximo
    int left  = height( T.left() );
    int right = height( T.right() );
    int diff = ( left > right ? left-right : right-left );
    if (diff > 1) {
        return false;
    }

    // verifica que los hijos estén correctamente ordenados
    if ( ! T.left().isEmpty() ) {
         if ( ! ( T.left().data() <= T.data() ) ) {
              return false; // hijo izquierdo desordenado
         }
    }
    if ( ! T.right().isEmpty() ) {
         if ( ! ( T.right().data() >= T.data() ) ) {
              return false; // hijo derecho desordenado
         }
    }
    return true;
}

#if 0
    template <class E>
    void balanceAVL( Bin_Tree<E> & T ) {
    }
    template <class E>
    void insertAVL( Bin_Tree<E> & T , const E& val ) {
        orderedInsert( T , val );
        balanceAVL(T);
    }
    template <class E>
    void deleteAVL( Bin_Tree<E> & T , const E& val) {
        orderedDelete( T , val );
        balanceAVL(T);
    }
#else
//  #include "A41369-A55609.h"
    #include "A52512.h"
//  #include "A54641.h"
#endif

// EOF: Bin_Tree_Lib.h