Tree_L.h

Go to the documentation of this file.

// 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 {            // assert( child->m_n_child > 0 );
            if ( static_cast<unsigned>(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á destruido ==> "child->m_right_brother" es un error
            } else {
                child->m_refCount--; // ya "*p" no le apunta
                child->m_n_child = -1; // ya no tiene padre porque "*p" va a morir
                child->m_right_brother = 0; // ni tampoco tiene hermanos
            }
            child = next; // hay que evitar usar "child->m_right_brother" si "child" ya está destruido
        }
    }
    #ifdef USE_v_Alive
        // Elimina a "p" de m_v_Alive[]
        for (unsigned j = 0; j < Tree_Node<E>::N_Alive; ++j) {
            if (p == Tree_Node<E>::m_v_Alive[j]) { // busca hasta que encuentra al puntero
                break;
            }
        }
        if (j < Tree_Node<E>::N_Alive) { // sí lo encontró
            for (unsigned k = j; k < Tree_Node<E>::N_Alive-1; ++k) { // corre a los demás para atrás
                Tree_Node<E>::m_v_Alive[k] = Tree_Node<E>::m_v_Alive[k+1];
            }
            Tree_Node<E>::m_n_Alive--; // ahora hay uno menos
            Tree_Node<E>::m_v_Alive[ Tree_Node<E>::m_n_Alive ] = 0;
        } else {
            for (unsigned k = 0; k<3; ++j) { // marca "feos" los del final
                Tree_Node<E>::m_v_Alive[Tree_Node<E>::N_Alive-1-k] = (Tree::Tree_Node<E> *)(-1);
            }
        }
    #endif
    // Después de matar a los hijos, mata al nodo...
    delete p; // ... porque esta es la última referencia
}

/** Elimina el árbol y sus descendientes.
    \par Complejidad:
         O( \c Count() ) + O( <code> Father().Count() </code> ) ==> tiempo <br>
         O( \c Height() ) ==> espacio

    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc03  */
template <class E>
void Tree<E>::Erase() {
    if (m_root == 0) {
        return;
    }

    // Encuentra el padre de "m_root"
    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().Same( Tree( brother ) ) );

    // Desconecta a "m_root" de la lista de hijos del padre
    if (father == 0) { // sólo la raíz tiene en blanco el puntero "m_right_brother"
        // no hay que desenlazar a la raíz porque nunca está en una lista de hermanos
    } else {
        // busca al "nodo anterior" para sacar a "m_root" de la lista de sus hermanos
        if ( m_root == father->m_left_child ) { // "m_root" es el hijo más izquierdo
            if ( m_root->m_n_child < 0 ) {
                father->m_left_child = 0; // elimina la lista de hijos porque "m_root" no tiene hermanos
            } else {
                father->m_left_child = m_root->m_right_brother; // desenlaza al primer hijo
            }
        } else {
            brother = father->m_left_child; // hijo más izquierdo de Father()
            while ( m_root != brother->m_right_brother ) {
                brother = brother->m_right_brother;
            }
            brother->m_right_brother = m_root->m_right_brother; // saca a  "m_root" de la lista de hermanos
        }
    }

    // ahora ya puede detruir al nodo
    if ( m_root->m_refCount == 1 ) {
        Erase0(m_root);  // mata al nodo porque ésta es la última referencia
    } else {
        m_root->m_refCount--; // lo va a desconectar de "m_root"
        m_root->m_n_child = -1; // ya no tiene padre
        m_root->m_right_brother = 0; // ni tampoco tiene hermanos
    }
    m_root = 0;
}

// Esta documentación para Tree::Erase_Son() aparece acá porque Doxygen no permite
// incluir un párrafo aparte "\par" en la documentación de 1 sólo renglón.

/** \fn void Tree::Erase_Son(unsigned n)

    \brief Elimina el sub-árbol número \c "n"

    \par Complejidad:
         O( <code> Child(n).Count() </code> ) ==> tiempo <br>
         O( <code> Height( Child(n) )  </code> ) ==> espacio
*/

