Bin_Tree.h

Ir a la documentación de este archivo.

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

/** \file  Bin_Tree.h
    \brief Declaraciones y definiciones para la clase \c Bin_Tree.

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

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

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

#include "lkptr.h"

template <class E> class Bin_Tree;  // declaración hacia adelante para Bin_Tree_Node <>

/// Nodos almacenados en el árbol
template <class E>
class Bin_Tree_Node {
public:
    friend class Bin_Tree<E>; // Sólo el árbol se le mete a este Rep
    typedef E value_type; ///< Nombre estándar del tipo de elemento contenido
        
private:
    
        value_type                 m_dato;   ///< Valor almacenado en el nodo.
    lkptr< Bin_Tree_Node <E> > m_padre; ///< Nodo padre (puede ser \c NULL si es raíz).
    lkptr< Bin_Tree_Node <E> > m_left;   ///< Hijo izquierdo del árbol (\c NULL si es hoja).
    lkptr< Bin_Tree_Node <E> > m_right;///< Hijo derecho del árbol (\c NULL si es hoja).
        
private:
    /// Constructor a partir de un valor específico.
    Bin_Tree_Node( const value_type& d ) : m_dato( d ), m_padre(0), m_left(0), m_right(0) 
                                        {}
public: // debe ser público para que otros módulos puedan destruir árboles ya construidos.
    ~Bin_Tree_Node() {} ///< Destructor.
}; // Bin_Tree_Node

/** Los métodos para trabajar con árboles binarios regresan "referencias" que son sub-árboles.
    - Un sub-árbol es parte del árbol, por lo que al modificar los valores del
      sub-árbol también el árbol original queda cambiado.
    - Para evitar este tipo de modificación indirecta, es necesario trabajar
      con una "copia profunda" del árbol orignal, la que se puede obtener con
      \c Bin_Tree::copyDeep().
    - Aún si el árbol original es eliminado, el sub-árbol continúa existiendo.
    - Debido a que los árboles y sub-árboles son referencias, en C++ es necesario mantener
      internamente "enlaces de referencia".
*/
template <class E>
class Bin_Tree {
private:
    lkptr< Bin_Tree_Node<E> > m_root; ///< Un árbol "es" el puntero al nodo raíz.
        
public:
    typedef E value_type; ///< Nombre estándar del tipo de elemento contenido

/// \name Constructores y destructor
//@{
public:
    Bin_Tree() : m_root(0) {} ///< Constructor de vector: el árbol queda vacío.
    Bin_Tree(const Bin_Tree& other) : m_root(0) { m_root = other.m_root; }
    Bin_Tree(const value_type & d);
    ~Bin_Tree();
private:
    /// Constructor a partir de un nodo.
    Bin_Tree( lkptr< Bin_Tree_Node<E> >& other ) : m_root(0) { m_root = other; }
//@}

/// \name Operaciones básicas
//@{
public:
    bool     isEmpty() const { return (m_root == 0); } ///< Retorna \c "true" si el sub-árbol está vacío
    unsigned count() const ;
    unsigned countChildren() const ;
    /// Usa \c count() para retornar la cantidad de valores almacenados en el sub-árbol
    unsigned size () const { return count(); }
    // /// Usa \c T.ok() para verificar la invariante de \c Bin_Tree
    // template <class E> friend bool check_ok(const Bin_Tree<E>& T) { return T.ok(); }
    bool     ok() const { return true; }
//@}

/// \name Operaciones de borrado
//@{
public:
    /** Elimina el árbol y sus descendientes.
        - \c T.left().erase(); // No cambia "T" porque el que cambia es "T.left()"
        -  \c T.makeLeftChild( Bin_Tree<E>() ); // borra el hijo izquierdo
        -  \c T.makeRightChild( Bin_Tree<E>() ); // borra el hijo derecho
        \par Complejidad:
             O( \c count()  ) ==> tiempo <br>
             O( \c height() ) ==> espacio.
        \see http://www.di-mare.com/adolfo/binder/c04.htm#sc03
    */
    void erase() { m_root.release(); }
//@}

/// \name Operaciones de copiado
//@{
public:
    /// Sinónimo de \c this->copy(o) (pero retorna \c *this).
    Bin_Tree& operator= ( const Bin_Tree & other ) { m_root = other.m_root; return *this; }
    void copy ( const Bin_Tree & other ) { m_root = other.m_root; }
    Bin_Tree& copyDeep( const Bin_Tree &other );
    /// Usa \c changeRoot() para sustituir por "d" el valor almacenado en la raíz del árbol.
    Bin_Tree& operator=( const value_type & d) { changeRoot(d); return *this; }
    void swap (Bin_Tree &other);
    void move (Bin_Tree &other);
//@}

/// \name Métodos para cambiar los valores almacenados en el árbol
//@{
public:
    void changeRoot(  const value_type &d );
    void changeChild( unsigned n, const value_type &d );
    void makeLeftChild(  Bin_Tree & T );
    void makeRightChild( Bin_Tree & T );
//@}

/// \name Operaciones para usar los valores almacenados
//@{
public:
    /// Valor almacenado en la raíz del sub-árbol
    value_type& dato        () const { return  m_root->m_dato;   }
    /// Valor almacenado en la raíz del sub-árbol
    value_type& operator *  () const { return  m_root->m_dato;   }
    /// Puntero al valor almacenado en la raíz del sub-árbol
    value_type* operator -> () const { return &(m_root->m_dato); }
//@}

/// \name Operaciones de comparación
//@{
public:
    /// ¿¿¿ (p == q) ???
    template <class E> friend bool operator == (const Bin_Tree<E> &p, const Bin_Tree<E> &q);
    /// ¿¿¿ (p != q) ???
    template <class E> friend bool operator != (const Bin_Tree<E> &p, const Bin_Tree<E> &q);
    bool equals( const Bin_Tree & o ) const { return (*this)==o; } ///< ¿¿¿ (*this==o) ???
    /// Retorna \c true si \c "o" comparte la raíz con \c "*this"
    bool same( const Bin_Tree & o ) const { return m_root == o.m_root; }
//@}

/// \name Métodos para recorrer el árbol
//@{
public:
    Bin_Tree root() const { return Bin_Tree( m_root ); } ///< Raíz del sub-árbol
    /// Acceso al padre.
    /// - Si el sub-árbol no tiene padre retorna el árbol vacío.
    Bin_Tree padre() const {
        if ( m_root == 0 ) { return Bin_Tree(); }
        else { return Bin_Tree( m_root->m_padre ); }
    }
    /// Acceso al hijo izquierdo.
    /// - Si el sub-árbol no tiene hijo izquierdo retorna el árbol vacío.
    Bin_Tree left() const {
        if ( m_root == 0 ) { return Bin_Tree(); }
    //  else if ( m_root->m_left == 0) { return Bin_Tree(); }
        else { return Bin_Tree( m_root->m_left ); }
    }
    /// Acceso al hijo derecho.
    /// - Si el sub-árbol no tiene hijo derecho retorna el árbol vacío.
    Bin_Tree right() const {
        if ( m_root == 0 ) { return Bin_Tree(); }
    //  else if ( m_root->m_right == 0) { return Bin_Tree(); }
        else { return Bin_Tree(m_root->m_right); }
    }
    /// Acceso al i-ésimo hijo del árbol.
    /// - Si el sub-árbol no tiene es hijo retorna el árbol vacío.
    /// - <code>( i == 0 )</code> ==> Hijo izquierdo.
    /// - <code>( i == 1 )</code> ==> Hijo derecho.
    Bin_Tree child(int i) const {
        if ( m_root == 0 ) { return Bin_Tree(); }
        else if (i==0)     { return Bin_Tree(m_left); }
        else if (i==1)     { return Bin_Tree(m_right); }
        else               { return Bin_Tree(); }
    }
//@}

/// \name Propiedades del árbol
//@{
public:
    /// Retorna \c "true" si el árbol es una hoja.
    /// - Retorna \c "false" para un árbol vacío.
    bool isLeaf() const {
        return ( m_root == 0 ? false : (m_root->m_left == 0) && (m_root->m_right == 0) );
    }
    /// Retorna \c "true" si el árbol no tiene padre.
    /// - Retorna \c "false" para un árbol vacío.
    bool isRoot() const { return ( m_root == 0 ? false : m_root->m_padre == 0 ); }
    /// Cantidad de referencias de la raíz del árbol
    unsigned refs() const { return (m_root==0 ? 0 : m_root.refs()); }
//@}
}; // Bin_Tree

