Página principal | Lista de namespace | Lista de componentes | Lista de archivos | Miembros del Namespace  | Miembros de las clases | Archivos de los miembros | Páginas relacionadas

Tree_L.h

Ir a la documentación de este archivo.
00001 // Tree_L.h (c) 2006 adolfo@di-mare.com
00002 
00003 /** \file Tree_L.h
00004     \brief Declaraciones y definiciones para la clase \c Tree
00005 
00006     \author Adolfo Di Mare <adolfo@di-mare.com>
00007     \date   2006
00008 
00009     - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
00010 */
00011 
00012 #ifndef Tree_L_h
00013 #define Tree_L_h
00014 
00015 #ifndef NDEBUG // ==> Overview of File Translation ==> C++
00016     #define USE_v_Alive
00017     #undef  USE_v_Alive
00018 #endif
00019 
00020 #include <cassert> // para usar assert()
00021 
00022 /// Arboles de adolfo@di-mare.com cuyos nodos contienen un puntero izquierdo al hijo y uno derecho al hermano o padre
00023 namespace TL {
00024 
00025 template <class E> class Tree;
00026 template <class E> bool check_ok( const E & );
00027 template <class E> bool check_ok( const Tree<E>& T); // declaration hacia adelante
00028 
00029 /// Nodos almacenados en el árbol.
00030 template <class E>
00031 class Tree_Node {
00032 public:
00033     friend class Tree<E>;
00034     typedef E value_type; ///< Nombre estándar del tipo de elemento contenido
00035 private:
00036     Tree_Node( const value_type& d ) : m_data( d ), m_refCount(1) {} ///< Constructor de vector
00037     static Tree_Node<E>* Get_New(const value_type& d);
00038     unsigned Abs_n_child() const;
00039 private:
00040     value_type  m_data; ///< Valor almacenado en el nodo
00041     unsigned    m_refCount; ///< Cantidad de punteros hacia mi
00042     int         m_n_child; ///< Soy el el hijo número <code> "(m_n_child - 1)" </code> de mi padre
00043     Tree_Node<E> * m_left_child; ///< Puntero al nodo hijo más izquierdo
00044     Tree_Node<E> * m_right_brother; ///< Puntero al nodo hermano o al padre
00045 private:
00046     #ifdef USE_v_Alive // ==> NDEBUG ==> Overview of File Translation ==> C++
00047         static const unsigned N_Alive = 333; ///< Cantidad máxima posible de punteros en uso
00048         static Tree_Node<E> *   m_v_Alive[N_Alive]; ///< Punteros en uso
00049         static unsigned m_n_Alive; ///< Cantidad de punteros en uso
00050     #endif
00051 }; // Tree_Node
00052 
00053 /** Los métodos para trabajar con árboles regresan "referencias" que son sub-árboles.
00054     - Un sub-árbol es parte del árbol, por lo que al modificar los valores del
00055       sub-árbol también el árbol original queda cambiado.
00056     - Para evitar este tipo de modificación indirecta, es necesario trabajar
00057       con una "copia profunda" del árbol orignal, la que se puede obtener con
00058       \c Tree::Copy_Deep().
00059     - Aún si el árbol original es eliminado, el sub-árbol continúa existiendo
00060     - Debido a que los árboles y sub-árboles son referencias, en C++ es necesario mantener
00061       internamente "cuentas de referencia" que impiden que métodos como \c Father() o \c Root()
00062       sean métodos <code>const</code>.
00063     - Muchos métodos retornan referencias \c Tree& porque es más eficiente, pues cada
00064       vez que un \c Tree es copiado hay que actualizar la "cuenta de referencia" de
00065       la raíz del sub-árbol.
00066 */
00067 template <class E>
00068 class Tree {
00069 public:
00070     typedef E value_type; ///< Nombre estándar del tipo de elemento contenido
00071 /// \name Constructores y destructor
00072 //@{
00073 public:
00074     Tree() : m_root(0) {} ///< Constructor de vector
00075     Tree(const Tree& o);
00076     Tree(const value_type & d);
00077     ~Tree();
00078 private:
00079     /// Constructor a partir de un nodo
00080     Tree(Tree_Node<E>* p) : m_root(p) { if (p!=0) { p->m_refCount++; } }
00081     /// Truco para usar el constructor que no verifica <code> (p != 0) </code>
00082     typedef void NOT_null_pointer;
00083     /// Constructor a partir de un nodo [ requiere <code> p != 0 </code> ]
00084     Tree(NOT_null_pointer* p) : m_root( (Tree_Node<E>*)p) { // assert( p != 0 );
00085         ((Tree_Node<E>*)p)->m_refCount++; }
00086 //@}
00087 
00088 /// \name Operaciones básicas
00089 //@{
00090 public:
00091     bool     Empty() const { return (m_root == 0); } ///< Retorna \c "true" si el sub-árbol está vacío
00092     unsigned Count() const ;
00093     unsigned Count_Children() const ;
00094     unsigned Size () const { return Count(); } ///< Usa \c Count() para retornar la cantidad de valores almacenados en el sub-árbol
00095     friend bool check_ok<E>(const Tree<E>& T);
00096     bool        Ok() { return check_ok(*this); } ///< Usa \c check_ok(Tree& T) para verificar la invariante de \c Tree
00097 //@}
00098 
00099 /// \name Operaciones de borrado
00100 //@{
00101 public:
00102     void Erase();
00103     void Erase_Son(unsigned n) { Tree_Node<E>*p; Erase_Son_Prev(n+1,p /*,p*/); }
00104 private:
00105     void Erase_Son_Prev(unsigned n, Tree_Node<E>*& /*, Tree_Node<E>*& */);
00106 //@}
00107 
00108 /// \name Operaciones de copiado
00109 //@{
00110 public:
00111     Tree& operator= (const Tree &o) { return Copy(o); } ///< Sinónimo de \c this->Copy(o)
00112     Tree& Copy (const Tree &o);
00113     Tree& Move (Tree &o);
00114     Tree& Swap (Tree &o);
00115     Tree& Copy_Deep( const Tree &o );
00116     /// Usa \c Change_Root() para sustituir por "d" el valor almacenado en la raíz del árbol
00117     Tree& operator=( const value_type & d) { Change_Root(d); return *this; }
00118 //@}
00119 
00120 /// \name Métodos para cambiar los valores almacenados en el árbol
00121 //@{
00122 public:
00123     Tree Change_Root(const value_type &d);
00124     Tree Change_Child( unsigned n, const value_type &d );
00125     Tree Change_Left_Sibling_Inmediate( const value_type &d );
00126     Tree Change_Right_Sibling_Inmediate( const value_type &d );
00127     Tree Graft( unsigned n, Tree &o );
00128 //@}
00129 
00130 /// \name Operaciones para usar los valores almacenados
00131 //@{
00132 public:
00133     value_type& Data        () { return  m_root->m_data;  } ///< Valor almacenado en la raíz del sub-árbol
00134     value_type& operator *  () { return   Data();  } ///< Valor almacenado en la raíz del sub-árbol
00135     value_type* operator -> () { return &(m_root->m_data); } ///< Puntero al valor almacenado en la raíz del sub-árbol
00136     const value_type& Data        () const { return  m_root->m_data;  } ///< Valor almacenado en la raíz del sub-árbol
00137     const value_type& operator *  () const { return   Data();  } ///< Valor almacenado en la raíz del sub-árbol
00138     const value_type* operator -> () const { return &(m_root->m_data); } ///< Puntero al valor almacenado en la raíz del sub-árbol
00139 //@}
00140 
00141 /// \name Operaciones de comparación
00142 //@{
00143 public:
00144     template <class X> friend bool operator == (const Tree<X> &p, const Tree<X> &q); ///< ¿¿¿ (p == q) ???
00145     template <class X> friend bool operator != (const Tree<X> &p, const Tree<X> &q); ///< ¿¿¿ (p != q) ???
00146     bool Equals( const Tree & o ) const { return (*this)==o; } ///< ¿¿¿ (*this==o) ???
00147     /// Retorna \c true si \c "o" comparte la raíz con \c "*this"
00148     bool Same( const Tree & o ) const { return m_root == o.m_root; }
00149 //@}
00150 
00151 /// \name Métodos para recorrer el árbol
00152 //@{
00153 public:
00154     Tree Root() const { return Tree( m_root ); } ///< Raíz del sub-árbol
00155     Tree Father() const ;
00156     Tree Child(unsigned n) const;
00157     Tree Left() const;
00158     Tree Right() const;
00159     Tree Leftmost() const;
00160     Tree Rightmost() const;
00161     Tree Sibling(int n) const;
00162     Tree Left_Sibling() const;
00163     Tree Right_Sibling() const;
00164     Tree Previous_Sibling() const { return Left_Sibling(); } ///<  Sinónimo de \c Left_Sibling()
00165     Tree Prev_Sibling() const { return Left_Sibling(); } ///<  Sinónimo de \c Left_Sibling()
00166     Tree Next_Sibling() const { return Right_Sibling(); } ///<  Sinónimo de \c Right_Sibling()
00167     Tree Right_Sibling_Inmediate() const;
00168     Tree Left_Sibling_Inmediate() const;
00169 //@}
00170 
00171 /// \name Propiedades del árbol
00172 //@{
00173 public:
00174     /// Retorna \c "n" si \c "*this" es el n-ésimo hijo de su padre, si no retorna \c 0 (cero)
00175     unsigned Child_Number() const { return ( m_root==0 ? 0 : m_root->Abs_n_child() - 1); }
00176     /// Retorna \c "n" si el hijo más izquierdo de \c "*this" es el n-ésimo hijo, si no retorna \c 0 (cero)
00177     unsigned Leftmost_N() const { return Leftmost().Child_Number(); }
00178     /// Retorna \c "n" si el hijo más derecho de \c "*this" es el n-ésimo hijo, si no retorna \c 0 (cero)
00179     unsigned Rightmost_N() const { return Rightmost().Child_Number(); }
00180     /// Retorna \c "true" si el árbol es una hoja
00181     bool Is_Leaf() const { return (m_root != 0) && (m_root->m_left_child != 0); }
00182     /// Retorna \c "true" si el árbol no tiene padre
00183     bool Is_Root() const { return (m_root != 0) && (m_root->m_right_brother == 0); }
00184     /// Cantidad de referencias de la raíz del árbol
00185     unsigned use_count() const { return (m_root==0 ? 0 : m_root->m_refCount); }
00186 //@}
00187 
00188 /// \name Funciones para manipular valores a bajo nivel
00189 //@{
00190 private:
00191     /// Convierte el puntero al nodo en un referencia a \c Tree
00192     static Tree& CastTo_Sub_Tree_Ref ( Tree_Node<E> * &p )
00193     { return (Tree&) *( reinterpret_cast<Tree*> (&p)); }
00194 //@}
00195 
00196 /// \name Funciones recursivas que realizan el trabajo sobre nodos
00197 //@{
00198 private:
00199     static void Erase0(Tree_Node<E> * p);
00200     static bool Comp0(const Tree_Node<E> *p, const Tree_Node<E> *q);
00201     static void Count0(const Tree_Node<E> * p, unsigned & n);
00202     static Tree_Node<E>* Copy_Deep0(const Tree_Node<E> * p);
00203 //@}
00204 private:
00205     Tree_Node<E> * m_root; ///< Un árbol "es" el puntero al nodo raíz
00206 }; // Tree
00207 
00208 #ifdef USE_v_Alive
00209     unsigned Tree::Tree_Node<E>::m_n_Alive = 0; // Hay que "repetir" estos nombres acá para que el ...
00210     Tree::Tree_Node<E>* Tree::Tree_Node<E>::m_v_Alive[Tree::Tree_Node<E>::N_Alive]; // ... compilador les asigne memoria
00211 #endif
00212 
00213 /** Crea un nuevo nodo y lo inicializa con \c "d"
00214 
00215     - Para mejorar la eficiencia, no incializa los punteros del nodo.
00216     - Si la macro \c USE_v_Alive de compilación existe, también agrega el nuevo
00217       nodo al contenedor global \c Tree::m_v_Alive[], de manera que es posible
00218       saber si un puntero a un nodo está o no en uso.
00219     - En realidad sobra usar este método, pero la utilidad de usarlo es
00220       que es posible examinar \c Tree::m_v_Alive[] para saber si los métodos
00221       de árbol están correctamente implementados.
00222 */
00223 template <class E>
00224 inline Tree_Node<E> * Tree_Node<E>::Get_New( const E& d) {
00225     Tree_Node<E>* p = new Tree_Node(d);
00226     #ifdef USE_v_Alive
00227         m_v_Alive[m_n_Alive] = p;
00228         m_n_Alive++;
00229     #endif
00230     return p;
00231 }
00232 
00233 ///  Constructor de copia desde otro árbol (copia superficial).
00234 /// - Como un sub-árbol en realidad es una referencia, este método
00235 ///   no hace la copia completa [profunda] del árbol.
00236 template <class E>
00237 inline Tree<E>::Tree(const Tree& o) {
00238     if (o.m_root != 0) {
00239         o.m_root->m_refCount++; // una referencia más porque "o" y "*this" ...
00240     }
00241     m_root =  o.m_root; // ... ahora comparten la raíz
00242 }
00243 
00244 /**  Destructor.
00245     \par Complejidad:
00246          O( \c Count() )
00247 
00248     \see http://www.di-mare.com/adolfo/binder/c04.htm#sc04 */
00249 template <class E>
00250 Tree<E>::~Tree() {
00251     if (m_root != 0) {
00252         if (m_root->m_refCount == 1) {
00253             Erase0(m_root);
00254         } else {
00255             m_root->m_refCount--;
00256         }
00257     }
00258 }
00259 
00260 /// Constructor a partir de un valor
00261 template <class E>
00262 inline Tree<E>::Tree(const E & d) {
00263     m_root = Tree_Node<E>::Get_New(d);
00264     m_root->m_n_child = -1;
00265     m_root->m_left_child = 0;
00266     m_root->m_right_brother = 0;
00267 }
00268 
00269 /** Copia superficial desde \c "o".
00270     - El valor anterior de \c "*this" se pierde
00271 
00272     \par Complejidad:
00273          O( \c Count() )
00274 
00275     \returns *this
00276 
00277     \see http://www.di-mare.com/adolfo/binder/c04.htm#sc05 */
00278 template <class E>
00279 Tree<E>& Tree<E>::Copy( const Tree &o ) {
00280     if (m_root != o.m_root) { // evita auto-borrado
00281         if (m_root != 0) {
00282             if ( m_root->m_refCount == 1 ) { // como es el último...
00283                 Erase0(m_root); // ...lo mata
00284             } else {
00285                 m_root->m_refCount--;
00286             }
00287         }
00288         m_root =  o.m_root; // comparte la raíz
00289         if (o.m_root != 0) {
00290             o.m_root->m_refCount++; // una referencia más
00291         }
00292     }
00293     return *this;
00294 }
00295 
00296 /** Traslada el valor de \c "o" a \c "*this".
00297   - El valor anterior de \c "*this" se pierde
00298   - El nuevo valor de \c "*this" es el que \c "o" tuvo
00299   - \c "o" queda en el estado en que lo dejaría \c Erase()
00300   - Si \c "*this" es \c "o" entonces su valor no cambia
00301   - En general, después de esta operación casi
00302     nunca ocurre que <code> (*this == o) </code>
00303 
00304     \par Complejidad:
00305          O( \c Count() )
00306 
00307     \returns \c *this
00308 
00309     \see http://www.di-mare.com/adolfo/binder/c04.htm#sc07 */
00310 template <class E>
00311 Tree<E>& Tree<E>::Move( Tree &o ) {
00312     if (m_root == o.m_root) { // evita auto-borrado
00313         if (m_root != 0) {
00314             if ( m_root->m_refCount == 1 ) { // como es el último...
00315                 Erase0(m_root); // ...lo mata
00316             } else {
00317                 m_root->m_refCount--;
00318             }
00319         }
00320         m_root = o.m_root; // se roba los hijos
00321         o.m_root = 0; // anula al dador
00322     }
00323     return *this;
00324 }
00325 
00326 /** Intercambia los valores de \c "*this" y \c "o".
00327     - Debido a que algunos métodos retornan copias del valor de \c "*this" en
00328       lugar de una referencia, como ocurre con \c Tree::Child(), a veces
00329       \c Swap() no tiene el resultado esperado por el programador.
00330     - Por ejemplo, si se invoca <code> T.Child(i). Swap( T.Child(j) ) </code>
00331       el resultado no es intercambiar los hijos, sino más bien intercambiar
00332       los valores de los sub-árboles temporales \c T.Child(i) y \c T.Child(j).
00333       La forma correcta de intercambiar hijos es usar \c Graft().
00334 
00335       \par Complejidad:
00336          O( \c 1 )
00337 
00338     \returns *this
00339 
00340     \see http://www.di-mare.com/adolfo/binder/c04.htm#sc08 */
00341 template <class E>
00342 inline Tree<E>& Tree<E>::Swap( Tree &o ) {
00343     Tree_Node<E> * tmp = m_root;
00344     m_root = o.m_root;
00345     o.m_root = tmp;
00346     return *this;
00347 }
00348 
00349 /** Acceso al padre.
00350     - Si el sub-árbol no tiene padre retorna el árbol vacío.
00351 
00352     \par Complejidad:
00353          O( <code> Father().Count_Children() </code> ) */
00354 template <class E>
00355 Tree<E> Tree<E>::Father() const {
00356     if (m_root == 0) {
00357         return Tree( );
00358     }
00359 
00360     Tree_Node<E>* p = m_root; // soy el primer hijo de mi padre
00361     while (p->m_n_child > 0) {
00362         p = p->m_right_brother; // se brinca los que no tienen el puntero al padre
00363     }
00364     return Tree( p->m_right_brother );
00365     // para la raíz siempre ocurre que [m_root->m_right_brother == 0] por lo que
00366     // Tree( p->m_right_brother ) produce un árbol vacío
00367 }
00368 
00369 /** Acceso al \c "n"-ésimo hijo.
00370     - Si el sub-árbol no tiene un hijo número \c "n" retorna el sub-árbol vacío.
00371 
00372     \par Complejidad:
00373          O( <code> Father().Count_Children() </code> ) */
00374 template <class E>
00375 Tree<E> Tree<E>::Child( unsigned n ) const {
00376     if (m_root == 0) {
00377         return Tree( );
00378     }
00379 
00380     Tree_Node<E>* child = m_root->m_left_child; // soy el primer hijo de mi padre
00381     if (child == 0) {
00382         return Tree( );
00383     }
00384 
00385     n++; // lo incrementa para evitar incrementar "m_n_child" para cada hijo de "m_root"
00386 
00387     for (;;) {
00388         if (child->m_n_child <= 0) { // es el último hijo
00389             if ( unsigned(- child->m_n_child) == n ) {
00390                 return Tree( (NOT_null_pointer*) child  );
00391             } else {
00392                 return Tree( );
00393             }
00394         } else {            // assert( child->m_n_child > 0 );
00395             if ( static_cast<unsigned>(child->m_n_child) == n ) {
00396                 return Tree( (NOT_null_pointer*) child );
00397             } else if ( unsigned(child->m_n_child) < n) {
00398                 child = child->m_right_brother;
00399             } else { // assert( unsigned(child->m_n_child) > n );
00400                 return Tree( );
00401             }
00402         }
00403     }
00404 }
00405 
00406 /** \typedef Tree::NOT_null_pointer
00407     \brief Truco para evitar comparar con \c 0 ( \c nil )
00408     al usar \c Tree::Tree_Node<E>* para construir \c Tree().
00409 
00410     Al implementar cada uno de los métodos de \c Tree con frecuencia ocurre
00411     que es posible saber que el sub-árbol retornado no está vacío. En estos casos, conviene
00412     usar un contructor que no verifique si la raíz del árbol es nula.
00413 
00414     Esta clase se usa como una marca para que se ejecute el contructor
00415     <code> Tree::Tree(NOT_null_pointer* p) </code>
00416     que no verifica la nulidad de \c "m_root"; esta es una micro-eficiencia, pero aquí sirve
00417     para mostrar un truco que es muy usado en C++ para aumentar la eficiencia de los
00418     programas, pues le permite al programado usar la sobrecarga de operadores para evitar
00419     repetir verificaciones innecesarias.
00420 
00421     \see http://www.di-mare.com/adolfo/binder/c01.htm#k1-micro-eficiencia
00422 */
00423 
00424 /** Sub-árbol izquierdo [en un árbol binario].
00425     - Sinónimo de \c Child(0).
00426     \par Complejidad:
00427          O( \c 1 ) */
00428 template <class E>
00429 inline Tree<E> Tree<E>::Left() const {
00430     if (m_root == 0) {
00431         return Tree( );
00432     } else if ( -1 ==m_root->m_left_child->m_n_child ||
00433                  1 ==m_root->m_left_child->m_n_child ) {
00434         return Tree( (NOT_null_pointer*) m_root->m_left_child );
00435     }
00436     return Tree( );
00437 }
00438 
00439 /** Sub-árbol derecho [en un árbol binario].
00440     - Sinónimo de \c Child(1).
00441 
00442     \par Complejidad:
00443          O( \c 1 ) */
00444 template <class E>
00445 Tree<E> Tree<E>::Right() const {
00446     if (m_root == 0) {
00447         return Tree( );
00448     } else if ( 0 == m_root->m_left_child ) { // no hay hijos
00449         return Tree( );
00450     } else if ( -1 ==m_root->m_left_child->m_n_child ) {
00451         return Tree( ); // sólo está el hijo izquierdo
00452     } else if ( 1 ==m_root->m_left_child->m_n_child ) {
00453         if ( -2 == m_root->m_left_child->m_right_brother->m_n_child  ||
00454               2 == m_root->m_left_child->m_right_brother->m_n_child ) {
00455             return Tree( (NOT_null_pointer*) m_root->m_left_child->m_right_brother  );
00456         }
00457     } else if ( 2 == m_root->m_left_child->m_n_child || -2 == m_root->m_left_child->m_n_child ) {
00458         return Tree( (NOT_null_pointer*) m_root->m_left_child );
00459     }
00460     return Tree( ); // uso 1-2 en lugar de 0-1 porque "m_n_child" contiene "uno más"
00461 }
00462 
00463 /** Obtiene el hermano no vacío anterior, que está hacia la izquierda.
00464     - Si no existe un hermano no vacío hacia la izquierda, retorna un sub-árbol vacío.
00465     - Si <code>n == Child_Number()</code> no necesariamente ocurrirá que
00466       <code> (n-1)== Left_Sibling().Child_Number()</code>
00467       pues los anteriores hijos de \c Father() pueden ser sub-árboles vacíos, como ocurre si
00468       un árbol binario tiene hijo derecho pero no tiene hijo izquierdo.
00469     - Este método usualmente se usa junto con \c Rightmost()
00470 
00471     \par Complejidad:
00472          O( <code> Father().Count_Children() </code> ) */
00473 template <class E>
00474 Tree<E> Tree<E>::Left_Sibling() const {
00475     if (m_root == 0)  {
00476         return Tree( );
00477     }
00478 
00479     unsigned n_child = m_root->Abs_n_child()-1; // assert( n_child >= 0 );
00480     if ( n_child <= 0 ) { // no puede haber un hijo anterior...
00481         return Tree( ); // huye porque no existen hijos antes del primero
00482     }
00483     #ifdef ESTO_SOBRA_en_Left_Sibling
00484         if (m_root->m_right_brother == 0)  { // sólo la raíz tiene en blanco "m_right_brother"
00485             return Tree( ); // la raíz no tiene hermanos
00486         }
00487         // Para el nodo raíz de un árbol [T] el campo [T.m_root->m_right_brother == 0] es nulo
00488         // - Afortunadamente, como [T.m_root->m_n_child == -1], el if(){} anterior retorna
00489         //   el sub-árbol vacío para el nodo raíz del árbol [T].
00490     #endif
00491 
00492     Tree_Node<E>* brother = m_root; // camina sobre los hermanos hasta llegar al padre
00493     while (brother->m_n_child > 0) {
00494         brother = brother->m_right_brother; // se brinca los que no tienen el puntero al padre
00495     }
00496     Tree_Node<E>* father = brother->m_right_brother;
00497     // assert( ! Father().Empty() && Father().Same( Tree( brother ) ) );
00498 
00499     brother = father->m_left_child; // hijo más izquierdo de Father()
00500     if ( m_root == brother ) {
00501         return Tree( ); // ya "m_root" era el hijo más izquierdo
00502     }
00503     while ( m_root != brother->m_right_brother ) {
00504         brother = brother->m_right_brother;
00505     }
00506     // assert( m_root == brother->m_right_brother );
00507     return Tree( brother );
00508 }
00509 
00510 /** Obtiene el hermano no vacío siguiente, que está hacia la derecha.
00511     - Si no existe un hermano hacia la derecha, retorna un sub-árbol vacío.
00512     - Si <code>n == Child_Number()</code> no necesariamente ocurrirá que
00513       <code>(n+1) == Right_Sibling().Child_Number()</code>
00514       pues los siguientes hijos de \c Father() pueden ser sub-árboles vacíos, como ocurre si
00515       un árbol binario tiene hijo izquierdo pero no tiene hijo derecho.
00516     - Este método usualmente se usa junto con \c Leftmost()
00517 
00518     \par Complejidad:
00519          O( \c 1 ) */
00520 template <class E>
00521 Tree<E> Tree<E>::Right_Sibling() const {
00522     if (m_root == 0)  {
00523         return Tree( );
00524     } if (m_root->m_n_child < 0) { // es el último hijo
00525         return Tree( ); // ==> ya no hay dónde más buscar
00526     } else {
00527         return Tree( m_root->m_right_brother );
00528         // sólo la raíz tiene "m_right_brother" en blanco (puntero nulo);
00529         // en ese caso se retorna el árbol vacío.
00530     }
00531 }
00532 
00533 /** Obtiene el hermano que está inmediatamente hacia la izquierda.
00534     - Este método es equivalente a invocar \c Sibling( -1 )
00535     - Si no existe un hermano hacia la derecha, retorna un sub-árbol vacío.
00536 
00537     \par Complejidad:
00538          O( <code> Father().Count_Children() </code> ) */
00539 template <class E>
00540 inline Tree<E> Tree<E>::Left_Sibling_Inmediate() const {
00541     return Sibling( -1 );
00542 }
00543 
00544 /** Obtiene el hermano que está inmediatamente hacia la derecha.
00545     - Este método es equivalente a invocar \c Sibling( +1 )
00546     - Si no existe ese hermano hacia la derecha, retorna un sub-árbol vacío.
00547 
00548     \par Complejidad:
00549          O( \c 1 ) */
00550 template <class E>
00551 Tree<E> Tree<E>::Right_Sibling_Inmediate() const {
00552 //  return Sibling( +1 );
00553     if (m_root == 0)  {
00554         return Tree( );
00555     }
00556     if (m_root->m_n_child <= 0) { // es el último hijo
00557         return Tree( ); // ya no hay hermanos a la derecha
00558     }
00559     // assert( m_root->m_right_brother != 0 ); // pues "(m_root->m_n_child > 0)"
00560     Tree_Node<E>* brother = m_root->m_right_brother;
00561     // assert( brother->Abs_n_child() > 0 ); // pues "brother" está "a la derecha" de "m_root"
00562     int n_brother = brother->Abs_n_child() - 1;
00563     if ( m_root->m_n_child == n_brother ) {
00564         return Tree( (NOT_null_pointer*) brother );
00565     } else {
00566         return Tree( );
00567     }
00568 #if 0
00569     if (brother->m_n_child > 0) {
00570         if ( m_root->m_n_child + 1 == brother->m_n_child ) {
00571             return Tree( (NOT_null_pointer*) brother );
00572         } else {
00573             return Tree( );
00574         }
00575     } else {
00576         if ( m_root->m_n_child + 1 == - brother->m_n_child ) {
00577             return Tree( (NOT_null_pointer*) brother );
00578         } else {
00579             return Tree( );
00580         }
00581     }
00582 #endif
00583 }
00584 
00585 /** Retorna el valor absoluto del campo \c "m_n_child".
00586     - Hay que tomar en cuenta que que \c m_n_child está incrementado en \c +int(1)
00587       porque la marca de "puntero al padre" es un valor negativo, y como hay un hijo número cero
00588       \c int(0), no sería posible marcar como "puntero al padre" a ese nodo
00589     - Esta rutina también existe para documentar el truco del "puntero al padre", pues más directo
00590       habría sido usar la función \c abs() definida en <code> \#include <cstdlib> </code>
00591     - En otras palabras, parte de la invariante de un nodo siempre será que
00592       <code> (m_n_child != 0) </code> porque siempre <code> int(0) == int(-0) </code> */
00593 template <class E>
00594 inline unsigned Tree_Node<E>::Abs_n_child() const {
00595     return ( m_n_child >= 0 ? unsigned(m_n_child) : unsigned( - m_n_child ) );
00596 }
00597 
00598 /** \c "n"-ésimo hermano a partir de \c "*this".
00599     - El hermano puede ser vacío aunque haya otros hermanos que no son vacíos.
00600     - Se "corre" hacia el n-ésimo hermano \c "n" "posiciones".
00601     - El hermano se determina contando sub-árboles hacia la derecha o izquierda de acuerdo
00602       al signo de \c "n":
00603           - Si \c n=0, regresa \c "*this".
00604           - Si \c n>0, regresa el hermano número \c "+n" contando hacia la derecha de \c "*this".
00605           - Si \c n<0, regresa el hermano número \c "-n" contando hacia la izquierda de \c "*this".
00606     - Si no existe un hermano número \c "n" retorna un sub-árbol vacío.
00607     - El árbol \c "T" tiene 3 hijos no vacíos \c "B", \c "C" y \c "E" y tiene 4 sub-árboles:
00608             - <code> C.Sibling( +0 ) == C</code>
00609             - <code> B.Sibling( +1 ) == C</code>
00610             - <code> E.Sibling( -2 ) == C</code>
00611             - <code> E.Sibling( -1 ) --> Vacío</code>
00612             - <code> A.Sibling( +1 ) --> Vacío </code>
00613             - <code> B.Sibling( -1 ) --> Vacío </code>
00614             - <code> E.Sibling( +1 ) --> Vacío </code>
00615         \code
00616            A <-- T
00617           /|\
00618         / / \ \       [] --> es representa un sub-árbol vacío
00619        B C  [] E
00620         \endcode
00621 
00622     \par Complejidad:
00623          O( <code> Father().Count_Children() </code> ) */
00624 template <class E>
00625 Tree<E> Tree<E>::Sibling( int n ) const {
00626     if (m_root == 0)  {
00627         return Tree( );
00628     } else if ( m_root->m_right_brother == 0 ) {
00629         return Tree( );
00630     } else if ( n==0 ) {
00631         return Tree( (NOT_null_pointer*) m_root );
00632     }
00633 
00634     Tree_Node<E>* brother; // desde dónde comenzar a buscar en la lista de hermanos
00635     unsigned n_target; // número de hijo que hay que encontrar: "(m_n_child + n)"
00636 
00637     // averigua "n_target" (hay que manejar el "+1" del "puntero al padre")
00638     if ( n < 0 ) { // a la izquierda ==> busque al padre para comenzar en m_left_child
00639         unsigned n_child = m_root->Abs_n_child()-1; // assert( n_child >= 0 );
00640         unsigned abs_n = unsigned(-n);      // assert( abs_n > 0 );
00641         if ( n_child < abs_n ) { // no se puede hacer la resta porque da un número de hijo negativo
00642             return Tree( ); // se sale pues no existen hijos antes del hijo más izquierdo
00643         } else {
00644             n_target = n_child - abs_n; // como el hermano está hacia la izquierda...
00645             // return Father().Child( n_target ); // ...hay que buscarlo desde el padre
00646             brother = m_root;
00647             while (brother->m_n_child > 0) { // se brinca los que no tienen el puntero al padre
00648                 brother = brother->m_right_brother;
00649             }
00650             brother = brother->m_right_brother->m_left_child; // buscará desde el primer nodo
00651         }
00652     } else { // assert( n > 0 ); // a la derecha ==> busque desde aquí en adelante
00653         brother = m_root;
00654         n_target = unsigned(n) + m_root->Abs_n_child()-1;  // assert( (n > 0) && (n_target > m_n_child) );
00655     }
00656 
00657     // hay que manejar el "+1" del "puntero al padre" en "n_target"
00658     ++n_target; // para no tener que restarle int(1) a "child->m_n_child"
00659 
00660     // avance hacia la derecha en busca del hermano "n_target"
00661     // assert( brother != 0 );
00662     for (;;) {
00663         if (brother->m_n_child < 0) { // es el último hijo
00664             if ( unsigned(- brother->m_n_child)  == n_target ) {
00665                 return Tree( (NOT_null_pointer*) brother );
00666             } else {
00667                 return Tree( ); // esa era el último ==> ya no hay dónde más buscar
00668             }
00669         } else {
00670             unsigned n_child = brother->m_n_child;
00671             if (n_child == n_target) { // lo encontró
00672                 return Tree( (NOT_null_pointer*) brother );
00673             } else if (n_child < n_target) { // siga buscando...
00674                 brother = brother->m_right_brother;
00675             } else { // if (n_child > n_target) // ya se lo brincó; no está
00676                 return Tree( );
00677             }
00678         }
00679     }
00680 }
00681 
00682 /** Obtiene el hijo más izquierdo del árbol.
00683     - Este método usualmente se usa junto con \c Right_Sibling()
00684 
00685     \par Complejidad:
00686          O( \c 1 )
00687 
00688     \remark Esta es una forma de procesar los hijos no vacíos de un sub-árbol de izquierda a derecha:
00689 
00690     \code
00691     Tree<E> Child = T.Leftmost();
00692     while ( ! Child.Empty() ) {
00693         Process( Child );
00694         Child = Child.Right_Sibling();
00695     }
00696     \endcode */
00697 template <class E>
00698 inline Tree<E> Tree<E>::Leftmost() const {
00699     if (m_root == 0)  {
00700         return Tree( );
00701     }
00702     return Tree( m_root->m_left_child ); // puede ser el puntero nulo
00703 }
00704 
00705 /** Obtiene el hijo más derecho del árbol.
00706     - Este método usualmente se usa junto con \c Left_Sibling()
00707 
00708     \par Complejidad:
00709          O( <code> Count_Children() </code> )
00710 
00711     \remark Esta es una forma de procesar los hijos no vacíos de un sub-árbol de derecha a izquierda:
00712 
00713     \code
00714     Tree<E> Child = T.Rightmost();
00715     while ( ! Child.Empty() ) {
00716         Process( Child );
00717         Child = Child.Left_Sibling();
00718     }
00719     \endcode */
00720 template <class E>
00721 Tree<E> Tree<E>::Rightmost() const {
00722     if (m_root == 0) {
00723         return Tree( );
00724     }
00725     Tree_Node<E>* child = m_root->m_left_child; // soy el primer hijo de mi padre
00726     if (child == 0) {
00727         return Tree( );
00728     }
00729 
00730     while (child->m_n_child > 0) { // todavía no se ha llegado al último hijo
00731         child = child->m_right_brother;
00732     }
00733     return Tree( (NOT_null_pointer*) child );
00734 }
00735 
00736 /** Implementación recursiva para \c Count().
00737     - Incrementa \c "n" en el número de hijos que tiene el sub-árbol cuya raíz es \c "p"
00738     - Cambia el valor de \c "n"
00739     - No cuenta el nodo raíz \c "p"
00740     - Esta función complementa a \c Count()
00741 
00742     \pre p != 0 */
00743 template <class E>
00744 void Tree<E>::Count0(const Tree_Node<E> * p, unsigned & n) {
00745     Tree_Node<E>* child = p->m_left_child; // soy el primer hijo de mi padre
00746     if (child == 0) {
00747         return;
00748     }
00749 
00750     for (;;) {
00751         ++n; // cuenta a este hijo
00752         Count0( child, n );
00753         if (child->m_n_child > 0) { // todavía no se ha llegado al último hijo
00754             child = child->m_right_brother;
00755         } else {
00756             break;
00757         }
00758     }
00759 }
00760 
00761 /** Retorna la cantidad de valores almacenados en el sub-árbol.
00762     - Calcula el número de sub-árboles no vacíos del árbol
00763 
00764     \par Complejidad:
00765          O( \c Count() ) ==> tiempo <br>
00766          O( \c Height() ) ==> espacio
00767 
00768     \see http://www.di-mare.com/adolfo/binder/c05.htm#sc03 */
00769 template <class E>
00770 unsigned Tree<E>::Count() const {
00771     if (m_root == 0) {
00772         return 0;
00773     } else {
00774         unsigned n = 1; // comienza contando en uno...
00775         Count0(m_root, n); // ... porque Count0() no cuenta la raíz
00776         return n;
00777     }
00778 }
00779 
00780 /** Retorna la cantidad de hijos del árbol.
00781     \par Complejidad:
00782          O( \c Count_Children() ) */
00783 template <class E>
00784 unsigned Tree<E>::Count_Children() const {
00785     if (m_root == 0) {
00786         return 0;
00787     }
00788     Tree_Node<E>* child = m_root->m_left_child;
00789     if ( 0 == child ) { // no hay hijos
00790         return 0;
00791     }
00792     unsigned tot = 0;
00793     for (;;) {
00794         ++tot; // cuenta a este hijo
00795         if (child->m_n_child > 0) { // todavía no se ha llegado al último hijo
00796             child = child->m_right_brother;
00797         } else {
00798             break;
00799         }
00800     }
00801     return tot;
00802 }
00803 template <class E>
00804 inline bool operator == (const Tree<E> &p, const Tree<E> &q) { return Tree<E>::Comp0(p.m_root, q.m_root); }
00805 template <class E>
00806 inline bool operator != (const Tree<E> &p, const Tree<E> &q) { return !(p == q); }
00807 
00808 /// Compara recursivamente los árboles cuyos nodo raíz son \c "*p" y \c "*q".
00809 /// - Implementación recursiva para <code> operator==(Tree, Tree) </code>.
00810 template <class E>
00811 bool Tree<E>::Comp0(const Tree_Node<E> *p, const Tree_Node<E> *q) {
00812     if (p == q) {
00813         return true;
00814     }
00815     if ( (p==0) || (q==0)) { // son diferentes...
00816         return false; // ...pues sólo 1 está vácio
00817     }
00818     if ( p->m_n_child != q->m_n_child ) {
00819         return false; // números de hijo diferentes
00820     }
00821     if ( ! (p->m_data == q->m_data) ) {
00822         return false; // valor diferente en la raíz
00823     }
00824 
00825     // A comparar a todos los hijos
00826     p = p->m_left_child;
00827     q = q->m_left_child;
00828     for (;;) {
00829         if (p == q) { // como se terminaron juntos...
00830             return true; // ...son iguales
00831         }
00832         if ( (p==0) || (q==0) ) { // son diferentes...
00833             return false; // ...pues sólo 1 está vácio
00834         }
00835         if ( p->m_n_child != q->m_n_child ) {
00836             return false; // números de hijo diferentes
00837         }
00838         if (! Comp0(p, q) ) {
00839             return false;  // recorrido recursivo
00840         }
00841         if ( p->m_n_child < 0 ) { // assert( q->m_n_child < 0 );
00842             return true; // ya no hay más hermanos
00843         }
00844         p = p->m_right_brother;
00845         q = q->m_right_brother;
00846     }
00847 }
00848 
00849 /**   Verifica que se cumpla la invariante de la clase, o sea, que el objeto esté bien construido.
00850       - La razón por la que esta función no es un método es continuar la costumbre de muchos
00851         programadores quienes no definen la invariante para sus clases, pues en muchos
00852         casos sobra hacerlo.
00853       - No invoca \c check_ok( value_type& ) para cada valor almacenado, aunque si el árbol
00854         cumple con su invariante necesariamentes es porque también sus elementos almacenados
00855         están bien construidos.
00856       - Esta función en general es difícil de implementar, y en algunos casos es imposible
00857         pues, cuando el objeto no está bien construido, puede ocurrir que la función no
00858         retorne (como ocurriria si un nodo interno del árbol apunta de vuelta a la raíz, lo
00859         que se resulta en un círculo).
00860       - En general, la implementáción de esta función no es completa pues hay casos en que
00861         es imposible verificar la invariante de una clase.
00862 
00863     \par Complejidad:
00864          O( \c Count() ) ==> tiempo <br>
00865          O( \c Height() ) ==> espacio
00866 
00867          \post Retorna \c "true" si el árbol es un objeto bien construido
00868       \see \c check_ok(Tree&)
00869 
00870     \see http://www.di-mare.com/adolfo/binder/c04.htm#sc11 */
00871 template <class E>
00872 bool check_ok(const Tree<E>& T) {
00873 
00874     if ( T.Empty() ) {
00875         return true;
00876     }
00877 
00878     #ifdef NO_Implementado_para_evitar_forzar_que_el_valor_almacenado_tenga_su_metodo_OK
00879         if (! check_ok( T.Data() ) ) { // si el valor almacenado no esta bien...
00880             return false; //... tampoco lo está el árbol
00881         }
00882         /* Usar la función check_ok(Tree::value_type en lugar del método
00883         Tree::value_type::Ok() evitar forzar a que los programadores clientes
00884         que usen árboles estén obligados a implementar el método
00885         Tree::value_type::Ok(), que se encarga de verificar la invariante del valor
00886         almacenado en le árbol.
00887         - Lindo: if (! check_ok( T.Data() ) ) //.... la función check_ok() es opcional
00888         - ¡FEO!: if (! T.Data().Ok() ) //... pues obliga a que exista el método value_type::Ok()
00889         */
00890     #endif
00891 
00892     unsigned N = T.Rightmost().Child_Number();
00893     for (unsigned i = 0; i < N; ++i) {
00894         if ( T.Child(i).Empty() ) { // este hijo no existe
00895             // continue; // con el siguiente
00896         }
00897         else if ( T.Child(i).Father() != T.Root() ) { // ==> ! T.Father.Empty()
00898             return false; // parece que este hijo no es mi hijo...
00899         }
00900         else if ( i != T.Child(i).Child_Number() ) {
00901             return false; // no estoy registrado como el i-ésimo hijo de mi padre
00902         }
00903         else if ( T.Child(i).Father().Child( i ) != T.Child( i ) ) {
00904             return false; // no estoy registrado como el i-ésimo hijo de mi padre
00905         }
00906         else if ( ! check_ok( T.Child(i) ) ) {
00907             return false; // hijo roto...
00908         }
00909     }
00910     return true;
00911 
00912     // Las siguientes relaciones lógicas se cumplen
00913     // [ ! T.Empty() ]                    ==> [ T.Root()!= Tree() ]
00914     // [ T.Child(i).Father() == T.Root()] ==> [ ! T.Father.Empty() ]
00915 
00916     /* Si este método retorna es porque el árbol está bien construido. Sin embargo,
00917        una invocación a check_ok() con un árbol mal construido posiblemente nunca retorne.
00918     */
00919 }
00920 
00921 
00922 /// Sustituye por \c "d" el valor almacenado en la raíz del árbol.
00923 /// - Si el árbol está vacío, le agrega el nodo raíz.
00924 /// \returns \c *this
00925 template <class E>
00926 Tree<E> Tree<E>::Change_Root(const value_type & d) {
00927     if (m_root == 0) { // como el árbol está vacío hay que agregarle la raíz
00928         m_root = Tree_Node<E>::Get_New(d); // crea el nodo raíz
00929         m_root->m_left_child = 0;
00930         m_root->m_right_brother = 0;
00931         m_root->m_n_child = -1;
00932     } else { // como no hay más referencias....
00933         m_root->m_data = d; // ... cambia el valor directamente
00934     }
00935     return *this;
00936 }
00937 
00938 /** Sustituye por \c "d" el valor almacenado en el hijo número \c "n" del árbol.
00939     - Si no existe el hijo número \c "n", lo agrega como una hoja con valor \c "d"
00940     - Si ya existe el hijo número \c "n", le sustituye su valor por \c "d"
00941 
00942     \pre <code> !Empty() && (0 <= n) && (n < \e infinito) </code>
00943 
00944     \par Complejidad:
00945          O( \c Count_Children() )
00946 
00947     \returns <code> Child(n) </code>  */
00948 template <class E>
00949 Tree<E> Tree<E>::Change_Child(unsigned n, const value_type &d) {
00950     if (m_root == 0) { // ignora árboles vacíos
00951         return Tree( );
00952     }
00953 
00954     n++; // evita incrementar "m_n_child" en cada iteración
00955 
00956     if (m_root->m_left_child == 0) { // Hay que agregar un sub-árbol nuevo
00957         Tree_Node<E> * p = Tree_Node<E>::Get_New(d);
00958         p->m_n_child = -int(n);
00959         p->m_right_brother = m_root;
00960         m_root->m_left_child = p;
00961         p->m_left_child = 0;
00962         return Tree ( (NOT_null_pointer*) m_root->m_left_child );
00963     }
00964 
00965     // assert( m_root->m_left_child != 0 );
00966     Tree_Node<E>* brother = m_root->m_left_child;
00967     unsigned n_brother =  brother->Abs_n_child();
00968 
00969     if ( n < n_brother ) { // Hay que crear Child(n) y ponerlo de primero
00970         Tree_Node<E>* p = Tree_Node<E>::Get_New(d);
00971         p->m_n_child = +int(n);
00972         p->m_right_brother = brother;
00973         m_root->m_left_child = p;
00974         p->m_left_child = 0;
00975         return Tree ( (NOT_null_pointer*) p );
00976     } else if ( n == n_brother ) {
00977         brother->m_data = d; // le cae encima al valor anterior
00978         return Tree ( (NOT_null_pointer*) brother );
00979     }
00980 
00981     // Child(n) no es el primer hijo de "m_root"
00982     // assert( m_root->m_left_child != Child(n).m_root );
00983 
00984     // assert( n_brother < n); // se corre hacia la derecha para encontrar "Child(n)"
00985 
00986     Tree_Node<E>* prev = brother;
00987     for (;;) {
00988         if ( brother->m_n_child < 0 ) {
00989             if ( int(n) ==  - brother->m_n_child ) {
00990                 brother->m_data = d; // le cae encima al valor anterior
00991                 return Tree ( (NOT_null_pointer*) brother );
00992             } else if (int(n) <  - brother->m_n_child ) {
00993                 Tree_Node<E>* p = Tree_Node<E>::Get_New(d); // ... [d] ==> [brother] ==> end
00994                 p->m_n_child = int(n);
00995                 p->m_right_brother = brother;
00996                 prev->m_right_brother = p;
00997                 p->m_left_child = 0;
00998                 return Tree ( (NOT_null_pointer*) p );
00999             } else {
01000                 Tree_Node<E>* p = Tree_Node<E>::Get_New(d); // ... [brother] ==> [d] ==> end
01001                 p->m_n_child = - int(n);
01002                 p->m_right_brother = brother->m_right_brother;
01003                 brother->m_n_child = - brother->m_n_child; // ahora el último es [d]
01004                 brother->m_right_brother = p;
01005                 p->m_left_child = 0;
01006                 return Tree ( (NOT_null_pointer*) p );
01007             }
01008         } else { // assert( brother->m_n_child > 0 );
01009             if ( int(n) ==  brother->m_n_child ) {
01010                 brother->m_data = d; // le cae encima al valor anterior
01011                 return Tree ( (NOT_null_pointer*) brother );
01012             } else if ( brother->m_n_child < int(n) ) {
01013                 prev = brother;
01014                 brother = brother->m_right_brother;
01015             } else { // como se acaba de pasar ==> hay que agregarlo después de "prev"
01016                 Tree_Node<E>* p = Tree_Node<E>::Get_New(d);
01017                 p->m_n_child = int(n); // como "brother" no es el último, tampoco lo será "p"
01018                 p->m_right_brother = brother;
01019                 prev->m_right_brother = p;
01020                 p->m_left_child = 0;
01021                 return Tree ( (NOT_null_pointer*) p );
01022             }
01023         }
01024     }
01025 }
01026 
01027 /** Sustituye por \c "d" el valor almacenado en el hermano inmediatamente anterior del sub-árbol.
01028     - Si <code> n == Child_Number() </code> cambia el valor
01029       del hijo número \c "n-1" de \c Father()
01030     - Si no existe el hijo número \c "n-1" de \c Father() lo agrega como
01031       una hoja con valor \c "d"
01032     - Si ya existe ese hijo número \c "n-1", le sustituye su valor por \c "d"
01033     - Retorna un árbol vacío si no es posible que exista el hijo número \c "n-1" de \c Father()
01034 
01035     \pre <code> !Empty() && (1 <= Child_Number()) </code>
01036 
01037     \par Complejidad:
01038          O( <code> Father().Count_Children() </code> )
01039 
01040     \returns El hermano izquierdo, <code> Sibling(-1) </code> */
01041 template <class E>
01042 Tree<E> Tree<E>::Change_Left_Sibling_Inmediate( const E &d ) {
01043     unsigned n = Child_Number();
01044     if (n > 0 ) {
01045         return Father().Change_Child( n-1, d );
01046     } else {
01047         return Tree( );
01048     }
01049 }
01050 
01051 /** Sustituye por \c "d" el valor almacenado en el hermano inmediatamente posterior del sub-árbol.
01052     - Si <code> n == Child_Number() </code> cambia el valor
01053       del hijo número \c "n+1" de \c Father()
01054     - Si no existe el hijo número \c "n+1" de \c Father() lo agrega como
01055       una hoja con valor \c "d"
01056     - Si ya existe ese hijo número \c "n+1", le sustituye su valor por \c "d"
01057     - Retorna un árbol vacío si no es posible que exista el hijo número \c "n+1" de \c Father()
01058 
01059     \pre <code> !Empty() && ( Child_Number() < \e infinito ) </code>
01060 
01061     \par Complejidad:
01062          O( \c 1 )
01063 
01064     \returns El hermano derecho, <code> Sibling(+1) </code> */
01065 template <class E>
01066 Tree<E> Tree<E>::Change_Right_Sibling_Inmediate( const value_type &d ) {
01067     if (m_root == 0) {
01068         return Tree( );
01069     }
01070     if ( m_root->m_right_brother == 0 ) { // es la raíz del árbol y por eso no tiene hermanos
01071         return Tree( );
01072     }
01073 
01074     Tree_Node<E> * brother;
01075     if ( m_root->m_n_child < 0 ) { // "*this" es el último hijo
01076         m_root->m_n_child = - m_root->m_n_child; // ya "m_root" no es el último hijo
01077 
01078         brother = Tree_Node<E>::Get_New( d );
01079         brother->m_n_child = - ( m_root->m_n_child + 1 ); // "brother" es el último hijo
01080 
01081         brother->m_left_child = 0;
01082         brother->m_right_brother = m_root->m_right_brother;
01083         m_root->m_right_brother = brother;
01084 
01085         return Tree( (NOT_null_pointer*) brother );
01086     }
01087 
01088     // assert( m_root->m_n_child > 0 );
01089     int n_brother = m_root->m_right_brother->Abs_n_child();
01090     if ( m_root->m_n_child + 1 == n_brother ) {
01091         m_root->m_right_brother->m_data = d;
01092         return Tree( (NOT_null_pointer*) m_root->m_right_brother );
01093     } else {
01094         brother = Tree_Node<E>::Get_New( d );
01095         brother->m_n_child = m_root->m_n_child + 1; // "brother" no puede ser el último hijo
01096 
01097         brother->m_left_child = 0;
01098         brother->m_right_brother = m_root->m_right_brother;
01099         m_root->m_right_brother = brother;
01100 
01101         return Tree( (NOT_null_pointer*) brother );
01102     }
01103 }
01104 
01105 /** Elimina recursivamente a \c "*p" y a todos sus descendientes.
01106     - Implementación recursiva para \c Erase()
01107     - Borra el nodo sólo después de que constata que ya no hay punteros que le apunten
01108     - No saca a \c "*p" de la lista de hijos del padre ==> ese es el trabajo
01109       de \c Graft() o \c Erase()
01110     - La rutina llamadora invoca \c Erase0() porque sabe que al decrementar
01111       \c "p->m_refCount" queda en cero
01112     - No decrementa \c "p->m_refCount" porque ya el invocador sabe que hay que destruir \c "*p"
01113     - Recursivamente, borra a los descendientes de \c "*p"
01114 
01115     \code
01116     // Forma usual de invocación
01117     if ( child->m_refCount <= 1 ) { // Ya no hay más referencias a "child"
01118         Erase0( child ); // lo elimina
01119     } else {
01120         child->m_refCount--; // uno menos le apunta
01121         child->m_n_child = -1;
01122         child->m_right_brother = 0; // ya no es hijo de nadie
01123     }
01124     \endcode
01125 
01126     \pre <code> (p != 0) && (p->m_refCount == 1) </code>
01127     \post No cambia \c "p" porque trabaja con una copia de su valor  */
01128 template <class E>
01129 void Tree<E>::Erase0( Tree_Node<E> * p ) {
01130     // assert( p != 0 );
01131     // assert( p->m_refCount == 1 );
01132 
01133     // Primero hay que matar hijos...
01134     if ( p->m_left_child != 0 ) {
01135         Tree_Node<E> *next, *child = p->m_left_child;
01136         while ( child != 0 ) { // como hay hijos, decide a a cuáles matar
01137             if ( child->m_n_child < 0 ) {
01138                 next = 0; // lo obliga a salir porque "child" es el último
01139             } else {
01140                 next = child->m_right_brother; // recuerda quién es el siguiente
01141             }
01142             if ( child->m_refCount == 1 ) {
01143                 Erase0( child ); // lo mata porque ésta es la última referencia
01144                 // OJO: "child" está destruido ==> "child->m_right_brother" es un error
01145             } else {
01146                 child->m_refCount--; // ya "*p" no le apunta
01147                 child->m_n_child = -1; // ya no tiene padre porque "*p" va a morir
01148                 child->m_right_brother = 0; // ni tampoco tiene hermanos
01149             }
01150             child = next; // hay que evitar usar "child->m_right_brother" si "child" ya está destruido
01151         }
01152     }
01153     #ifdef USE_v_Alive
01154         // Elimina a "p" de m_v_Alive[]
01155         for (unsigned j = 0; j < Tree_Node<E>::N_Alive; ++j) {
01156             if (p == Tree_Node<E>::m_v_Alive[j]) { // busca hasta que encuentra al puntero
01157                 break;
01158             }
01159         }
01160         if (j < Tree_Node<E>::N_Alive) { // sí lo encontró
01161             for (unsigned k = j; k < Tree_Node<E>::N_Alive-1; ++k) { // corre a los demás para atrás
01162                 Tree_Node<E>::m_v_Alive[k] = Tree_Node<E>::m_v_Alive[k+1];
01163             }
01164             Tree_Node<E>::m_n_Alive--; // ahora hay uno menos
01165             Tree_Node<E>::m_v_Alive[ Tree_Node<E>::m_n_Alive ] = 0;
01166         } else {
01167             for (unsigned k = 0; k<3; ++j) { // marca "feos" los del final
01168                 Tree_Node<E>::m_v_Alive[Tree_Node<E>::N_Alive-1-k] = (Tree::Tree_Node<E> *)(-1);
01169             }
01170         }
01171     #endif
01172     // Después de matar a los hijos, mata al nodo...
01173     delete p; // ... porque esta es la última referencia
01174 }
01175 
01176 /** Elimina el árbol y sus descendientes.
01177     \par Complejidad:
01178          O( \c Count() ) + O( <code> Father().Count() </code> ) ==> tiempo <br>
01179          O( \c Height() ) ==> espacio
01180 
01181     \see http://www.di-mare.com/adolfo/binder/c04.htm#sc03  */
01182 template <class E>
01183 void Tree<E>::Erase() {
01184     if (m_root == 0) {
01185         return;
01186     }
01187 
01188     // Encuentra el padre de "m_root"
01189     Tree_Node<E>* brother = m_root; // camina sobre los hermanos hasta llegar al padre
01190     while (brother->m_n_child > 0) {
01191         brother = brother->m_right_brother; // se brinca los que no tienen el puntero al padre
01192     }
01193     Tree_Node<E>* father = brother->m_right_brother;
01194     // assert( Father().Same( Tree( brother ) ) );
01195 
01196     // Desconecta a "m_root" de la lista de hijos del padre
01197     if (father == 0) { // sólo la raíz tiene en blanco el puntero "m_right_brother"
01198         // no hay que desenlazar a la raíz porque nunca está en una lista de hermanos
01199     } else {
01200         // busca al "nodo anterior" para sacar a "m_root" de la lista de sus hermanos
01201         if ( m_root == father->m_left_child ) { // "m_root" es el hijo más izquierdo
01202             if ( m_root->m_n_child < 0 ) {
01203                 father->m_left_child = 0; // elimina la lista de hijos porque "m_root" no tiene hermanos
01204             } else {
01205                 father->m_left_child = m_root->m_right_brother; // desenlaza al primer hijo
01206             }
01207         } else {
01208             brother = father->m_left_child; // hijo más izquierdo de Father()
01209             while ( m_root != brother->m_right_brother ) {
01210                 brother = brother->m_right_brother;
01211             }
01212             brother->m_right_brother = m_root->m_right_brother; // saca a  "m_root" de la lista de hermanos
01213         }
01214     }
01215 
01216     // ahora ya puede detruir al nodo
01217     if ( m_root->m_refCount == 1 ) {
01218         Erase0(m_root);  // mata al nodo porque ésta es la última referencia
01219     } else {
01220         m_root->m_refCount--; // lo va a desconectar de "m_root"
01221         m_root->m_n_child = -1; // ya no tiene padre
01222         m_root->m_right_brother = 0; // ni tampoco tiene hermanos
01223     }
01224     m_root = 0;
01225 }
01226 
01227 // Esta documentación para Tree::Erase_Son() aparece acá porque Doxygen no permite
01228 // incluir un párrafo aparte "\par" en la documentación de 1 sólo renglón.
01229 
01230 /** \fn void Tree::Erase_Son(unsigned n)
01231 
01232     \brief Elimina el sub-árbol número \c "n"
01233 
01234     \par Complejidad:
01235          O( <code> Child(n).Count() </code> ) ==> tiempo <br>
01236          O( <code> Height( Child(n) )  </code> ) ==> espacio
01237 */
01238 
01239 /** Elimina el sub-árbol número \c "n-1" y retorna un puntero al nodo anterior al borrado.
01240     - Esta es la rutina que en realidad hace el trabajo de \c Erase_Son().
01241     - Elimina el sub-árbol número \c "n-1", como también lo hace \c Erase_Son().
01242     - La única diferencia con \c Erase_Son() es que este método retorna un puntero
01243       al nodo anterior al nodo eliminado.
01244     - "prev" apunta al nodo que está antes de "prev" en el árbol.
01245     - Trabaja con \c "n-1" porque no incrementa el valor de \c "n", pues se supone que
01246       la rutina invocadora ya hizo ese ajuste en el valor originar de \c "n".
01247     - Esta rutina existe para compartir el código que se necesita para implementar
01248       \c Erase_Son() y \c Graft().
01249     - Si retorna <code> 0 == NULL </code> es porque <code> Nodo[n-1] </code>
01250       debe ser el primero en la lista de hijos del padre.
01251 
01252     \remark [Eliminado porque ya no hace falta]
01253     - "prev_prev" apunta al nodo que está antes de "prev" en el árbol.
01254     - Si "prev" y "prev_prev" son la misma variable, el valor correcto para "prev" es
01255       calculado. */
01256 template <class E>
01257 void Tree<E>::Erase_Son_Prev(unsigned n, Tree_Node<E>* & prev /*, Tree_Node<E>* & prev_prev */) {
01258     // prev_prev = 0; // el que está "antes" de "prev"
01259     prev = 0; // nodo que antecede a "child"
01260     if (m_root == 0) { // ignora árboles vacíos
01261         return;
01262     }
01263     Tree_Node<E>* child = m_root->m_left_child; // "child" es el nodo que hay que eliminar
01264     if ( child == 0 ) { // no hay hijos ==> el Nodo[n] es un sub-árbol vacío
01265         return;
01266     }
01267 
01268     // n++; // sobra, porque la rutina invocadora ya ajustó el valor a cotejar con "m_n_child"
01269 
01270     // camina sobre los hermanos hasta llegar a Nodo[n]
01271     if ( child->m_n_child <= 0 ) { // sólo hay un hijo
01272         unsigned n_child = - child->m_n_child;
01273         if ( n == n_child ) { // es el único hijo y hay que eliminarlo
01274             if ( child->m_refCount <= 1 ) { // aquí saca a "child" de la lista de hijos de "m_root"
01275                 Erase0( child );
01276             } else {
01277                 child->m_refCount--;
01278                 child->m_n_child = -1;
01279                 child->m_right_brother = 0; // ya no es hijo de nadie
01280             }
01281             m_root->m_left_child = 0;
01282             return;
01283         } else { // no hace falta eliminar a nadie pues Child(n) es un sub-árbol vacío
01284              // hay que determinar adónde debe apuntar "prev"
01285             if ( n > n_child ) {
01286                 // prev_prev = prev;
01287                 prev = child;
01288                 return; // porque el n-ésimo hijo estará después de "child"
01289             } else { // assert( n < n_child );
01290                 return; // el n-ésimo hijo quedará de primero en la lista de hijos del padre
01291             }
01292         }
01293     }
01294 
01295     // assert( (child->m_n_child > 0) && (Count_Children() > 1) );
01296     for (;;) {
01297         if (child->m_n_child <= 0) { // hay que eliminar el último hijo
01298             if ( unsigned(- child->m_n_child) == n ) { // assert( prev != 0 );
01299                 prev->m_right_brother = child->m_right_brother;
01300                 prev->m_n_child = - prev->m_n_child;  // este es el nuevo último
01301                 if ( child->m_refCount <= 1 ) {
01302                     Erase0( child );
01303                 } else {
01304                     child->m_refCount--;
01305                     child->m_n_child = -1;
01306                     child->m_right_brother = 0; // ya no es hijo de nadie
01307                 }
01308             } else if ( unsigned(- child->m_n_child) < n ) {
01309                 // no encontró al hermano con m_n_child == n
01310                 // prev_prev = prev;
01311                 prev = child;
01312             }
01313             break;
01314         } else if ( unsigned(child->m_n_child) == n ) {
01315             if ( prev == 0 ) {
01316                 m_root->m_left_child = child->m_right_brother;
01317             } else {
01318                 prev->m_right_brother = child->m_right_brother;
01319             }
01320             if ( child->m_refCount <= 1 ) {
01321                 Erase0( child );
01322             } else {
01323                 child->m_refCount--;
01324                 child->m_n_child = -1;
01325                 child->m_right_brother = 0; // ya no es hijo de nadie
01326             }
01327             break;
01328         } else if ( unsigned(child->m_n_child) < n) {
01329             // prev_prev = prev;
01330             prev = child;
01331             child = child->m_right_brother;
01332         } else { // assert( unsigned(child->m_n_child) > n );
01333             break; // no encontró al hermano con m_n_child == n
01334         }
01335     }
01336 }
01337 
01338 /**   Verifica que se cumpla la invariante de la clase, o sea, que el objeto esté bien construido.
01339       - Además de todo el trabajo que hace \c check_ok(Tree& T), acá hay que constatar que
01340         el nodo raíz no tiene padre, que es la diferencia fundamental entre un árbol y un sub-árbol
01341 
01342       \post Retorna \c "true" si el árbol es un objeto bien construido
01343 
01344       \deprecated Los árboles y los sub-árboles son la misma cosa.
01345 
01346       \see \c check_ok(Tree&)  */
01347 template <class E>
01348 inline bool check_ok_Tree(Tree<E>& T) {
01349     if ( T.Root().Empty() ) {
01350         return true;
01351     } else {
01352         return ( T.Root().Father().Empty() ) && check_ok( Tree<E> (T) );
01353     }
01354 }
01355 
01356 /** Hace una copia profunda nodo por nodo del árbol cuyo nodo raíz es \c "*p".
01357     - Implementación recursiva para \c Tree::Copy_Deep()
01358     - No altera \c p->m_refCount porque copia los nodos
01359     - El campo \c p->m_right_brother queda con basura porque no queda inicializado
01360     - Le corresponde a la rutina invocadora inicializar \c p->m_right_brother
01361 
01362     \pre <code> p != 0 </code>
01363     \post No cambia \c "p" porque trabaja con una copia de su valor
01364 
01365     \returns Puntero al nodo raíz del árbol copiado */
01366 template <class E>
01367 Tree_Node<E> * Tree<E>::Copy_Deep0(const Tree_Node<E> * p) {
01368     Tree_Node<E> * q; // resultado
01369     q = Tree_Node<E>::Get_New(p->m_data); // m_refCount = 1;
01370     q->m_n_child = p->m_n_child;
01371 
01372     if ( p->m_left_child == 0 ) {
01373         q->m_left_child = 0;
01374     } else { // cuando hay hijos los copia
01375         Tree_Node<E> * pChild = p->m_left_child;
01376         Tree_Node<E> * qChild = Copy_Deep0( pChild ); // copia el primer nodo
01377         q->m_left_child = qChild;
01378         while ( pChild->m_n_child > 0 ) {
01379             pChild = pChild->m_right_brother;
01380             qChild->m_right_brother = Copy_Deep0( pChild );
01381             qChild = qChild->m_right_brother;
01382         }
01383         qChild->m_right_brother = q; // "q" es el padre de todos
01384     }
01385     return q;
01386 }
01387 
01388 /** Copia profunda de \c "o".
01389     - Copia todo el valor de \c "o" sobre \c "*this", de forma que el nuevo valor de
01390       \c "*this" sea un duplicado exacto del valor de \c "o"
01391     - El valor anterior de \c "*this" se pierde
01392     - El objeto \c "o" mantiene su valor anterior
01393     - Luego de la copia, cuando el valor de \c "o" cambia, el de \c "*this" no cambiará,
01394       y viceversa, pues la copia es una copia profunda; no es superficial
01395     - Si \c "*this" es \c "o" entonces su valor no cambia
01396     - Después de esta operación siempre ocurre que <code> *this == o </code>
01397 
01398     \par Complejidad:
01399          O( \c Count() ) + O( \c o.Count() )
01400 
01401     \returns \c *this
01402 
01403     \see http://www.di-mare.com/adolfo/binder/c04.htm#sc05 */
01404 template <class E>
01405 Tree<E>& Tree<E>::Copy_Deep(const Tree &o) {
01406     // Borra el valor actual
01407     if (m_root != 0) {
01408         if ( m_root->m_refCount == 1 ) { // como es el último...
01409             Erase0(m_root); // ...lo mata
01410         } else {
01411             m_root->m_refCount--;
01412         }
01413     }
01414 
01415     // Hace la copia desde "o"
01416     if (o.m_root != 0 ) {
01417         m_root = Copy_Deep0( o.m_root );
01418         m_root->m_n_child = -1; // es el nodo raíz
01419         m_root->m_right_brother = 0;
01420         m_root->m_refCount = 1;
01421     } else {
01422         m_root = 0;
01423     }
01424     return *this;
01425 }
01426 
01427 /** Injerta \c "o" para que sea el \c "n"-ésimo hijo de \c "*this".
01428     - Si \c "o" es sub-árbol de otro árbol, dejara de serlo para pasar ser hijo de \c "*this"
01429     - Si \c "*this" tiene un \c "n"-ésimo hijo, ese hijo desaparece
01430     - Si \c "o" está vacío, elimina el \c "n"-ésimo hijo del árbol [<code> Erase_Son(n) </code>]
01431 
01432     \pre
01433     - <code> ! Root().Empty() </code>
01434        - Si el  árbol está vacío no tiene raíz, y por lo tanto tampoco puede tener hijos
01435     - <code> ! Ancestor(o, *this) </code>
01436        - "o" no puede ser ancestro de *this"
01437     - <code> (0 <= n) && (n < \e infinito) </code>
01438     - <code> ! Root(). Same( o.Root() ) </code>
01439 
01440     \post
01441     - \c "o" deja de ser sub-árbol del árbol en que estaba
01442     - <code> o.Father() .Same( Root() ) </code>
01443 
01444     \remarks
01445     - Un sub-árbol puede ser hijo (o sub-árbol) de otro árbol
01446     - Un sub-árbol puede ser hijo únicamente de un árbol
01447     - Este método no hace nada cuando [ <code> ! Root() .Same( o.Root() ) </code> ]
01448     - Injertar un sub-árbol vacío es una forma de eliminar a un hijo junto con
01449       toda su descendencia
01450 
01451     \returns "o" ==> El árbol recién injertado
01452 
01453     \par Complejidad::
01454          O( \c Count_Children() ) + O( <code> o.Father().Count_Children() </code> ) */
01455 template <class E>
01456 Tree<E> Tree<E>::Graft(unsigned n, Tree &o) {
01457     if (m_root == 0) { // ignora árboles vacíos
01458         return Tree( );
01459     }
01460     if (m_root == o.m_root) { // evita auto-borrado
01461         return *this;
01462     }
01463     #ifdef FALTA_verificar_en_Graft
01464         bool Ancestor( Tree & Child, Tree & Father );
01465         assert( ! Ancestor( o, *this ) ); // "o" no puede ser ancestro de *this"
01466     #endif
01467 
01468     n++; // lo incrementa para no incrementar "m_n_child" para cada hijo de "m_root" o de "o"
01469 
01470     if ( o.m_root == 0 ) { // Sólo hay que eliminar el hijo número "n" de "m_root"
01471         Tree_Node<E> * prev;
01472         Erase_Son_Prev(n, prev /*, prev */);
01473         return Tree( ); // si se vale repetir "prev" en Erase_Son_Prev()
01474     }
01475     // assert( o.m_root != 0 );
01476 
01477     // Determina quién es el padre de "o"
01478     Tree_Node<E> * brother = o.m_root;
01479     while ( brother->m_n_child > 0 ) {
01480         brother = brother->m_right_brother;
01481     }
01482     Tree_Node<E> * o_father = brother->m_right_brother; // éste es el padre de "o"
01483     Tree_Node<E> * prev;
01484 
01485     if ( o_father != m_root ) {
01486         /*  El puntero "prev" apunta al nodo después del que hay que injertar "o".
01487             - Si "prev == 0" hay que  poner a "o" de primero en lista de hijos de "m_root".
01488             - Si "prev != 0" hay que  instalar "o" después de "prev".
01489             - Aquí es donde se usa Erase_Son_Prev().
01490         */
01491         // Elimina el hijo número "n" de "m_root"
01492         Erase_Son_Prev(n, prev /*, prev */);
01493         // assert( Child(n-1).Empty() ); // Ojo: mata "Child(n-1)" porque ya "n" está incrementado
01494     } else { // assert( o_father == m_root ); //  Caso especial ==> T.Graft( T.Child(n), n ± i );
01495         unsigned o_n_child = o.m_root->Abs_n_child();
01496         if ( o_n_child == n ) { // Caso especial cuando "o" ya es hijo de "m_root"
01497             // "o" está en su lugar ==> no hay que hacer nada
01498             // [y hay que evitar borrarlo con Erase_Son(n)]
01499             return Tree( (NOT_null_pointer*) o.m_root );
01500         }
01501 
01502         Erase_Son_Prev(n, prev /*, prev */);
01503 
01504         if ( (prev == o.m_root) || (prev != 0 && prev->m_right_brother == o.m_root ) ) {
01505             // ya "o" está en donde debe
01506             if ( o.m_root->m_right_brother == m_root ) { // basta cambiar "m_n_child"
01507                 o.m_root->m_n_child = - int(n);
01508             } else  {
01509                 o.m_root->m_n_child = + int(n);
01510             }
01511             return Tree( (NOT_null_pointer*) o.m_root );
01512         }
01513     }
01514 
01515     if (o_father != 0) { // Saca a "o" de la lista de hijos de su padre
01516         o.m_root->m_refCount--; // pues no estará en la lista de hijos de su padre actual
01517         assert( o_father->m_left_child != 0 );
01518         if ( o.m_root == o_father->m_left_child ) { // "o" es el primer hijo
01519             if ( o.m_root->m_n_child < 0 ) { // "o" es el único hijo
01520                 o_father->m_left_child = 0;
01521             } else { // "o" tiene hermanos
01522                 o_father->m_left_child = o.m_root->m_right_brother;
01523             }
01524         } else {
01525             brother = o_father->m_left_child; // hermano más izquierdo de "o"
01526             while ( brother->m_right_brother != o.m_root ) {
01527                 brother = brother->m_right_brother;
01528             }
01529             brother->m_right_brother = o.m_root->m_right_brother;
01530             if ( o.m_root->m_n_child < 0 ) { // "o" estaba de último hijo
01531                 brother->m_n_child = - brother->m_n_child; // hay un nuevo hijo de último
01532             }
01533         }
01534     }
01535     // assert( o.Father().Empty() ); // ya "o" está solito y sin familia
01536 
01537     o.m_root->m_refCount++; // lo incrementa porque lo va a enlazar como hijo de "m_root"
01538 
01539     if ( prev == 0 ) { // enlaza "o" al principio de la lista de hijos de "m_root"
01540         if ( m_root->m_left_child == 0 ) {
01541             o.m_root->m_right_brother = m_root; // "o" será el único hijo de "m_root"
01542             o.m_root->m_n_child = - int(n);
01543             m_root->m_left_child = o.m_root;
01544         } else {
01545             o.m_root->m_right_brother = m_root->m_left_child;
01546             // assert( o.m_root->m_right_brother != m_root );
01547             o.m_root->m_n_child = + int(n);
01548             m_root->m_left_child = o.m_root;
01549         }
01550     } else { // assert( prev != 0 );
01551         // enlaza en el medio de la lista de hijos de "m_root"
01552         o.m_root->m_right_brother = prev->m_right_brother;
01553         prev->m_right_brother = o.m_root;
01554         if ( o.m_root->m_right_brother == m_root ) {
01555             prev->m_n_child = - prev->m_n_child; // ya "prev" no está de último
01556             o.m_root->m_n_child = - int(n);
01557         } else  {
01558             o.m_root->m_n_child = + int(n);
01559         }
01560     }
01561 
01562     return Tree( (NOT_null_pointer*) o.m_root );
01563 
01564 
01565 /*  ¿Por qué hay que usar "prev_prev"? En realidad no hace falta, pero sí hay que
01566     destacar un caso especial, cuando "o" es hijo de "*this", o sea cuando:
01567     - ( Root(). Same( o.Root() ) )
01568         R       T.Erase(); T = 'R';
01569        / \      T.Change_Child(1, '1');
01570       1   3     T.Change_Child(3, '3');
01571 
01572     Al ejecutar T.Graft( 5 , T.Child(3) ); lo que hay que hacer es desligar el Nodo['3'] de su
01573     padre, el árbol T que tiene por raíz a Nodo['A'], para ligarlo de nuevo como Nodo['5'].
01574 
01575     Para este caso, "prev" apunto a T.Child(3), pues es después de Nodo['3'] en donde habría
01576     que  enlazar a Nodo['5']. Desafortunadamente, como el primer paso del algoritmo saca de
01577     T a Nodo[3], al tratar de enlazarlo luego de "prev" en realidad lo que se haría es
01578     enlazar al nodo después de sí mismo; estor resulta en la "desaparición misteriosa"
01579     de Nodo['3']. Por eso, la solución a este caso especial, es retornar no "prev", sino
01580     "prev_prev", que apunta al nodo anterio al Nodo[5], que en este caso es Nodo['1'].
01581 */
01582 } // Graft()
01583 
01584 } // namespace TL
01585 
01586 #endif  // Tree_L_h
01587 
01588 // EOF: Tree_L.h

Generado el Tue Jun 30 06:20:32 2009 para Uso de TL::Tree y TV::Tree: por  doxygen 1.3.9.1