/** Elimina el sub-árbol número \c "n-1" y retorna un puntero al nodo anterior al borrado.
    - Esta es la rutina que en realidad hace el trabajo de \c Erase_Son().
    - Elimina el sub-árbol número \c "n-1", como también lo hace \c Erase_Son().
    - La única diferencia con \c Erase_Son() es que este método retorna un puntero
      al nodo anterior al nodo eliminado.
    - "prev" apunta al nodo que está antes de "prev" en el árbol.
    - Trabaja con \c "n-1" porque no incrementa el valor de \c "n", pues se supone que
      la rutina invocadora ya hizo ese ajuste en el valor originar de \c "n".
    - Esta rutina existe para compartir el código que se necesita para implementar
      \c Erase_Son() y \c Graft().
    - Si retorna <code> 0 == NULL </code> es porque <code> Nodo[n-1] </code>
      debe ser el primero en la lista de hijos del padre.

    \remark [Eliminado porque ya no hace falta]
    - "prev_prev" apunta al nodo que está antes de "prev" en el árbol.
    - Si "prev" y "prev_prev" son la misma variable, el valor correcto para "prev" es
      calculado. */
template <class E>
void Tree<E>::Erase_Son_Prev(unsigned n, Tree_Node<E>* & prev /*, Tree_Node<E>* & prev_prev */) {
    // prev_prev = 0; // el que está "antes" de "prev"
    prev = 0; // nodo que antecede a "child"
    if (m_root == 0) { // ignora árboles vacíos
        return;
    }
    Tree_Node<E>* child = m_root->m_left_child; // "child" es el nodo que hay que eliminar
    if ( child == 0 ) { // no hay hijos ==> el Nodo[n] es un sub-árbol vacío
        return;
    }

    // n++; // sobra, porque la rutina invocadora ya ajustó el valor a cotejar con "m_n_child"

    // camina sobre los hermanos hasta llegar a Nodo[n]
    if ( child->m_n_child <= 0 ) { // sólo hay un hijo
        unsigned n_child = - child->m_n_child;
        if ( n == n_child ) { // es el único hijo y hay que eliminarlo
            if ( child->m_refCount <= 1 ) { // aquí saca a "child" de la lista de hijos de "m_root"
                Erase0( child );
            } else {
                child->m_refCount--;
                child->m_n_child = -1;
                child->m_right_brother = 0; // ya no es hijo de nadie
            }
            m_root->m_left_child = 0;
            return;
        } else { // no hace falta eliminar a nadie pues Child(n) es un sub-árbol vacío
             // hay que determinar adónde debe apuntar "prev"
            if ( n > n_child ) {
                // prev_prev = prev;
                prev = child;
                return; // porque el n-ésimo hijo estará después de "child"
            } else { // assert( n < n_child );
                return; // el n-ésimo hijo quedará de primero en la lista de hijos del padre
            }
        }
    }

    // assert( (child->m_n_child > 0) && (Count_Children() > 1) );
    for (;;) {
        if (child->m_n_child <= 0) { // hay que eliminar el último hijo
            if ( unsigned(- child->m_n_child) == n ) { // assert( prev != 0 );
                prev->m_right_brother = child->m_right_brother;
                prev->m_n_child = - prev->m_n_child;  // este es el nuevo último
                if ( child->m_refCount <= 1 ) {
                    Erase0( child );
                } else {
                    child->m_refCount--;
                    child->m_n_child = -1;
                    child->m_right_brother = 0; // ya no es hijo de nadie
                }
            } else if ( unsigned(- child->m_n_child) < n ) {
                // no encontró al hermano con m_n_child == n
                // prev_prev = prev;
                prev = child;
            }
            break;
        } else if ( unsigned(child->m_n_child) == n ) {
            if ( prev == 0 ) {
                m_root->m_left_child = child->m_right_brother;
            } else {
                prev->m_right_brother = child->m_right_brother;
            }
            if ( child->m_refCount <= 1 ) {
                Erase0( child );
            } else {
                child->m_refCount--;
                child->m_n_child = -1;
                child->m_right_brother = 0; // ya no es hijo de nadie
            }
            break;
        } else if ( unsigned(child->m_n_child) < n) {
            // prev_prev = prev;
            prev = child;
            child = child->m_right_brother;
        } else { // assert( unsigned(child->m_n_child) > n );
            break; // no encontró al hermano con m_n_child == n
        }
    }
}