/** \fn template <class E> inline Bin_Tree<E>::Bin_Tree(const Bin_Tree& o)
    \brief Constructor de copia desde otro árbol (copia superficial).
    - Como un sub-árbol en realidad es una referencia, este método
      no hace la copia completa [profunda] del árbol.
      \par Complejidad:
          O( \c 1 ).
*/

/**  Destructor.
    \par Complejidad:
         O( \c count()  ) ==> tiempo <br>
         O( \c height() ) ==> espacio.
    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc04
*/
template <class E>
Bin_Tree<E>::~Bin_Tree() { // lkptr<> destruye el valor si hace falta
    m_root.release( );     // se auto-mata
}

/// Constructor a partir de un valor.
template <class E>
inline Bin_Tree<E>::Bin_Tree(const E & d) {
    m_root.reset( new Bin_Tree_Node<E>(d) );
}

/** \fn template <class E> void Bin_Tree<E>::copy (const Bin_Tree &o)
    \brief Copia superficial desde \c "o".
    - El valor anterior de \c "*this" se pierde.
    \par Complejidad:
         O( \c 1 ).
    \returns *this.
    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc05
*/

/** Intercambia los valores de \c "*this" y \c "o".
    - Debido a que algunos métodos retornan copias del valor de \c "*this" en
      lugar de una referencia, como ocurre con \c Bin_Tree::child(), a veces
      \c swap() no tiene el resultado esperado por el programador.
    - Por ejemplo, si se invoca <code> T.child(i). swap( T.child(j) ) </code>
      el resultado no es intercambiar los hijos, sino más bien intercambiar
      los valores de los sub-árboles temporales \c T.child(i) y \c T.child(j).
      La forma correcta de intercambiar hijos es usar \c makeLeftChild() y/o
      \c makeRightChild().

    \par Complejidad:
         O( \c 1 ).
    \returns *this.

    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc08
*/
template <class E>
void Bin_Tree<E>::swap (Bin_Tree &other) {
    if (this == &other) {
        return;          // evita auto-copia
    }
    Bin_Tree<E> TMP;     // tmp está vacío
    TMP.move( *this );   // *this queda vacío
    this->move( other ); // ahora other está vacío
    other.move( TMP );   // ahora TMP vuelve a quedar vacío
    return;
    #if 0
        // Esta implementación no sirve porque no cambia m_padre en los hijos
        lkptr< Bin_Tree_Node<E> > tmp ( m_root );
        m_root = other.m_root;
        other.m_root = tmp;
    #endif
}

