Tree_L.h

Ir a la documentación de este archivo.

// Tree_L.h (c) 2006 adolfo@di-mare.com

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

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

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

#ifndef Tree_L_h
#define Tree_L_h

#ifndef NDEBUG // ==> Overview of File Translation ==> C++
    #define USE_v_Alive
    #undef  USE_v_Alive
#endif

#include <cassert> // para usar assert()

/// Arboles de adolfo@di-mare.com cuyos nodos contienen un puntero izquierdo al hijo y uno derecho al hermano o padre
namespace TL {

template <class E> class Tree;
template <class E> bool check_ok( const E & );
template <class E> bool check_ok( const Tree<E>& T); // declaration hacia adelante

/// Nodos almacenados en el árbol.
template <class E>
class Tree_Node {
public:
    friend class Tree<E>;
    typedef E value_type; ///< Nombre estándar del tipo de elemento contenido
private:
    Tree_Node( const value_type& d ) : m_data( d ), m_refCount(1) {} ///< Constructor de vector
    static Tree_Node<E>* Get_New(const value_type& d);
    unsigned Abs_n_child() const;
private:
    value_type  m_data; ///< Valor almacenado en el nodo
    unsigned    m_refCount; ///< Cantidad de punteros hacia mi
    int         m_n_child; ///< Soy el el hijo número <code> "(m_n_child - 1)" </code> de mi padre
    Tree_Node<E> * m_left_child; ///< Puntero al nodo hijo más izquierdo
    Tree_Node<E> * m_right_brother; ///< Puntero al nodo hermano o al padre
private:
    #ifdef USE_v_Alive // ==> NDEBUG ==> Overview of File Translation ==> C++
        static const unsigned N_Alive = 333; ///< Cantidad máxima posible de punteros en uso
        static Tree_Node<E> *   m_v_Alive[N_Alive]; ///< Punteros en uso
        static unsigned m_n_Alive; ///< Cantidad de punteros en uso
    #endif
}; // Tree_Node

/** Los métodos para trabajar con árboles 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 Tree::Copy_Deep().
    - 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 "cuentas de referencia" que impiden que métodos como \c Father() o \c Root()
      sean métodos <code>const</code>.
    - Muchos métodos retornan referencias \c Tree& porque es más eficiente, pues cada
      vez que un \c Tree es copiado hay que actualizar la "cuenta de referencia" de
      la raíz del sub-árbol.
*/
template <class E>
class Tree {
public:
    typedef E value_type; ///< Nombre estándar del tipo de elemento contenido
/// \name Constructores y destructor
//@{
public:
    Tree() : m_root(0) {} ///< Constructor de vector
    Tree(const Tree& o);
    Tree(const value_type & d);
    ~Tree();
private:
    /// Constructor a partir de un nodo
    Tree(Tree_Node<E>* p) : m_root(p) { if (p!=0) { p->m_refCount++; } }
    /// Truco para usar el constructor que no verifica <code> (p != 0) </code>
    typedef void NOT_null_pointer;
    /// Constructor a partir de un nodo [ requiere <code> p != 0 </code> ]
    Tree(NOT_null_pointer* p) : m_root( (Tree_Node<E>*)p) { // assert( p != 0 );
        ((Tree_Node<E>*)p)->m_refCount++; }
//@}

/// \name Operaciones básicas
//@{
public:
    bool     Empty() const { return (m_root == 0); } ///< Retorna \c "true" si el sub-árbol está vacío
    unsigned Count() const ;
    unsigned Count_Children() const ;
    unsigned Size () const { return Count(); } ///< Usa \c Count() para retornar la cantidad de valores almacenados en el sub-árbol
    friend bool check_ok<E>(const Tree<E>& T);
    bool        Ok() { return check_ok(*this); } ///< Usa \c check_ok(Tree& T) para verificar la invariante de \c Tree
//@}

/// \name Operaciones de borrado
//@{
public:
    void Erase();
    void Erase_Son(unsigned n) { Tree_Node<E>*p; Erase_Son_Prev(n+1,p /*,p*/); }
private:
    void Erase_Son_Prev(unsigned n, Tree_Node<E>*& /*, Tree_Node<E>*& */);
//@}

/// \name Operaciones de copiado
//@{
public:
    Tree& operator= (const Tree &o) { return Copy(o); } ///< Sinónimo de \c this->Copy(o)
    Tree& Copy (const Tree &o);
    Tree& Move (Tree &o);
    Tree& Swap (Tree &o);
    Tree& Copy_Deep( const Tree &o );
    /// Usa \c Change_Root() para sustituir por "d" el valor almacenado en la raíz del árbol
    Tree& operator=( const value_type & d) { Change_Root(d); return *this; }
//@}

/// \name Métodos para cambiar los valores almacenados en el árbol
//@{
public:
    Tree Change_Root(const value_type &d);
    Tree Change_Child( unsigned n, const value_type &d );
    Tree Change_Left_Sibling_Inmediate( const value_type &d );
    Tree Change_Right_Sibling_Inmediate( const value_type &d );
    Tree Graft( unsigned n, Tree &o );
//@}

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

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

/// \name Métodos para recorrer el árbol
//@{
public:
    Tree Root() const { return Tree( m_root ); } ///< Raíz del sub-árbol
    Tree Father() const ;
    Tree Child(unsigned n) const;
    Tree Left() const;
    Tree Right() const;
    Tree Leftmost() const;
    Tree Rightmost() const;
    Tree Sibling(int n) const;
    Tree Left_Sibling() const;
    Tree Right_Sibling() const;
    Tree Previous_Sibling() const { return Left_Sibling(); } ///<  Sinónimo de \c Left_Sibling()
    Tree Prev_Sibling() const { return Left_Sibling(); } ///<  Sinónimo de \c Left_Sibling()
    Tree Next_Sibling() const { return Right_Sibling(); } ///<  Sinónimo de \c Right_Sibling()
    Tree Right_Sibling_Inmediate() const;
    Tree Left_Sibling_Inmediate() const;
//@}

/// \name Propiedades del árbol
//@{
public:
    /// Retorna \c "n" si \c "*this" es el n-ésimo hijo de su padre, si no retorna \c 0 (cero)
    unsigned Child_Number() const { return ( m_root==0 ? 0 : m_root->Abs_n_child() - 1); }
    /// Retorna \c "n" si el hijo más izquierdo de \c "*this" es el n-ésimo hijo, si no retorna \c 0 (cero)
    unsigned Leftmost_N() const { return Leftmost().Child_Number(); }
    /// Retorna \c "n" si el hijo más derecho de \c "*this" es el n-ésimo hijo, si no retorna \c 0 (cero)
    unsigned Rightmost_N() const { return Rightmost().Child_Number(); }
    /// Retorna \c "true" si el árbol es una hoja
    bool Is_Leaf() const { return (m_root != 0) && (m_root->m_left_child != 0); }
    /// Retorna \c "true" si el árbol no tiene padre
    bool Is_Root() const { return (m_root != 0) && (m_root->m_right_brother == 0); }
    /// Cantidad de referencias de la raíz del árbol
    unsigned use_count() const { return (m_root==0 ? 0 : m_root->m_refCount); }
//@}

/// \name Funciones para manipular valores a bajo nivel
//@{
private:
    /// Convierte el puntero al nodo en un referencia a \c Tree
    static Tree& CastTo_Sub_Tree_Ref ( Tree_Node<E> * &p )
    { return (Tree&) *( reinterpret_cast<Tree*> (&p)); }
//@}

/// \name Funciones recursivas que realizan el trabajo sobre nodos
//@{
private:
    static void Erase0(Tree_Node<E> * p);
    static bool Comp0(const Tree_Node<E> *p, const Tree_Node<E> *q);
    static void Count0(const Tree_Node<E> * p, unsigned & n);
    static Tree_Node<E>* Copy_Deep0(const Tree_Node<E> * p);
//@}
private:
    Tree_Node<E> * m_root; ///< Un árbol "es" el puntero al nodo raíz
}; // Tree

#ifdef USE_v_Alive
    unsigned Tree::Tree_Node<E>::m_n_Alive = 0; // Hay que "repetir" estos nombres acá para que el ...
    Tree::Tree_Node<E>* Tree::Tree_Node<E>::m_v_Alive[Tree::Tree_Node<E>::N_Alive]; // ... compilador les asigne memoria
#endif

/** Crea un nuevo nodo y lo inicializa con \c "d"

    - Para mejorar la eficiencia, no incializa los punteros del nodo.
    - Si la macro \c USE_v_Alive de compilación existe, también agrega el nuevo
      nodo al contenedor global \c Tree::m_v_Alive[], de manera que es posible
      saber si un puntero a un nodo está o no en uso.
    - En realidad sobra usar este método, pero la utilidad de usarlo es
      que es posible examinar \c Tree::m_v_Alive[] para saber si los métodos
      de árbol están correctamente implementados.
*/
template <class E>
inline Tree_Node<E> * Tree_Node<E>::Get_New( const E& d) {
    Tree_Node<E>* p = new Tree_Node(d);
    #ifdef USE_v_Alive
        m_v_Alive[m_n_Alive] = p;
        m_n_Alive++;
    #endif
    return p;
}

///  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.
template <class E>
inline Tree<E>::Tree(const Tree& o) {
    if (o.m_root != 0) {
        o.m_root->m_refCount++; // una referencia más porque "o" y "*this" ...
    }
    m_root =  o.m_root; // ... ahora comparten la raíz
}

/**  Destructor.
    \par Complejidad:
         O( \c Count() )

    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc04 */
template <class E>
Tree<E>::~Tree() {
    if (m_root != 0) {
        if (m_root->m_refCount == 1) {
            Erase0(m_root);
        } else {
            m_root->m_refCount--;
        }
    }
}

/// Constructor a partir de un valor
template <class E>
inline Tree<E>::Tree(const E & d) {
    m_root = Tree_Node<E>::Get_New(d);
    m_root->m_n_child = -1;
    m_root->m_left_child = 0;
    m_root->m_right_brother = 0;
}

/** Copia superficial desde \c "o".
    - El valor anterior de \c "*this" se pierde

    \par Complejidad:
         O( \c Count() )

    \returns *this

    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc05 */
template <class E>
Tree<E>& Tree<E>::Copy( const Tree &o ) {
    if (m_root != o.m_root) { // evita auto-borrado
        if (m_root != 0) {
            if ( m_root->m_refCount == 1 ) { // como es el último...
                Erase0(m_root); // ...lo mata
            } else {
                m_root->m_refCount--;
            }
        }
        m_root =  o.m_root; // comparte la raíz
        if (o.m_root != 0) {
            o.m_root->m_refCount++; // una referencia más
        }
    }
    return *this;
}

/** Traslada el valor de \c "o" a \c "*this".
  - El valor anterior de \c "*this" se pierde
  - El nuevo valor de \c "*this" es el que \c "o" tuvo
  - \c "o" queda en el estado en que lo dejaría \c Erase()
  - Si \c "*this" es \c "o" entonces su valor no cambia
  - En general, después de esta operación casi
    nunca ocurre que <code> (*this == o) </code>

    \par Complejidad:
         O( \c Count() )

    \returns \c *this

    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc07 */
template <class E>
Tree<E>& Tree<E>::Move( Tree &o ) {
    if (m_root == o.m_root) { // evita auto-borrado
        if (m_root != 0) {
            if ( m_root->m_refCount == 1 ) { // como es el último...
                Erase0(m_root); // ...lo mata
            } else {
                m_root->m_refCount--;
            }
        }
        m_root = o.m_root; // se roba los hijos
        o.m_root = 0; // anula al dador
    }
    return *this;
}

/** 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 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 Graft().

      \par Complejidad:
         O( \c 1 )

    \returns *this

    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc08 */
template <class E>
inline Tree<E>& Tree<E>::Swap( Tree &o ) {
    Tree_Node<E> * tmp = m_root;
    m_root = o.m_root;
    o.m_root = tmp;
    return *this;
}

/** Acceso al padre.
    - Si el sub-árbol no tiene padre retorna el árbol vacío.

    \par Complejidad:
         O( <code> Father().Count_Children() </code> ) */
template <class E>
Tree<E> Tree<E>::Father() const {
    if (m_root == 0) {
        return Tree( );
    }

    Tree_Node<E>* p = m_root; // soy el primer hijo de mi padre
    while (p->m_n_child > 0) {
        p = p->m_right_brother; // se brinca los que no tienen el puntero al padre
    }
    return Tree( p->m_right_brother );
    // para la raíz siempre ocurre que [m_root->m_right_brother == 0] por lo que
    // Tree( p->m_right_brother ) produce un árbol vacío
}

/** Acceso al \c "n"-ésimo hijo.
    - Si el sub-árbol no tiene un hijo número \c "n" retorna el sub-árbol vacío.

    \par Complejidad:
         O( <code> Father().Count_Children() </code> ) */
template <class E>
Tree<E> Tree<E>::Child( unsigned n ) const {
    if (m_root == 0) {
        return Tree( );
    }

    Tree_Node<E>* child = m_root->m_left_child; // soy el primer hijo de mi padre
    if (child == 0) {
        return Tree( );
    }

    n++; // lo incrementa para evitar incrementar "m_n_child" para cada hijo de "m_root"

    for (;;) {
        if (child->m_n_child <= 0) { // es el último hijo
            if ( unsigned(- child->m_n_child) == n ) {
                return Tree( (NOT_null_pointer*) child  );
            } else {
                return Tree( );
            }
        } else {
            if ( child->m_n_child == n ) {
                return Tree( (NOT_null_pointer*) child );
            } else if ( unsigned(child->m_n_child) < n) {
                child = child->m_right_brother;
            } else { // assert( unsigned(child->m_n_child) > n );
                return Tree( );
            }
        }
    }
}

/** \typedef Tree::NOT_null_pointer
    \brief Truco para evitar comparar con \c 0 ( \c nil )
    al usar \c Tree::Tree_Node<E>* para construir \c Tree().

    Al implementar cada uno de los métodos de \c Tree con frecuencia ocurre
    que es posible saber que el sub-árbol retornado no está vacío. En estos casos, conviene
    usar un contructor que no verifique si la raíz del árbol es nula.

    Esta clase se usa como una marca para que se ejecute el contructor
    <code> Tree::Tree(NOT_null_pointer* p) </code>
    que no verifica la nulidad de \c "m_root"; esta es una micro-eficiencia, pero aquí sirve
    para mostrar un truco que es muy usado en C++ para aumentar la eficiencia de los
    programas, pues le permite al programado usar la sobrecarga de operadores para evitar
    repetir verificaciones innecesarias.

    \see http://www.di-mare.com/adolfo/binder/c01.htm#k1-micro-eficiencia
*/

/** Sub-árbol izquierdo [en un árbol binario].
    - Sinónimo de \c Child(0).
    \par Complejidad:
         O( \c 1 ) */
template <class E>
inline Tree<E> Tree<E>::Left() const {
    if (m_root == 0) {
        return Tree( );
    } else if ( -1 ==m_root->m_left_child->m_n_child ||
                 1 ==m_root->m_left_child->m_n_child ) {
        return Tree( (NOT_null_pointer*) m_root->m_left_child );
    }
    return Tree( );
}

/** Sub-árbol derecho [en un árbol binario].
    - Sinónimo de \c Child(1).

    \par Complejidad:
         O( \c 1 ) */
template <class E>
Tree<E> Tree<E>::Right() const {
    if (m_root == 0) {
        return Tree( );
    } else if ( 0 == m_root->m_left_child ) { // no hay hijos
        return Tree( );
    } else if ( -1 ==m_root->m_left_child->m_n_child ) {
        return Tree( ); // sólo está el hijo izquierdo
    } else if ( 1 ==m_root->m_left_child->m_n_child ) {
        if ( -2 == m_root->m_left_child->m_right_brother->m_n_child  ||
              2 == m_root->m_left_child->m_right_brother->m_n_child ) {
            return Tree( (NOT_null_pointer*) m_root->m_left_child->m_right_brother  );
        }
    } else if ( 2 == m_root->m_left_child->m_n_child || -2 == m_root->m_left_child->m_n_child ) {
        return Tree( (NOT_null_pointer*) m_root->m_left_child );
    }
    return Tree( ); // uso 1-2 en lugar de 0-1 porque "m_n_child" contiene "uno más"
}

/** Obtiene el hermano no vacío anterior, que está hacia la izquierda.
    - Si no existe un hermano no vacío hacia la izquierda, retorna un sub-árbol vacío.
    - Si <code>n == Child_Number()</code> no necesariamente ocurrirá que
      <code> (n-1)== Left_Sibling().Child_Number()</code>
      pues los anteriores hijos de \c Father() pueden ser sub-árboles vacíos, como ocurre si
      un árbol binario tiene hijo derecho pero no tiene hijo izquierdo.
    - Este método usualmente se usa junto con \c Rightmost()

    \par Complejidad:
         O( <code> Father().Count_Children() </code> ) */
template <class E>
Tree<E> Tree<E>::Left_Sibling() const {
    if (m_root == 0)  {
        return Tree( );
    }

    unsigned n_child = m_root->Abs_n_child()-1; // assert( n_child >= 0 );
    if ( n_child <= 0 ) { // no puede haber un hijo anterior...
        return Tree( ); // huye porque no existen hijos antes del primero
    }
    #ifdef ESTO_SOBRA_en_Left_Sibling
        if (m_root->m_right_brother == 0)  { // sólo la raíz tiene en blanco "m_right_brother"
            return Tree( ); // la raíz no tiene hermanos
        }
        // Para el nodo raíz de un árbol [T] el campo [T.m_root->m_right_brother == 0] es nulo
        // - Afortunadamente, como [T.m_root->m_n_child == -1], el if(){} anterior retorna
        //   el sub-árbol vacío para el nodo raíz del árbol [T].
    #endif

    Tree_Node<E>* brother = m_root; // camina sobre los hermanos hasta llegar al padre
    while (brother->m_n_child > 0) {
        brother = brother->m_right_brother; // se brinca los que no tienen el puntero al padre
    }
    Tree_Node<E>* father = brother->m_right_brother;
    // assert( ! Father().Empty() && Father().Same( Tree( brother ) ) );

    brother = father->m_left_child; // hijo más izquierdo de Father()
    if ( m_root == brother ) {
        return Tree( ); // ya "m_root" era el hijo más izquierdo
    }
    while ( m_root != brother->m_right_brother ) {
        brother = brother->m_right_brother;
    }
    // assert( m_root == brother->m_right_brother );
    return Tree( brother );
}

/** Obtiene el hermano no vacío siguiente, que está hacia la derecha.
    - Si no existe un hermano hacia la derecha, retorna un sub-árbol vacío.
    - Si <code>n == Child_Number()</code> no necesariamente ocurrirá que
      <code>(n+1) == Right_Sibling().Child_Number()</code>
      pues los siguientes hijos de \c Father() pueden ser sub-árboles vacíos, como ocurre si
      un árbol binario tiene hijo izquierdo pero no tiene hijo derecho.
    - Este método usualmente se usa junto con \c Leftmost()

    \par Complejidad:
         O( \c 1 ) */
template <class E>
Tree<E> Tree<E>::Right_Sibling() const {
    if (m_root == 0)  {
        return Tree( );
    } if (m_root->m_n_child < 0) { // es el último hijo
        return Tree( ); // ==> ya no hay dónde más buscar
    } else {
        return Tree( m_root->m_right_brother );
        // sólo la raíz tiene "m_right_brother" en blanco (puntero nulo);
        // en ese caso se retorna el árbol vacío.
    }
}

/** Obtiene el hermano que está inmediatamente hacia la izquierda.
    - Este método es equivalente a invocar \c Sibling( -1 )
    - Si no existe un hermano hacia la derecha, retorna un sub-árbol vacío.

    \par Complejidad:
         O( <code> Father().Count_Children() </code> ) */
template <class E>
inline Tree<E> Tree<E>::Left_Sibling_Inmediate() const {
    return Sibling( -1 );
}

/** Obtiene el hermano que está inmediatamente hacia la derecha.
    - Este método es equivalente a invocar \c Sibling( +1 )
    - Si no existe ese hermano hacia la derecha, retorna un sub-árbol vacío.

    \par Complejidad:
         O( \c 1 ) */
template <class E>
Tree<E> Tree<E>::Right_Sibling_Inmediate() const {
//  return Sibling( +1 );
    if (m_root == 0)  {
        return Tree( );
    }
    if (m_root->m_n_child <= 0) { // es el último hijo
        return Tree( ); // ya no hay hermanos a la derecha
    }
    // assert( m_root->m_right_brother != 0 ); // pues "(m_root->m_n_child > 0)"
    Tree_Node<E>* brother = m_root->m_right_brother;
    // assert( brother->Abs_n_child() > 0 ); // pues "brother" está "a la derecha" de "m_root"
    int n_brother = brother->Abs_n_child() - 1;
    if ( m_root->m_n_child == n_brother ) {
        return Tree( (NOT_null_pointer*) brother );
    } else {
        return Tree( );
    }
#if 0
    if (brother->m_n_child > 0) {
        if ( m_root->m_n_child + 1 == brother->m_n_child ) {
            return Tree( (NOT_null_pointer*) brother );
        } else {
            return Tree( );
        }
    } else {
        if ( m_root->m_n_child + 1 == - brother->m_n_child ) {
            return Tree( (NOT_null_pointer*) brother );
        } else {
            return Tree( );
        }
    }
#endif
}

/** Retorna el valor absoluto del campo \c "m_n_child".
    - Hay que tomar en cuenta que que \c m_n_child está incrementado en \c +int(1)
      porque la marca de "puntero al padre" es un valor negativo, y como hay un hijo número cero
      \c int(0), no sería posible marcar como "puntero al padre" a ese nodo
    - Esta rutina también existe para documentar el truco del "puntero al padre", pues más directo
      habría sido usar la función \c abs() definida en <code> \#include <cstdlib> </code>
    - En otras palabras, parte de la invariante de un nodo siempre será que
      <code> (m_n_child != 0) </code> porque siempre <code> int(0) == int(-0) </code> */
template <class E>
inline unsigned Tree_Node<E>::Abs_n_child() const {
    return ( m_n_child >= 0 ? unsigned(m_n_child) : unsigned( - m_n_child ) );
}

/** \c "n"-ésimo hermano a partir de \c "*this".
    - El hermano puede ser vacío aunque haya otros hermanos que no son vacíos.
    - Se "corre" hacia el n-ésimo hermano \c "n" "posiciones".
    - El hermano se determina contando sub-árboles hacia la derecha o izquierda de acuerdo
      al signo de \c "n":
          - Si \c n=0, regresa \c "*this".
          - Si \c n>0, regresa el hermano número \c "+n" contando hacia la derecha de \c "*this".
          - Si \c n<0, regresa el hermano número \c "-n" contando hacia la izquierda de \c "*this".
    - Si no existe un hermano número \c "n" retorna un sub-árbol vacío.
    - El árbol \c "T" tiene 3 hijos no vacíos \c "B", \c "C" y \c "E" y tiene 4 sub-árboles:
            - <code> C.Sibling( +0 ) == C</code>
            - <code> B.Sibling( +1 ) == C</code>
            - <code> E.Sibling( -2 ) == C</code>
            - <code> E.Sibling( -1 ) --> Vacío</code>
            - <code> A.Sibling( +1 ) --> Vacío </code>
            - <code> B.Sibling( -1 ) --> Vacío </code>
            - <code> E.Sibling( +1 ) --> Vacío </code>
        \code
           A <-- T
          /|\
        / / \ \       [] --> es representa un sub-árbol vacío
       B C  [] E
        \endcode

    \par Complejidad:
         O( <code> Father().Count_Children() </code> ) */
template <class E>
Tree<E> Tree<E>::Sibling( int n ) const {
    if (m_root == 0)  {
        return Tree( );
    } else if ( m_root->m_right_brother == 0 ) {
        return Tree( );
    } else if ( n==0 ) {
        return Tree( (NOT_null_pointer*) m_root );
    }

    Tree_Node<E>* brother; // desde dónde comenzar a buscar en la lista de hermanos
    unsigned n_target; // número de hijo que hay que encontrar: "(m_n_child + n)"

    // averigua "n_target" (hay que manejar el "+1" del "puntero al padre")
    if ( n < 0 ) { // a la izquierda ==> busque al padre para comenzar en m_left_child
        unsigned n_child = m_root->Abs_n_child()-1; // assert( n_child >= 0 );
        unsigned abs_n = unsigned(-n);      // assert( abs_n > 0 );
        if ( n_child < abs_n ) { // no se puede hacer la resta porque da un número de hijo negativo
            return Tree( ); // se sale pues no existen hijos antes del hijo más izquierdo
        } else {
            n_target = n_child - abs_n; // como el hermano está hacia la izquierda...
            // return Father().Child( n_target ); // ...hay que buscarlo desde el padre
            brother = m_root;
            while (brother->m_n_child > 0) { // se brinca los que no tienen el puntero al padre
                brother = brother->m_right_brother;
            }
            brother = brother->m_right_brother->m_left_child; // buscará desde el primer nodo
        }
    } else { // assert( n > 0 ); // a la derecha ==> busque desde aquí en adelante
        brother = m_root;
        n_target = unsigned(n) + m_root->Abs_n_child()-1;  // assert( (n > 0) && (n_target > m_n_child) );
    }

    // hay que manejar el "+1" del "puntero al padre" en "n_target"
    ++n_target; // para no tener que restarle int(1) a "child->m_n_child"

    // avance hacia la derecha en busca del hermano "n_target"
    // assert( brother != 0 );
    for (;;) {
        if (brother->m_n_child < 0) { // es el último hijo
            if ( unsigned(- brother->m_n_child)  == n_target ) {
                return Tree( (NOT_null_pointer*) brother );
            } else {
                return Tree( ); // esa era el último ==> ya no hay dónde más buscar
            }
        } else {
            unsigned n_child = brother->m_n_child;
            if (n_child == n_target) { // lo encontró
                return Tree( (NOT_null_pointer*) brother );
            } else if (n_child < n_target) { // siga buscando...
                brother = brother->m_right_brother;
            } else { // if (n_child > n_target) // ya se lo brincó; no está
                return Tree( );
            }
        }
    }
}

/** Obtiene el hijo más izquierdo del árbol.
    - Este método usualmente se usa junto con \c Right_Sibling()

    \par Complejidad:
         O( \c 1 )

    \remark Esta es una forma de procesar los hijos no vacíos de un sub-árbol de izquierda a derecha:

    \code
    Tree<E> Child = T.Leftmost();
    while ( ! Child.Empty() ) {
        Process( Child );
        Child = Child.Right_Sibling();
    }
    \endcode */
template <class E>
inline Tree<E> Tree<E>::Leftmost() const {
    if (m_root == 0)  {
        return Tree( );
    }
    return Tree( m_root->m_left_child ); // puede ser el puntero nulo
}

/** Obtiene el hijo más derecho del árbol.
    - Este método usualmente se usa junto con \c Left_Sibling()

    \par Complejidad:
         O( <code> Count_Children() </code> )

    \remark Esta es una forma de procesar los hijos no vacíos de un sub-árbol de derecha a izquierda:

    \code
    Tree<E> Child = T.Rightmost();
    while ( ! Child.Empty() ) {
        Process( Child );
        Child = Child.Left_Sibling();
    }
    \endcode */
template <class E>
Tree<E> Tree<E>::Rightmost() const {
    if (m_root == 0) {
        return Tree( );
    }
    Tree_Node<E>* child = m_root->m_left_child; // soy el primer hijo de mi padre
    if (child == 0) {
        return Tree( );
    }

    while (child->m_n_child > 0) { // todavía no se ha llegado al último hijo
        child = child->m_right_brother;
    }
    return Tree( (NOT_null_pointer*) child );
}

/** Implementación recursiva para \c Count().
    - Incrementa \c "n" en el número de hijos que tiene el sub-árbol cuya raíz es \c "p"
    - Cambia el valor de \c "n"
    - No cuenta el nodo raíz \c "p"
    - Esta función complementa a \c Count()

    \pre p != 0 */
template <class E>
void Tree<E>::Count0(const Tree_Node<E> * p, unsigned & n) {
    Tree_Node<E>* child = p->m_left_child; // soy el primer hijo de mi padre
    if (child == 0) {
        return;
    }

    for (;;) {
        ++n; // cuenta a este hijo
        Count0( child, n );
        if (child->m_n_child > 0) { // todavía no se ha llegado al último hijo
            child = child->m_right_brother;
        } else {
            break;
        }
    }
}

/** 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 Tree<E>::Count() const {
    if (m_root == 0) {
        return 0;
    } else {
        unsigned n = 1; // comienza contando en uno...
        Count0(m_root, n); // ... porque Count0() no cuenta la raíz
        return n;
    }
}

/** Retorna la cantidad de hijos del árbol.
    \par Complejidad:
         O( \c Count_Children() ) */
template <class E>
unsigned Tree<E>::Count_Children() const {
    if (m_root == 0) {
        return 0;
    }
    Tree_Node<E>* child = m_root->m_left_child;
    if ( 0 == child ) { // no hay hijos
        return 0;
    }
    unsigned tot = 0;
    for (;;) {
        ++tot; // cuenta a este hijo
        if (child->m_n_child > 0) { // todavía no se ha llegado al último hijo
            child = child->m_right_brother;
        } else {
            break;
        }
    }
    return tot;
}
template <class E>
inline bool operator == (const Tree<E> &p, const Tree<E> &q) { return Tree<E>::Comp0(p.m_root, q.m_root); }
template <class E>
inline bool operator != (const Tree<E> &p, const Tree<E> &q) { return !(p == q); }

/// Compara recursivamente los árboles cuyos nodo raíz son \c "*p" y \c "*q".
/// - Implementación recursiva para <code> operator==(Tree, Tree) </code>.
template <class E>
bool Tree<E>::Comp0(const Tree_Node<E> *p, const Tree_Node<E> *q) {
    if (p == q) {
        return true;
    }
    if ( (p==0) || (q==0)) { // son diferentes...
        return false; // ...pues sólo 1 está vácio
    }
    if ( p->m_n_child != q->m_n_child ) {
        return false; // números de hijo diferentes
    }
    if ( ! (p->m_data == q->m_data) ) {
        return false; // valor diferente en la raíz
    }

    // A comparar a todos los hijos
    p = p->m_left_child;
    q = q->m_left_child;
    for (;;) {
        if (p == q) { // como se terminaron juntos...
            return true; // ...son iguales
        }
        if ( (p==0) || (q==0) ) { // son diferentes...
            return false; // ...pues sólo 1 está vácio
        }
        if ( p->m_n_child != q->m_n_child ) {
            return false; // números de hijo diferentes
        }
        if (! Comp0(p, q) ) {
            return false;  // recorrido recursivo
        }
        if ( p->m_n_child < 0 ) { // assert( q->m_n_child < 0 );
            return true; // ya no hay más hermanos
        }
        p = p->m_right_brother;
        q = q->m_right_brother;
    }
}

/**   Verifica que se cumpla la invariante de la clase, o sea, que el objeto esté bien construido.
      - La razón por la que esta función no es un método es continuar la costumbre de muchos
        programadores quienes no definen la invariante para sus clases, pues en muchos
        casos sobra hacerlo.
      - No invoca \c check_ok( value_type& ) para cada valor almacenado, aunque si el árbol
        cumple con su invariante necesariamentes es porque también sus elementos almacenados
        están bien construidos.
      - Esta función en general es difícil de implementar, y en algunos casos es imposible
        pues, cuando el objeto no está bien construido, puede ocurrir que la función no
        retorne (como ocurriria si un nodo interno del árbol apunta de vuelta a la raíz, lo
        que se resulta en un círculo).
      - En general, la implementáción de esta función no es completa pues hay casos en que
        es imposible verificar la invariante de una clase.

    \par Complejidad:
         O( \c Count() ) ==> tiempo <br>
         O( \c Height() ) ==> espacio

         \post Retorna \c "true" si el árbol es un objeto bien construido
      \see \c check_ok(Tree&)

    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc11 */
template <class E>
bool check_ok(const Tree<E>& T) {

    if ( T.Empty() ) {
        return true;
    }

    #ifdef NO_Implementado_para_evitar_forzar_que_el_valor_almacenado_tenga_su_metodo_OK
        if (! check_ok( T.Data() ) ) { // si el valor almacenado no esta bien...
            return false; //... tampoco lo está el árbol
        }
        /* Usar la función check_ok(Tree::value_type en lugar del método
        Tree::value_type::Ok() evitar forzar a que los programadores clientes
        que usen árboles estén obligados a implementar el método
        Tree::value_type::Ok(), que se encarga de verificar la invariante del valor
        almacenado en le árbol.
        - Lindo: if (! check_ok( T.Data() ) ) //.... la función check_ok() es opcional
        - ¡FEO!: if (! T.Data().Ok() ) //... pues obliga a que exista el método value_type::Ok()
        */
    #endif

    unsigned N = T.Rightmost().Child_Number();
    for (unsigned i = 0; i < N; ++i) {
        if ( T.Child(i).Empty() ) { // este hijo no existe
            // continue; // con el siguiente
        }
        else if ( T.Child(i).Father() != T.Root() ) { // ==> ! T.Father.Empty()
            return false; // parece que este hijo no es mi hijo...
        }
        else if ( i != T.Child(i).Child_Number() ) {
            return false; // no estoy registrado como el i-ésimo hijo de mi padre
        }
        else if ( T.Child(i).Father().Child( i ) != T.Child( i ) ) {
            return false; // no estoy registrado como el i-ésimo hijo de mi padre
        }
        else if ( ! check_ok( T.Child(i) ) ) {
            return false; // hijo roto...
        }
    }
    return true;

    // Las siguientes relaciones lógicas se cumplen
    // [ ! T.Empty() ]                    ==> [ T.Root()!= Tree() ]
    // [ T.Child(i).Father() == T.Root()] ==> [ ! T.Father.Empty() ]

    /* Si este método retorna es porque el árbol está bien construido. Sin embargo,
       una invocación a check_ok() con un árbol mal construido posiblemente nunca retorne.
    */
}


/// Sustituye por \c "d" el valor almacenado en la raíz del árbol.
/// - Si el árbol está vacío, le agrega el nodo raíz.
/// \returns \c *this
template <class E>
Tree<E> Tree<E>::Change_Root(const value_type & d) {
    if (m_root == 0) { // como el árbol está vacío hay que agregarle la raíz
        m_root = Tree_Node<E>::Get_New(d); // crea el nodo raíz
        m_root->m_left_child = 0;
        m_root->m_right_brother = 0;
        m_root->m_n_child = -1;
    } else { // como no hay más referencias....
        m_root->m_data = d; // ... cambia el valor directamente
    }
    return *this;
}

/** 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"

    \pre <code> !Empty() && (0 <= n) && (n < \e infinito) </code>

    \par Complejidad:
         O( \c Count_Children() )

    \returns <code> Child(n) </code>  */
template <class E>
Tree<E> Tree<E>::Change_Child(unsigned n, const value_type &d) {
    if (m_root == 0) { // ignora árboles vacíos
        return Tree( );
    }

    n++; // evita incrementar "m_n_child" en cada iteración

    if (m_root->m_left_child == 0) { // Hay que agregar un sub-árbol nuevo
        Tree_Node<E> * p = Tree_Node<E>::Get_New(d);
        p->m_n_child = -int(n);
        p->m_right_brother = m_root;
        m_root->m_left_child = p;
        p->m_left_child = 0;
        return Tree ( (NOT_null_pointer*) m_root->m_left_child );
    }

    // assert( m_root->m_left_child != 0 );
    Tree_Node<E>* brother = m_root->m_left_child;
    unsigned n_brother =  brother->Abs_n_child();

    if ( n < n_brother ) { // Hay que crear Child(n) y ponerlo de primero
        Tree_Node<E>* p = Tree_Node<E>::Get_New(d);
        p->m_n_child = +int(n);
        p->m_right_brother = brother;
        m_root->m_left_child = p;
        p->m_left_child = 0;
        return Tree ( (NOT_null_pointer*) p );
    } else if ( n == n_brother ) {
        brother->m_data = d; // le cae encima al valor anterior
        return Tree ( (NOT_null_pointer*) brother );
    }

    // Child(n) no es el primer hijo de "m_root"
    // assert( m_root->m_left_child != Child(n).m_root );

    // assert( n_brother < n); // se corre hacia la derecha para encontrar "Child(n)"

    Tree_Node<E>* prev = brother;
    for (;;) {
        if ( brother->m_n_child < 0 ) {
            if ( int(n) ==  - brother->m_n_child ) {
                brother->m_data = d; // le cae encima al valor anterior
                return Tree ( (NOT_null_pointer*) brother );
            } else if (int(n) <  - brother->m_n_child ) {
                Tree_Node<E>* p = Tree_Node<E>::Get_New(d); // ... [d] ==> [brother] ==> end
                p->m_n_child = int(n);
                p->m_right_brother = brother;
                prev->m_right_brother = p;
                p->m_left_child = 0;
                return Tree ( (NOT_null_pointer*) p );
            } else {
                Tree_Node<E>* p = Tree_Node<E>::Get_New(d); // ... [brother] ==> [d] ==> end
                p->m_n_child = - int(n);
                p->m_right_brother = brother->m_right_brother;
                brother->m_n_child = - brother->m_n_child; // ahora el último es [d]
                brother->m_right_brother = p;
                p->m_left_child = 0;
                return Tree ( (NOT_null_pointer*) p );
            }
        } else { // assert( brother->m_n_child > 0 );
            if ( int(n) ==  brother->m_n_child ) {
                brother->m_data = d; // le cae encima al valor anterior
                return Tree ( (NOT_null_pointer*) brother );
            } else if ( brother->m_n_child < int(n) ) {
                prev = brother;
                brother = brother->m_right_brother;
            } else { // como se acaba de pasar ==> hay que agregarlo después de "prev"
                Tree_Node<E>* p = Tree_Node<E>::Get_New(d);
                p->m_n_child = int(n); // como "brother" no es el último, tampoco lo será "p"
                p->m_right_brother = brother;
                prev->m_right_brother = p;
                p->m_left_child = 0;
                return Tree ( (NOT_null_pointer*) p );
            }
        }
    }
}

/** Sustituye por \c "d" el valor almacenado en el hermano inmediatamente anterior del sub-árbol.
    - Si <code> n == Child_Number() </code> cambia el valor
      del hijo número \c "n-1" de \c Father()
    - Si no existe el hijo número \c "n-1" de \c Father() lo agrega como
      una hoja con valor \c "d"
    - Si ya existe ese hijo número \c "n-1", le sustituye su valor por \c "d"
    - Retorna un árbol vacío si no es posible que exista el hijo número \c "n-1" de \c Father()

    \pre <code> !Empty() && (1 <= Child_Number()) </code>

    \par Complejidad:
         O( <code> Father().Count_Children() </code> )

    \returns El hermano izquierdo, <code> Sibling(-1) </code> */
template <class E>
Tree<E> Tree<E>::Change_Left_Sibling_Inmediate( const E &d ) {
    unsigned n = Child_Number();
    if (n > 0 ) {
        return Father().Change_Child( n-1, d );
    } else {
        return Tree( );
    }
}

/** Sustituye por \c "d" el valor almacenado en el hermano inmediatamente posterior del sub-árbol.
    - Si <code> n == Child_Number() </code> cambia el valor
      del hijo número \c "n+1" de \c Father()
    - Si no existe el hijo número \c "n+1" de \c Father() lo agrega como
      una hoja con valor \c "d"
    - Si ya existe ese hijo número \c "n+1", le sustituye su valor por \c "d"
    - Retorna un árbol vacío si no es posible que exista el hijo número \c "n+1" de \c Father()

    \pre <code> !Empty() && ( Child_Number() < \e infinito ) </code>

    \par Complejidad:
         O( \c 1 )

    \returns El hermano derecho, <code> Sibling(+1) </code> */
template <class E>
Tree<E> Tree<E>::Change_Right_Sibling_Inmediate( const value_type &d ) {
    if (m_root == 0) {
        return Tree( );
    }
    if ( m_root->m_right_brother == 0 ) { // es la raíz del árbol y por eso no tiene hermanos
        return Tree( );
    }

    Tree_Node<E> * brother;
    if ( m_root->m_n_child < 0 ) { // "*this" es el último hijo
        m_root->m_n_child = - m_root->m_n_child; // ya "m_root" no es el último hijo

        brother = Tree_Node<E>::Get_New( d );
        brother->m_n_child = - ( m_root->m_n_child + 1 ); // "brother" es el último hijo

        brother->m_left_child = 0;
        brother->m_right_brother = m_root->m_right_brother;
        m_root->m_right_brother = brother;

        return Tree( (NOT_null_pointer*) brother );
    }

    // assert( m_root->m_n_child > 0 );
    int n_brother = m_root->m_right_brother->Abs_n_child();
    if ( m_root->m_n_child + 1 == n_brother ) {
        m_root->m_right_brother->m_data = d;
        return Tree( (NOT_null_pointer*) m_root->m_right_brother );
    } else {
        brother = Tree_Node<E>::Get_New( d );
        brother->m_n_child = m_root->m_n_child + 1; // "brother" no puede ser el último hijo

        brother->m_left_child = 0;
        brother->m_right_brother = m_root->m_right_brother;
        m_root->m_right_brother = brother;

        return Tree( (NOT_null_pointer*) brother );
    }
}

/** Elimina recursivamente a \c "*p" y a todos sus descendientes.
    - Implementación recursiva para \c Erase()
    - Borra el nodo sólo después de que constata que ya no hay punteros que le apunten
    - No saca a \c "*p" de la lista de hijos del padre ==> ese es el trabajo
      de \c Graft() o \c Erase()
    - La rutina llamadora invoca \c Erase0() porque sabe que al decrementar
      \c "p->m_refCount" queda en cero
    - No decrementa \c "p->m_refCount" porque ya el invocador sabe que hay que destruir \c "*p"
    - Recursivamente, borra a los descendientes de \c "*p"

    \code
    // Forma usual de invocación
    if ( child->m_refCount <= 1 ) { // Ya no hay más referencias a "child"
        Erase0( child ); // lo elimina
    } else {
        child->m_refCount--; // uno menos le apunta
        child->m_n_child = -1;
        child->m_right_brother = 0; // ya no es hijo de nadie
    }
    \endcode

    \pre <code> (p != 0) && (p->m_refCount == 1) </code>
    \post No cambia \c "p" porque trabaja con una copia de su valor  */
template <class E>
void Tree<E>::Erase0( Tree_Node<E> * p ) {
    // assert( p != 0 );
    // assert( p->m_refCount == 1 );

    // Primero hay que matar hijos...
    if ( p->m_left_child != 0 ) {
        Tree_Node<E> *next, *child = p->m_left_child;
        while ( child != 0 ) { // como hay hijos, decide a a cuáles matar
            if ( child->m_n_child < 0 ) {
                next = 0; // lo obliga a salir porque "child" es el último
            } else {
                next = child->m_right_brother; // recuerda quién es el siguiente
            }
            if ( child->m_refCount == 1 ) {
                Erase0( child ); // lo mata porque ésta es la última referencia
                // OJO: "child" está destruid