/**   Verifica que se cumpla la invariante de la clase, o sea, que el objeto esté bien construido.
      - Además de todo el trabajo que hace \c check_ok(Tree& T), acá hay que constatar que
        el nodo raíz no tiene padre, que es la diferencia fundamental entre un árbol y un sub-árbol

      \post Retorna \c "true" si el árbol es un objeto bien construido

      \deprecated Los árboles y los sub-árboles son la misma cosa.

      \see \c check_ok(Tree&)  */
template <class E>
inline bool check_ok_Tree(Tree<E>& T) {
    if ( T.Root().Empty() ) {
        return true;
    } else {
        return ( T.Root().Father().Empty() ) && check_ok( Tree<E> (T) );
    }
}

/** Hace una copia profunda nodo por nodo del árbol cuyo nodo raíz es \c "*p".
    - Implementación recursiva para \c Tree::Copy_Deep()
    - No altera \c p->m_refCount porque copia los nodos
    - El campo \c p->m_right_brother queda con basura porque no queda inicializado
    - Le corresponde a la rutina invocadora inicializar \c p->m_right_brother

    \pre <code> p != 0 </code>
    \post No cambia \c "p" porque trabaja con una copia de su valor

    \returns Puntero al nodo raíz del árbol copiado */
template <class E>
Tree_Node<E> * Tree<E>::Copy_Deep0(const Tree_Node<E> * p) {
    Tree_Node<E> * q; // resultado
    q = Tree_Node<E>::Get_New(p->m_data); // m_refCount = 1;
    q->m_n_child = p->m_n_child;

    if ( p->m_left_child == 0 ) {
        q->m_left_child = 0;
    } else { // cuando hay hijos los copia
        Tree_Node<E> * pChild = p->m_left_child;
        Tree_Node<E> * qChild = Copy_Deep0( pChild ); // copia el primer nodo
        q->m_left_child = qChild;
        while ( pChild->m_n_child > 0 ) {
            pChild = pChild->m_right_brother;
            qChild->m_right_brother = Copy_Deep0( pChild );
            qChild = qChild->m_right_brother;
        }
        qChild->m_right_brother = q; // "q" es el padre de todos
    }
    return q;
}

/** Copia profunda de \c "o".
    - Copia todo el valor de \c "o" sobre \c "*this", de forma que el nuevo valor de
      \c "*this" sea un duplicado exacto del valor de \c "o"
    - El valor anterior de \c "*this" se pierde
    - El objeto \c "o" mantiene su valor anterior
    - Luego de la copia, cuando el valor de \c "o" cambia, el de \c "*this" no cambiará,
      y viceversa, pues la copia es una copia profunda; no es superficial
    - Si \c "*this" es \c "o" entonces su valor no cambia
    - Después de esta operación siempre ocurre que <code> *this == o </code>

    \par Complejidad:
         O( \c Count() ) + O( \c o.Count() )

    \returns \c *this

    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc05 */
template <class E>
Tree<E>& Tree<E>::Copy_Deep(const Tree &o) {
    // Borra el valor actual
    if (m_root != 0) {
        if ( m_root->m_refCount == 1 ) { // como es el último...
            Erase0(m_root); // ...lo mata
        } else {
            m_root->m_refCount--;
        }
    }

    // Hace la copia desde "o"
    if (o.m_root != 0 ) {
        m_root = Copy_Deep0( o.m_root );
        m_root->m_n_child = -1; // es el nodo raíz
        m_root->m_right_brother = 0;
        m_root->m_refCount = 1;
    } else {
        m_root = 0;
    }
    return *this;
}