/** Traslada a \c "*this" el valor de \c "other".
    - El valor anterior de \c "*this" se pierde.
    - El nuevo valor de \c "*this" es el que \c "other" tuvo.
    - \c "other" queda en el estado en que lo dejaría \c other.erase().
    - Si \c "*this" es \c "other" entonces su valor no cambia.
    - En general, después de esta operación casi
      nunca ocurre que \c this->equal(other) es \c "true".
    \par Complejidad:
         O( \c count() )
    \returns *this.
    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc07
*/
template <class E>
void Bin_Tree<E>::move (Bin_Tree &other) {
    if (this == &other) {
        return; // evita auto-copia
    }
    m_root = other.m_root;
    if ( m_root->m_left != 0 ) {
        if ( m_root->m_left->m_padre == other.m_root ) {
            m_root->m_left->m_padre = m_root; // reconecta el hijo izquierdo
        }
    }
    if ( m_root->m_right != 0 ) {
        if ( m_root->m_right->m_padre == other.m_root ) {
            m_root->m_right->m_padre = m_root;
        }
    }
    other.m_root.release();
    return;
    // Es O( count() ) porque a veces opertor=() borra "*this" completo
}
/** Retorna la cantidad de valores almacenados en el sub-árbol.
    - Calcula el número de sub-árboles no vacíos del árbol.
    \par Complejidad:
         O( \c count() ) ==> tiempo <br>
         O( \c height() ) ==> espacio.
    \see http://www.di-mare.com/adolfo/binder/c05.htm#sc03 */