/** Injerta \c "o" para que sea el \c "n"-ésimo hijo de \c "*this".
    - Si \c "o" es sub-árbol de otro árbol, dejara de serlo para pasar ser hijo de \c "*this"
    - Si \c "*this" tiene un \c "n"-ésimo hijo, ese hijo desaparece
    - Si \c "o" está vacío, elimina el \c "n"-ésimo hijo del árbol [<code> Erase_Son(n) </code>]

    \pre
    - <code> ! Root().Empty() </code>
       - Si el  árbol está vacío no tiene raíz, y por lo tanto tampoco puede tener hijos
    - <code> ! Ancestor(o, *this) </code>
       - "o" no puede ser ancestro de *this"
    - <code> (0 <= n) && (n < \e infinito) </code>
    - <code> ! Root(). Same( o.Root() ) </code>

    \post
    - \c "o" deja de ser sub-árbol del árbol en que estaba
    - <code> o.Father() .Same( Root() ) </code>

    \remarks
    - Un sub-árbol puede ser hijo (o sub-árbol) de otro árbol
    - Un sub-árbol puede ser hijo únicamente de un árbol
    - Este método no hace nada cuando [ <code> ! Root() .Same( o.Root() ) </code> ]
    - Injertar un sub-árbol vacío es una forma de eliminar a un hijo junto con
      toda su descendencia

    \returns "o" ==> El árbol recién injertado

    \par Complejidad::
         O( \c Count_Children() ) + O( <code> o.Father().Count_Children() </code> ) */
template <class E>
Tree<E> Tree<E>::Graft(unsigned n, Tree &o) {
    if (m_root == 0) { // ignora árboles vacíos
        return Tree( );
    }
    if (m_root == o.m_root) { // evita auto-borrado
        return *this;
    }
    #ifdef FALTA_verificar_en_Graft
        bool Ancestor( Tree & Child, Tree & Father );
        assert( ! Ancestor( o, *this ) ); // "o" no puede ser ancestro de *this"
    #endif

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

    if ( o.m_root == 0 ) { // Sólo hay que eliminar el hijo número "n" de "m_root"
        Tree_Node<E> * prev;
        Erase_Son_Prev(n, prev /*, prev */);
        return Tree( ); // si se vale repetir "prev" en Erase_Son_Prev()
    }
    // assert( o.m_root != 0 );

    // Determina quién es el padre de "o"
    Tree_Node<E> * brother = o.m_root;
    while ( brother->m_n_child > 0 ) {
        brother = brother->m_right_brother;
    }
    Tree_Node<E> * o_father = brother->m_right_brother; // éste es el padre de "o"
    Tree_Node<E> * prev;

    if ( o_father != m_root ) {
        /*  El puntero "prev" apunta al nodo después del que hay que injertar "o".
            - Si "prev == 0" hay que  poner a "o" de primero en lista de hijos de "m_root".
            - Si "prev != 0" hay que  instalar "o" después de "prev".
            - Aquí es donde se usa Erase_Son_Prev().
        */
        // Elimina el hijo número "n" de "m_root"
        Erase_Son_Prev(n, prev /*, prev */);
        // assert( Child(n-1).Empty() ); // Ojo: mata "Child(n-1)" porque ya "n" está incrementado
    } else { // assert( o_father == m_root ); //  Caso especial ==> T.Graft( T.Child(n), n ± i );
        unsigned o_n_child = o.m_root->Abs_n_child();
        if ( o_n_child == n ) { // Caso especial cuando "o" ya es hijo de "m_root"
            // "o" está en su lugar ==> no hay que hacer nada
            // [y hay que evitar borrarlo con Erase_Son(n)]
            return Tree( (NOT_null_pointer*) o.m_root );
        }

        Erase_Son_Prev(n, prev /*, prev */);

        if ( (prev == o.m_root) || (prev != 0 && prev->m_right_brother == o.m_root ) ) {
            // ya "o" está en donde debe
            if ( o.m_root->m_right_brother == m_root ) { // basta cambiar "m_n_child"
                o.m_root->m_n_child = - int(n);
            } else  {
                o.m_root->m_n_child = + int(n);
            }
            return Tree( (NOT_null_pointer*) o.m_root );
        }
    }

    if (o_father != 0) { // Saca a "o" de la lista de hijos de su padre
        o.m_root->m_refCount--; // pues no estará en la lista de hijos de su padre actual
        assert( o_father->m_left_child != 0 );
        if ( o.m_root == o_father->m_left_child ) { // "o" es el primer hijo
            if ( o.m_root->m_n_child < 0 ) { // "o" es el único hijo
                o_father->m_left_child = 0;
            } else { // "o" tiene hermanos
                o_father->m_left_child = o.m_root->m_right_brother;
            }
        } else {
            brother = o_father->m_left_child; // hermano más izquierdo de "o"
            while ( brother->m_right_brother != o.m_root ) {
                brother = brother->m_right_brother;
            }
            brother->m_right_brother = o.m_root->m_right_brother;
            if ( o.m_root->m_n_child < 0 ) { // "o" estaba de último hijo
                brother->m_n_child = - brother->m_n_child; // hay un nuevo hijo de último
            }
        }
    }
    // assert( o.Father().Empty() ); // ya "o" está solito y sin familia

    o.m_root->m_refCount++; // lo incrementa porque lo va a enlazar como hijo de "m_root"

    if ( prev == 0 ) { // enlaza "o" al principio de la lista de hijos de "m_root"
        if ( m_root->m_left_child == 0 ) {
            o.m_root->m_right_brother = m_root; // "o" será el único hijo de "m_root"
            o.m_root->m_n_child = - int(n);
            m_root->m_left_child = o.m_root;
        } else {
            o.m_root->m_right_brother = m_root->m_left_child;
            // assert( o.m_root->m_right_brother != m_root );
            o.m_root->m_n_child = + int(n);
            m_root->m_left_child = o.m_root;
        }
    } else { // assert( prev != 0 );
        // enlaza en el medio de la lista de hijos de "m_root"
        o.m_root->m_right_brother = prev->m_right_brother;
        prev->m_right_brother = o.m_root;
        if ( o.m_root->m_right_brother == m_root ) {
            prev->m_n_child = - prev->m_n_child; // ya "prev" no está de último
            o.m_root->m_n_child = - int(n);
        } else  {
            o.m_root->m_n_child = + int(n);
        }
    }

    return Tree( (NOT_null_pointer*) o.m_root );


/*  ¿Por qué hay que usar "prev_prev"? En realidad no hace falta, pero sí hay que
    destacar un caso especial, cuando "o" es hijo de "*this", o sea cuando:
    - ( Root(). Same( o.Root() ) )
        R       T.Erase(); T = 'R';
       / \      T.Change_Child(1, '1');
      1   3     T.Change_Child(3, '3');

    Al ejecutar T.Graft( 5 , T.Child(3) ); lo que hay que hacer es desligar el Nodo['3'] de su
    padre, el árbol T que tiene por raíz a Nodo['A'], para ligarlo de nuevo como Nodo['5'].

    Para este caso, "prev" apunto a T.Child(3), pues es después de Nodo['3'] en donde habría
    que  enlazar a Nodo['5']. Desafortunadamente, como el primer paso del algoritmo saca de
    T a Nodo[3], al tratar de enlazarlo luego de "prev" en realidad lo que se haría es
    enlazar al nodo después de sí mismo; estor resulta en la "desaparición misteriosa"
    de Nodo['3']. Por eso, la solución a este caso especial, es retornar no "prev", sino
    "prev_prev", que apunta al nodo anterio al Nodo[5], que en este caso es Nodo['1'].
*/
} // Graft()

} // namespace TL

#endif  // Tree_L_h

// EOF: Tree_L.h