template <class E>
unsigned Bin_Tree<E>::count() const {
    if (m_root == 0) {
        return 0;
    } else {
        return 1 + ( left().count() + right().count() );
    }
}

/// Retorna la cantidad de hijos del árbol.
/// \par Complejidad:
///      O( \c 1 )
template <class E>
unsigned Bin_Tree<E>::countChildren() const {
    if (m_root == 0) {
        return 0;
    }
    int n = 0;
    if ( !left().isEmpty() ) {
        ++n;
    }
    if ( !right().isEmpty() ) {
        ++n;
    }
    return n;
}

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

/// Sustituye por \c "d" el valor almacenado en la raíz del árbol.
/// - Si el árbol está vacío, le agrega su raíz.
template <class E>
void Bin_Tree<E>::changeRoot(const value_type & d) {
    if (m_root == 0) { // como el árbol está vacío hay que agregarle la raíz
        m_root.reset ( new Bin_Tree_Node<E>(d) ); // crea el nodo raíz
    } else { // como no hay más referencias....
        m_root->m_dato = d; // ... cambia el valor directamente
    }
}

/** Sustituye por \c "d" el valor almacenado en el hijo número \c "n" del árbol.
    - Si no existe el hijo número \c "n", lo agrega como una hoja con valor \c "d".
    - Si ya existe el hijo número \c "n", le sustituye su valor por \c "d".
    - Si \c "n" no es uno de {0,1} no hace nada.
*/
template <class E>
void Bin_Tree<E>::changeChild(unsigned n, const value_type &d) {
    if (m_root == 0) { // ignora árboles vacíos
        return;
    }
    else if ( n==0 ) {
        if (m_root->m_left == 0) {
            m_root->m_left.reset ( new Bin_Tree_Node<E>(d) ); // crea el nodo raíz
            m_root->m_left->m_padre = m_root; // conecta el hijo hacia su padre
        }
        else {
            m_root->m_left->m_dato =  d; // cambia el valor almacenado
        }
        return;
    }
    else if ( n==1 ) {
        if (m_root->m_right.get() == 0) {
            m_root->m_right.reset ( new Bin_Tree_Node<E>(d) ); // crea el nodo raíz
            m_root->m_right->m_padre = m_root; // conecta el hijo hacia su padre
        }
        else {
            m_root->m_right->m_dato =  d; // cambia el valor almacenado
        }
        return;
    }
    else {
        return;
    }
}

/** Pone al árbol \c "T" como sub-árbol izquierdo de \c "*this".
    - Elimina el sub-árbol izquierdo de \c "*this" si \c "T" está vacío.
    \pre <code> ! isEmpty() </code>
*/
template <class E>
void Bin_Tree<E>::makeLeftChild( Bin_Tree & T ) {
    m_root->m_left = T.m_root;
    if (! T.isEmpty() ) {
        T.m_root->m_padre = this->m_root;
    }
}

/** Pone al árbol \c "T" como sub-árbol derecho de \c "*this".
    - Elimina el sub-árbol derecho de \c "*this" si \c "T" está vacío.
    \pre <code> ! isEmpty() </code>
*/
template <class E>
void Bin_Tree<E>::makeRightChild( Bin_Tree & T ) {
    m_root->m_right = T.m_root;
    if (! T.isEmpty() ) {
        T.m_root->m_padre = this->m_root;
    }
}

/** 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> */
template <class E>
unsigned depth(  Bin_Tree<E> & T ) {
    if ( T.isEmpty() ) {
        return 0;
    }
    unsigned n = 0;
    Bin_Tree<E> F = T;
    do {
        F = F.padre();
        ++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 height0( Bin_Tree<E> & T, unsigned &max, unsigned actual) {
    if ( T.isEmpty() ) {
        if (max < actual) {
            max = actual; // se deja el más grande de los 2
        }
        return;
    } else {
        height0(T.left(),  max, actual+1);
        height0(T.right(), max, actual+1);
        return;
    }
}

/** Retorna la altura de \c "T".
  - 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
                                     [ 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 unsigned height( Bin_Tree<E> & T ) {
    unsigned actual,  max;
    max    = 0;
    actual = 0;
    height0( T, max, actual );
    max = ( max > 0 ? max-1 : 0 );
    return max;
}

/** Copia profunda de \c "other".
    - Copia todo el valor de \c "other" sobre \c "*this", de forma que el nuevo valor de
      \c "*this" sea un duplicado exacto del valor de \c "other".
    - El valor anterior de \c "*this" 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 "*this" es \c "other" entonces su valor no cambia.
    - Después de esta operación siempre ocurre que <code> *this == other </code>.
    \par Complejidad:
         O( \c count() ) + O( \c other.count() ).
    \returns \c *this.
    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc05
*/
template <class E>
Bin_Tree<E>& Bin_Tree<E>::copyDeep( const Bin_Tree &other ) {
    if ( this == &other ) {
        return *this; // evita auto-copia
    }
    else if ( same(other) ) {
        m_root.release(); // deja el valor en el otro
    }
    if ( other.isEmpty() ) {
        m_root.release(); // llegó al final de la recursión
    }
    else {
        // copia el valor de la raíz
        if (m_root == 0) {
            m_root.reset( new Bin_Tree_Node<E>( other.m_root->m_dato ) );
        }
        else { // le cae encima al valor actual
            m_root->m_dato = other.m_root->m_dato;
        }

        if ( other.left().isEmpty() ) { // copia el sub-árbol izquierdo
            m_root->m_left.release(); // suelto a mi hijo
        }
        else {
            Bin_Tree T_left;
            T_left.copyDeep(  other.left() );
            m_root->m_left = T_left.m_root;
            T_left.m_root->m_padre = m_root;
        }

        if ( other.right().isEmpty() ) { // copia el sub-árbol derecho
            m_root->m_right.release(); // suelto a mi hijo
        }
        else {
            Bin_Tree T_right;
            T_right.copyDeep( other.right() );
            m_root->m_right = T_right.m_root;
            T_right.m_root->m_padre = m_root;
        }
    }
    return *this;
}


// Agrega una copia de \c "val" al árbol binario ordenado \c "T".
template <class E>
void orderedInsert( Bin_Tree<E> & T , const E& val ) {
    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.dato() ) {
            if ( Root.left().isEmpty() ) {
                Root.makeLeftChild( Child );
                return;
            }
            else {
                Root = Root.left();
            }
        }
        else if ( val > Root.dato() ) {
            if ( Root.right().isEmpty() ) {
                Root.makeRightChild( Child );
                return;
            }
            else {
                Root = Root.right();
            }
        }
        else {
            return; // no inserta duplicados
        }
        }
}





// Agrega una copia de \c "val" al árbol binario ordenado \c "T".
template <class E>
void IPD_cout( const Bin_Tree<E>& T ) {
    if ( T.isEmpty() ) {
        return; // porque ya terminó
    }
    IPD_cout( T.left() );
    std::cout << " " << T.dato();
    IPD_cout( T.right() );
}

template <class E>
bool Comp(Bin_Tree<E>& p, 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.dato() == q.dato()) ) {
        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ó nodos diferentes
}

template <class E>
void copyDeep( Bin_Tree<E>& T, const Bin_Tree<E> &other ) {
    if ( &T == &other ) {
        return; // evita auto-copia
    }
    else if ( T.same(other) ) {
        T.erase(); // deja el valor en el otro
    }
    T.changeRoot( other.dato() ); // nueva raíz del árbol
    if ( other.left().isEmpty() ) {
        T.makeLeftChild( Bin_Tree<E>() ); // borra el hijo izquierdo
        // T.left().erase(); no funciona porque T.left() es "otro" árbol
    }
    else {
        Bin_Tree<E> Child; // árbol vacío
        copyDeep( Child, other.left() );
        T.makeLeftChild( Child );
    }
    if ( other.right().isEmpty() ) {
        T.makeRightChild( Bin_Tree<E>() );
    }
    else {
        Bin_Tree<E> Child;
        copyDeep( Child, other.right() );
        T.makeRightChild( Child );
    }
}

#endif  // Bin_Tree_h

// EOF: Bin_Tree.h

---