Del básico al intermedio: Colas, listas y árboles (VII)

Introducción

En el artículo anterior, Del básico al intermedio: Colas, listas y árboles (VI), mostramos cómo implementar el mecanismo básico para construir un árbol. Al final de ese artículo, adaptamos el código para que utilizara una plantilla y, de este modo, generalizamos un poco el mecanismo desarrollado.

Aunque probablemente muchos no utilicen árboles de forma intensiva, comprender los mecanismos que intervienen en la implementación de esta estructura de datos te permitirá aprovechar mejor las funcionalidades de MQL5. Recuerda que aquí el objetivo principal es didáctico. Por tanto, cada principio adoptado debe adaptarse a tus necesidades y a las particularidades de cada caso. Aunque, en teoría, todo lo implementado y mostrado aquí pueda parecer válido para cualquier situación, es posible que no sea lo más adecuado para tu objetivo particular. En ese caso, comprender correctamente los conceptos presentados y explicados en los artículos te ayudará a encontrar la mejor solución para tu situación.

Muy bien, partiendo de este principio, debemos comprender cómo realizar otro tipo de operación en un árbol. Aunque probablemente no utilices esta implementación con frecuencia, entender cómo funciona puede ayudarte a resolver otros tipos de problemas. Este artículo se centrará inicialmente en la eliminación de nodos de un árbol binario.

Si crees que se trata de una tarea sencilla, estás en lo cierto. Sin embargo, si no comprendes determinados conceptos, esta tarea, que a mi parecer es relativamente sencilla y fácil de implementar, puede convertirse en un gran dolor de cabeza, mi querido lector. Sobre todo si estás empezando a adentrarte en la programación. Sin más preámbulos, pasemos al tema principal de este artículo.

Colas, listas y árboles (VII)

Cuando se trata de eliminar nodos de una estructura enlazada, muchas personas pueden encontrar ciertas dificultades. Sin embargo, a diferencia de lo que ocurre con las colas y las listas, en las que eliminar un nodo es relativamente sencillo, no sucede lo mismo cuando la estructura es un árbol. Por tanto, saber exactamente qué ocurre durante la eliminación de un nodo de un árbol puede ayudarte a comprender otros aspectos que veremos más adelante. Esto se debe a que, al eliminar un nodo de un árbol, nos encontramos con una situación bastante curiosa: creamos temporalmente un segundo árbol.

Para que puedas comprender cómo se elimina un nodo de un árbol y qué ocurre con su estructura, primero debes entender la propia estructura del árbol mediante la salida que generarán las funciones de recorrido en el terminal. Sé que al principio esto puede parecer bastante extraño y difícil de visualizar en los primeros ejemplos de árboles que modeles, así que lo veremos juntos y con calma. Lo primero que debemos analizar es el código presentado en el artículo anterior, aunque con una pequeña modificación. A continuación se incluye el código completo.

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T>
005. class C_TreeNode
006. {
007.     private :
008. //+----------------+
009.         T           info;
010.         C_TreeNode  *left,
011.                     *right;
012. //+----------------+
013.     public  :
014. //+----------------+
015.         C_TreeNode()
016.             :left(NULL),
017.             right(NULL)
018.         {}
019. //+----------------+
020.         void SetInfo(T arg) { info = arg; }
021. //+----------------+
022.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
023. //+----------------+
024.         void SetRight(C_TreeNode *ptr) { right = ptr; }
025. //+----------------+
026.         T GetInfo(void) const { return info; }
027. //+----------------+
028.         C_TreeNode *GetLeft(void) const { return left; }
029. //+----------------+
030.         C_TreeNode *GetRight(void) const { return right; }
031. //+----------------+
032. };
033. //+------------------------------------------------------------------+
034. #define C_TreeNode C_TreeNode<T>
035. template <typename T>
036. class C_Tree
037. {
038. //+----------------+
039.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
040.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy};
041. //+----------------+
042.     private :
043.         C_TreeNode *root;
044.         string      m_szInfo;
045. //+----------------+
046.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, T info)
047.         {
048.             if (ptr == NULL)
049.             {
050.                 ptr = new C_TreeNode;
051. 
052.                 (*ptr).SetInfo(info);
053.                 if (arg == NULL) return ptr;
054.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
055.                 else (*arg).SetRight(ptr);
056. 
057.                 return ptr;
058.             }
059.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
060.             else return Insert(ptr, (*ptr).GetRight(), info);
061.         }
062. //+----------------+
063.         void Seq(C_TreeNode *ptr, const E_SEQ type)
064.         {
065.             if (ptr == NULL) return;
066. 
067.             switch (type)
068.             {
069.                 case eInOrder   :
070.                 case ePostOrder :
071.                 case eDestroy   :
072.                     Seq((*ptr).GetLeft(), type);
073.                     if (type == eInOrder) break;
074.                     Seq((*ptr).GetRight(), type);
075.             }
076.             m_szInfo += def_InfoToString(ptr);
077.             switch (type)
078.             {
079.                 case ePreOrder  :
080.                     Seq((*ptr).GetLeft(), type);
081.                 case eInOrder   :
082.                     Seq((*ptr).GetRight(), type);
083.                     break;
084.                 case eDestroy   :
085.                     delete ptr;
086.             }
087.         }
088. //+----------------+
089.     public  :
090. //+----------------+
091.         C_Tree()
092.             :root(NULL)
093.         {}
094. //+----------------+
095.         ~C_Tree()
096.         {
097.             Seq(root, eDestroy);
098.         }
099. //+----------------+
100.         void Store(T info)
101.         {
102.             if (root == NULL) root = Insert(root, root, info);
103.             else Insert(root, root, info);
104.         }
105. //+----------------+
106.         string In_Order(void)
107.         {
108.             m_szInfo = "In Order: ";
109.             Seq(root, eInOrder);
110.             
111.             return m_szInfo;
112.         }
113. //+----------------+
114.         string Pre_Order(void)
115.         {
116.             m_szInfo = "Pre Order: ";
117.             Seq(root, ePreOrder);
118. 
119.             return m_szInfo;
120.         }
121. //+----------------+
122.         string Post_Order(void)
123.         {
124.             m_szInfo = "Post Order: ";
125.             Seq(root, ePostOrder);
126. 
127.             return m_szInfo;
128.         }
129. //+----------------+
130.     #undef def_InfoToString
131. //+----------------+
132. };
133. #undef C_TreeNode
134. //+------------------------------------------------------------------+
135. void OnStart(void)
136. {
137.     C_Tree <int> Tree;
138. 
139.     Tree.Store(10);
140.     Tree.Store(-6);
141.     Tree.Store(47);
142.     Tree.Store(35);
143.     Tree.Store(85);
144.     Tree.Store(40);
145. 
146.     Print(Tree.In_Order());
147.     Print(Tree.Pre_Order());
148.     Print(Tree.Post_Order());
149. }
150. //+------------------------------------------------------------------+

Código 01

Aunque se incluye el código completo, lo que realmente nos interesa es comprender qué estructura generan las instrucciones comprendidas entre las líneas 139 y 144. Y aunque las llamadas a las funciones de recorrido comprendidas entre las líneas 146 y 148 generan una salida en formato lineal, necesito que tú, mi querido y estimado lector, hagas un pequeño esfuerzo por interpretarla de otra manera. Esa salida debe permitirte formar una representación mental de la estructura que genera el código. En algunos casos, podríamos obtener una estructura similar a una lista enlazada. Sin embargo, debido al orden en que se añadieron los valores, no crearemos una estructura lineal, sino una estructura arbórea. Eso es precisamente lo que quiero que intentes visualizar mentalmente, porque, si no lo consigues, no podrás comprender cómo eliminar un nodo de un árbol sin destruir el propio árbol.

Al ejecutar este código 01, verás en el terminal la salida mostrada en la imagen siguiente.

Imagen 01

Ahora, mi querido lector, necesito que te concentres en esta imagen 01 y que, al mismo tiempo, reconstruyas mentalmente cómo las funciones Pre_Order y Post_Order generaron las salidas mostradas en la imagen 01. ¿Por qué no mencionas la salida generada por In_Order? La razón es sencilla, mi querido lector. La función In_Order siempre genera una salida similar a la de una lista enlazada ordenada. Como esa salida no nos ayuda demasiado, al menos en este escenario, podemos ignorarla.

Bien, centrémonos primero en la salida generada por la función Post_Order. Esta función muestra primero los nodos terminales y solo después los nodos internos del árbol. Recuerda lo siguiente: NO SABES cuántos nodos terminales existen en el árbol. Solo sabes que cada nodo puede apuntar a un máximo de dos nodos hijos. Por tanto, sabemos con total certeza que los dos primeros nodos que aparecen en la salida son terminales, independientemente de cualquier otra información, ya que la propia clase C_TreeNode indica que existen dos direcciones posibles.

Ahora debemos observar la salida generada por la función Pre_Order. En este caso, la función comienza el recorrido desde el nodo raíz y avanza primero hacia la izquierda hasta encontrar un nodo terminal. Después regresa al nodo anterior y continúa por la rama derecha. A partir de esto, ya podemos afirmar que el nodo raíz almacena el valor 10, mientras que el valor -6 está almacenado en un nodo terminal situado a la izquierda del nodo raíz. Esto nos permite generar la imagen mostrada a continuación.

Imagen 02

Bien, ya tenemos una representación parcial del árbol que podemos visualizar mentalmente. Ahora necesito que continúes con este pequeño esfuerzo. Si observas con calma la imagen 02, notarás lo siguiente: los dos valores conocidos y visibles en ella forman parte de una rama completa del árbol. Lo que falta puede y debe interpretarse como un nuevo árbol. Si consigues entenderlo, podrás ver que, según la salida generada por Pre_Order, el siguiente nodo visitado será la raíz de este nuevo árbol que visualizamos. Sé que puede parecer extraño, pero debes intentar representar la estructura de forma no lineal.

Muy bien, si la imagen 02 representa la rama izquierda, el nodo raíz almacena el valor 10 y la instrucción de la línea 54 determina cómo se enlazarán los nodos, podemos afirmar que la imagen siguiente representa el próximo paso en la construcción mental del árbol creado por el código 01.

Imagen 03

Bien, esto parece tener sentido. Sin embargo, todavía debemos completar los demás nodos de la imagen 03. Para hacerlo, recurriremos nuevamente a la salida generada por la función Post_Order. Presta atención. El primer valor que aparece en la salida es -6 y el segundo es 40. ¿Por qué? Porque el nodo que almacena el valor 40 es terminal. Espera un momento: si se trata de un nodo terminal, podría ocupar cualquiera de las posiciones vacías de la imagen 03, ¿correcto? Sí, mi querido lector. Sin embargo, debes observar el código de la función Post_Order. Al hacerlo, comprenderás que Post_Order avanza hasta la mayor profundidad posible antes de comenzar a retroceder, y siempre recorre primero la rama izquierda y después la derecha. Es muy importante que comprendas bien este punto, porque, si se invierte el orden, la función generará una salida diferente. A partir de este conocimiento, podemos afirmar con total seguridad que la imagen siguiente representa la posición que debe ocupar el nodo cuyo valor es 40.

Imagen 04

Bien, ahora nos quedan dos nodos por colocar en sus posiciones correctas. Para determinar dónde deben situarse los nodos que almacenan esos valores, podemos aplicar un poco de lógica o consultar la propia imagen 01. En ambos casos, obtendremos finalmente lo que se muestra a continuación, completando así la representación de nuestro árbol.

Imagen 05

Perfecto. Si comprendiste cómo se obtuvo esta imagen 05, significa que podemos continuar. Sin embargo, antes de hacerlo, quiero mostrarte un pequeño detalle. Supongamos que el recorrido del árbol se implementa con un orden distinto, como se muestra en el fragmento siguiente.

                   .
                   .
                   .
062. //+----------------+
063.         void Seq(C_TreeNode *ptr, const E_SEQ type)
064.         {
065.             if (ptr == NULL) return;
066. 
067.             switch (type)
068.             {
069.                 case ePostOrder :
070.                 case eDestroy   :
071.                     Seq((*ptr).GetRight(), type);
072.                 case eInOrder   :
073.                     Seq((*ptr).GetLeft(), type);
074.             }
075.             m_szInfo += def_InfoToString(ptr);
076.             switch (type)
077.             {
078.                 case eInOrder   :
079.                 case ePreOrder  :
080.                     Seq((*ptr).GetRight(), type);
081.                     if (type == eInOrder) break;
082.                     Seq((*ptr).GetLeft(), type);
083.                     break;
084.                 case eDestroy   :
085.                     delete ptr;
086.             }
087.         }
088. //+----------------+
                   .
                   .
                   .

Fragmento 01

En este caso, el código generaría la salida mostrada en la imagen siguiente.

Imagen 06

Observa que, en este caso, el simple hecho de haber modificado el código 01 según lo propuesto en el fragmento 01 hizo que la salida final del recorrido fuera la mostrada en la imagen 06. Fíjate también en que la diferencia entre el fragmento 01 y el código 01 es muy sutil. Podría pasar inadvertida si no se mostrara aquí en el artículo. Ahora ya lo sabes, mi querido lector: siempre que analices una salida de este tipo, procura examinar también el código fuente para obtener una visión más completa de la situación.

Perfecto, ahora ya podemos comprender cómo se elimina un nodo del árbol. Estoy seguro de que tú, mi querido lector, podrás interpretar correctamente la salida generada en el terminal. Sin embargo, y solo para mostrar de forma muy sencilla cómo se elimina un nodo del árbol, primero eliminaremos el nodo cuyo valor es 47. Al hacerlo, la estructura del árbol quedará como se muestra en la imagen siguiente.

Imagen 07

Vaya, esto sí que resulta bastante inquietante, porque tenemos un nodo raíz cuyo valor es 10, un árbol desconectado cuyo nodo raíz es 35 y un nodo aislado con el valor 85. La estructura quedará así, mi querido lector, si eliminamos sin ningún cuidado ni criterio el nodo cuyo valor es 47.

Bien, ¿cómo encontraremos dentro del árbol el nodo que almacena el valor 47? Todavía no has explicado cómo se hace. Hum, es cierto. Aún no he explicado cómo localizar un nodo a partir del valor que contiene. Ha sido un descuido mío. Discúlpame, mi querido lector. Antes de comenzar con la eliminación, veamos cómo localizar un nodo específico mediante su valor almacenado. La búsqueda es muy sencilla: solo debemos añadir un poco de código al método Seq, cuya definición comienza en la línea 63. Para ello, usaremos el código completo que aparece a continuación.

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T>
005. class C_TreeNode
006. {
007.     private :
008. //+----------------+
009.         T           info;
010.         C_TreeNode  *left,
011.                     *right;
012. //+----------------+
013.     public  :
014. //+----------------+
015.         C_TreeNode()
016.             :left(NULL),
017.             right(NULL)
018.         {}
019. //+----------------+
020.         void SetInfo(T arg) { info = arg; }
021. //+----------------+
022.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
023. //+----------------+
024.         void SetRight(C_TreeNode *ptr) { right = ptr; }
025. //+----------------+
026.         T GetInfo(void) const { return info; }
027. //+----------------+
028.         C_TreeNode *GetLeft(void) const { return left; }
029. //+----------------+
030.         C_TreeNode *GetRight(void) const { return right; }
031. //+----------------+
032. };
033. //+------------------------------------------------------------------+
034. #define C_TreeNode C_TreeNode<T>
035. template <typename T>
036. class C_Tree
037. {
038. //+----------------+
039.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
040.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy, eSearch};
041. //+----------------+
042.     private :
043.         C_TreeNode *root;
044.         string      m_szInfo;
045. //+----------------+
046.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, T info)
047.         {
048.             if (ptr == NULL)
049.             {
050.                 ptr = new C_TreeNode;
051. 
052.                 (*ptr).SetInfo(info);
053.                 if (arg == NULL) return ptr;
054.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
055.                 else (*arg).SetRight(ptr);
056. 
057.                 return ptr;
058.             }
059.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
060.             else return Insert(ptr, (*ptr).GetRight(), info);
061.         }
062. //+----------------+
063.         C_TreeNode *Seq(C_TreeNode *ptr, const E_SEQ type, const T info = 0)
064.         {
065.             if (ptr == NULL) return NULL;
066. 
067.             switch (type)
068.             {
069.                 case eSearch    :
070.                     while ((ptr != NULL) && ((*ptr).GetInfo() != info))
071.                         ptr = (info < (*ptr).GetInfo() ? (*ptr).GetLeft() : (*ptr).GetRight());
072.                     return ptr;
073.                 case eInOrder   :
074.                 case ePostOrder :
075.                 case eDestroy   :
076.                     Seq((*ptr).GetLeft(), type);
077.                     if (type == eInOrder) break;
078.                     Seq((*ptr).GetRight(), type);
079.             }
080.             m_szInfo += def_InfoToString(ptr);
081.             switch (type)
082.             {
083.                 case ePreOrder  :
084.                     Seq((*ptr).GetLeft(), type);
085.                 case eInOrder   :
086.                     Seq((*ptr).GetRight(), type);
087.                     break;
088.                 case eDestroy   :
089.                     delete ptr;
090.             }
091. 
092.             return NULL;
093.         }
094. //+----------------+
095.     public  :
096. //+----------------+
097.         C_Tree()
098.             :root(NULL)
099.         {}
100. //+----------------+
101.         ~C_Tree()
102.         {
103.             Seq(root, eDestroy);
104.         }
105. //+----------------+
106.         void Store(T info)
107.         {
108.             if (root == NULL) root = Insert(root, root, info);
109.             else Insert(root, root, info);
110.         }
111. //+----------------+
112.         string In_Order(void)
113.         {
114.             m_szInfo = "In Order: ";
115.             Seq(root, eInOrder);
116.             
117.             return m_szInfo;
118.         }
119. //+----------------+
120.         string Pre_Order(void)
121.         {
122.             m_szInfo = "Pre Order: ";
123.             Seq(root, ePreOrder);
124. 
125.             return m_szInfo;
126.         }
127. //+----------------+
128.         string Post_Order(void)
129.         {
130.             m_szInfo = "Post Order: ";
131.             Seq(root, ePostOrder);
132. 
133.             return m_szInfo;
134.         }
135. //+----------------+
136.         void Address(const T info)
137.         {
138.             Print(info, " information address is: ", Seq(root, eSearch, info));
139.         }
140. //+----------------+
141.     #undef def_InfoToString
142. //+----------------+
143. };
144. #undef C_TreeNode
145. //+------------------------------------------------------------------+
146. void OnStart(void)
147. {
148.     C_Tree <int> Tree;
149. 
150.     Tree.Store(10);
151.     Tree.Store(-6);
152.     Tree.Store(47);
153.     Tree.Store(35);
154.     Tree.Store(85);
155.     Tree.Store(40);
156. 
157.     Print(Tree.In_Order());
158.     Print(Tree.Pre_Order());
159.     Print(Tree.Post_Order());
160.     Tree.Address(47);
161. }
162. //+------------------------------------------------------------------+

Código 02

Observa que el código 02 difiere muy poco del código 01. Básicamente, la declaración incluida en la línea 40 incorpora una nueva enumeración, mientras que el método Seq, cuya definición comienza en la línea 63, deja de ser un método sin valor de retorno y pasa a devolver la dirección del nodo localizado.

Hay un aspecto de este método que conviene comprender, mi querido lector: la expresión condicional evaluada por el bucle while, ubicada en la línea 70. Muchas personas, sobre todo quienes están empezando, no comprenden bien cómo funciona un compilador. Tal vez en el futuro lo explique con detalle. Aún lo estoy pensando. Quizá sea un tema sobre el que a muchos les interese aprender, aunque todavía no sé si merece la pena abordarlo. Si te interesa, indícalo en los comentarios de este artículo. Si hay suficientes personas interesadas, lo explicaré con el mayor nivel de detalle posible. Y lo haré con un enfoque práctico, utilizando exclusivamente MQL5.

Otro detalle que conviene mencionar es que la expresión condicional ubicada en la línea 71 reproduce la misma lógica utilizada para insertar nodos en el árbol. Observa que compara los valores con el mismo criterio que la instrucción de inserción incluida en la línea 59. Comprender esto es importante, porque debemos seguir el mismo criterio de recorrido para no perdernos dentro del árbol.

Continuemos, porque quiero explicar un detalle de la expresión condicional que evalúa el bucle while, ubicada en la línea 70. El bucle en sí no nos interesa; lo importante es la comprobación expresada en esa condición.

Presta mucha atención, porque lo que voy a mostrarte puede volver loco a cualquier programador, aunque a algunos programadores más que a otros. Observa lo siguiente: cuando se ejecute la llamada a Address incluida en la línea 160, se invocará este método, cuya definición comienza en la línea 136. A su vez, Address llamará al método Seq, cuya definición comienza en la línea 63, para obtener la dirección del nodo que almacena el valor proporcionado como argumento. Hasta aquí, todo está bien. De hecho, al ejecutar este código, verás la salida mostrada a continuación.

Imagen 08

Ahora viene el detalle. Abre el editor y, en este código 02 incluido en el anexo, sustituye el valor utilizado como criterio de búsqueda por otro que no esté almacenado en ningún nodo del árbol. Por ejemplo, utiliza 50 como valor buscado. La salida será la mostrada a continuación.

Imagen 09

Hasta aquí, todo correcto. No hay ningún problema. Ahora sustituye la condición ubicada en la línea 70 por la que se muestra a continuación.

while (((*ptr).GetInfo() != info) && (ptr != NULL))

Vuelve a compilar el código 02 después de modificar únicamente la condición ubicada en la línea 70. Al intentar ejecutarlo, verás la salida mostrada en la imagen siguiente.

Imagen 10

¿Qué ha ocurrido? Vamos, esto no tiene ningún sentido. Debes estar bromeando, porque nunca había visto un comportamiento así. ¿La condición ubicada en la línea 70 prácticamente no ha cambiado y, aun así, el código ha fallado? Qué locura. Bien, mi querido lector, aunque creas que esa condición no ha cambiado, sí lo ha hecho. Esto se debe a algunos aspectos del proceso de compilación. Explicarlo de forma teórica resulta algo complicado, pero, al observar en la práctica cómo funciona el compilador, todo cobra sentido. Por tanto, si deseas comprenderlo con más detalle, no olvides escribir en los comentarios de este artículo: «Quiero entender cómo funciona un compilador». Así sabré si merece la pena crear algunos artículos para explicarlo en profundidad.

Volvamos a nuestra cuestión. Gracias al método Address, cuya definición comienza en la línea 136, ya disponemos de un mecanismo para localizar un nodo a partir del valor que almacena. Ha llegado el momento de implementar el código que eliminará un nodo del árbol.

Para ello, tendremos que implementar un mecanismo de eliminación que, en principio, puede resultar un tanto confuso. Sin embargo, si comprendiste el comienzo de este artículo, entenderás perfectamente lo que vamos a hacer. Como no quiero complicar de inmediato el mecanismo de eliminación y eliminar nodos de un árbol es distinto de hacerlo en una lista, comenzaremos por el caso más sencillo. Después podremos analizar un caso algo más elaborado y, por tanto, más general. El caso más sencillo consiste en eliminar una hoja del árbol. ¿Qué significa que un nodo sea una hoja? Explicaste qué es un nodo, una rama y también una raíz.

Sin embargo, no dijiste nada sobre las hojas. Bien, para mí, el concepto de hoja debería resultar bastante intuitivo. De todos modos, aclaremos qué significa. Una hoja es un nodo terminal, es decir, un nodo del que no sale ninguna rama. Básicamente, es el punto donde termina la rama por la que estamos avanzando. Para que quede aún más claro, en la imagen 05 tenemos tres hojas: los nodos cuyos valores son -6, 40 y 85. Con esto, creo que ya puedes comprender qué es una hoja.

Bien, este es el caso más sencillo. En teoría, solo tendríamos que eliminar ese nodo del árbol. Sin embargo, en la práctica, no basta con liberar la memoria ocupada por la hoja. Antes de eliminar la hoja, debemos actualizar el puntero del nodo padre que apunta a la hoja. De lo contrario, las búsquedas o los recorridos posteriores intentarán seguir un enlace que contiene una dirección de memoria no válida y el código fallará.

¿Cómo es eso? No he entendido lo que quieres decir. Calma, mi querido lector, pronto lo comprenderás. Primero implementemos un código que permita eliminar las hojas de un árbol. A continuación se incluye el código de ejemplo completo.

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T>
005. class C_TreeNode
006. {
007.     private :
008. //+----------------+
009.         T           info;
010.         C_TreeNode  *left,
011.                     *right;
012. //+----------------+
013.     public  :
014. //+----------------+
015.         C_TreeNode()
016.             :left(NULL),
017.             right(NULL)
018.         {}
019. //+----------------+
020.         void SetInfo(T arg) { info = arg; }
021. //+----------------+
022.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
023. //+----------------+
024.         void SetRight(C_TreeNode *ptr) { right = ptr; }
025. //+----------------+
026.         T GetInfo(void) const { return info; }
027. //+----------------+
028.         C_TreeNode *GetLeft(void) const { return left; }
029. //+----------------+
030.         C_TreeNode *GetRight(void) const { return right; }
031. //+----------------+
032. };
033. //+------------------------------------------------------------------+
034. #define C_TreeNode C_TreeNode<T>
035. template <typename T>
036. class C_Tree
037. {
038. //+----------------+
039.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
040.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy, eSearch};
041. //+----------------+
042.     private :
043.         C_TreeNode *root;
044.         string      m_szInfo;
045. //+----------------+
046.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, T info)
047.         {
048.             if (ptr == NULL)
049.             {
050.                 ptr = new C_TreeNode;
051. 
052.                 (*ptr).SetInfo(info);
053.                 if (arg == NULL) return ptr;
054.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
055.                 else (*arg).SetRight(ptr);
056. 
057.                 return ptr;
058.             }
059.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
060.             else return Insert(ptr, (*ptr).GetRight(), info);
061.         }
062. //+----------------+
063.         C_TreeNode *Seq(C_TreeNode *ptr, const E_SEQ type, const T info = 0)
064.         {
065.             if (ptr == NULL) return NULL;
066. 
067.             switch (type)
068.             {
069.                 case eSearch    :
070.                     while ((ptr != NULL) && ((*ptr).GetInfo() != info))
071.                         ptr = (info < (*ptr).GetInfo() ? (*ptr).GetLeft() : (*ptr).GetRight());
072.                     return ptr;
073.                 case eInOrder   :
074.                 case ePostOrder :
075.                 case eDestroy   :
076.                     Seq((*ptr).GetLeft(), type);
077.                     if (type == eInOrder) break;
078.                     Seq((*ptr).GetRight(), type);
079.             }
080.             m_szInfo += def_InfoToString(ptr);
081.             switch (type)
082.             {
083.                 case ePreOrder  :
084.                     Seq((*ptr).GetLeft(), type);
085.                 case eInOrder   :
086.                     Seq((*ptr).GetRight(), type);
087.                     break;
088.                 case eDestroy   :
089.                     delete ptr;
090.             }
091. 
092.             return NULL;
093.         }
094. //+----------------+
095.     public  :
096. //+----------------+
097.         C_Tree()
098.             :root(NULL)
099.         {}
100. //+----------------+
101.         ~C_Tree()
102.         {
103.             Seq(root, eDestroy);
104.         }
105. //+----------------+
106.         void Store(T info)
107.         {
108.             if (root == NULL) root = Insert(root, root, info);
109.             else Insert(root, root, info);
110.         }
111. //+----------------+
112.         string In_Order(void)
113.         {
114.             m_szInfo = "In Order: ";
115.             Seq(root, eInOrder);
116.             
117.             return m_szInfo;
118.         }
119. //+----------------+
120.         string Pre_Order(void)
121.         {
122.             m_szInfo = "Pre Order: ";
123.             Seq(root, ePreOrder);
124. 
125.             return m_szInfo;
126.         }
127. //+----------------+
128.         string Post_Order(void)
129.         {
130.             m_szInfo = "Post Order: ";
131.             Seq(root, ePostOrder);
132. 
133.             return m_szInfo;
134.         }
135. //+----------------+
136.         void DeleteNode(const T info)
137.         {
138.             C_TreeNode *tmp, *ptr = root;
139. 
140.             for (tmp = NULL; (ptr != NULL) && ((*ptr).GetInfo() != info); tmp = ptr, ptr = (info < (*ptr).GetInfo() ? (*ptr).GetLeft() : (*ptr).GetRight()));
141. 
142.             if (ptr != NULL)
143.             {
144.                 if ((*ptr).GetLeft() == (*ptr).GetRight())
145.                 {
146.                     if (info < (*tmp).GetInfo()) (*tmp).SetLeft(NULL);
147.                     else (*tmp).SetRight(NULL);
148.                     delete ptr;
149.                 }
150.             }
151.         }
152. //+----------------+
153.     #undef def_InfoToString
154. //+----------------+
155. };
156. #undef C_TreeNode
157. //+------------------------------------------------------------------+
158. void OnStart(void)
159. {
160.     C_Tree <int> Tree;
161. 
162.     Tree.Store(10);
163.     Tree.Store(-6);
164.     Tree.Store(47);
165.     Tree.Store(35);
166.     Tree.Store(85);
167.     Tree.Store(40);
168. 
169.     Print(Tree.In_Order());
170.     Print(Tree.Pre_Order());
171.     Print(Tree.Post_Order());
172. 
173.     Tree.DeleteNode(85);
174.     Print("----------------");
175. 
176.     Print(Tree.In_Order());
177.     Print(Tree.Pre_Order());
178.     Print(Tree.Post_Order());
179. }
180. //+------------------------------------------------------------------+

Código 03

Los nodos pueden eliminarse de distintas formas, tanto mediante recursividad como con enfoques iterativos. En este caso, utilizaremos un enfoque iterativo. El motivo es que resulta algo más rápido, sobre todo porque la eliminación de nodos puede desequilibrar el árbol con mucha rapidez. La consiguiente degeneración de la estructura reduce el rendimiento de los recorridos recursivos utilizados para eliminar nodos. Veamos qué estamos haciendo en el Code 03.

Cuando se ejecute la llamada a Address incluida en la línea 173, se invocará el método Address, cuya definición comienza en la línea 136. Dentro de Address, el bucle de búsqueda recorrerá el árbol hasta localizar el nodo cuyo valor coincida con el argumento recibido. ¿Por qué no utilizamos la búsqueda realizada por el método Seq? Porque Seq devuelve la dirección del nodo encontrado, pero no conserva una referencia a su nodo padre. Address necesita ambas referencias para actualizar, en el nodo padre, el puntero que apunta al nodo que se eliminará.

Observa lo siguiente, mi querido lector. El bucle cuya definición comienza en la línea 140 comparará el valor almacenado en cada nodo con el valor buscado hasta localizar el nodo que queremos eliminar. En cada iteración, la asignación a la variable tmp conservará una referencia al nodo visitado en la iteración anterior, que al finalizar la búsqueda será el nodo padre del nodo encontrado. Cuando termine la búsqueda, la condición ubicada en la línea 144 comprobará si el nodo encontrado es una hoja. En ese caso, la asignación incluida en la línea 146 modificará el puntero izquierdo o derecho del nodo padre para que deje de apuntar a la hoja que se va a eliminar. Finalmente, la instrucción delete incluida en la línea 148 liberará la memoria ocupada por esa hoja.

Así, al ejecutar este código 03, obtendremos la salida mostrada a continuación.

Imagen 11

Ahora presta atención a un detalle de esta imagen 11, precisamente en la parte que he resaltado. Si observas con atención, notarás que el nodo que almacenaba el valor proporcionado como argumento a la llamada incluida en la línea 173 no aparece en esta zona delimitada. Esto confirma que la asignación dejó de enlazar el nodo padre con la hoja eliminada y que la instrucción delete liberó la memoria ocupada por esa hoja. Es importante que lo notes, porque mediante la misma técnica mostrada en el código 03 podremos eliminar casi todos los nodos del árbol, hoja por hoja. Y digo casi porque tenemos un problema al eliminar el nodo raíz. Si intentas eliminarlo con este código 03, aunque sea el único nodo del árbol, el código fallará inevitablemente. Esto se debe a que la asignación incluida en la línea 146 intenta acceder al supuesto nodo padre de la raíz mediante una referencia no válida. Para solucionarlo, tendremos que añadir una condición que evite ese acceso.

Bien, ahora que entiendes la lógica del código de eliminación y que debemos conservar una referencia al nodo padre del nodo que se eliminará, podemos reorganizar el código de una forma más clara y útil, tanto desde el punto de vista práctico como didáctico. Así que no te asustes por lo que veremos a continuación, mi querido lector. Simplemente no quiero desarrollar el código bloque por bloque, porque eso acabaría volviendo la explicación bastante tediosa.

Después de aplicar todos los cambios necesarios, obtenemos el código que se muestra a continuación, que será nuestro nuevo código para construir árboles.

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T>
005. class C_TreeNode
006. {
007.     private :
008. //+----------------+
009.         T           info;
010.         C_TreeNode  *left,
011.                     *right;
012. //+----------------+
013.     public  :
014. //+----------------+
015.         C_TreeNode()
016.             :left(NULL),
017.             right(NULL)
018.         {}
019. //+----------------+
020.         void SetInfo(T arg) { info = arg; }
021. //+----------------+
022.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
023. //+----------------+
024.         void SetRight(C_TreeNode *ptr) { right = ptr; }
025. //+----------------+
026.         T GetInfo(void) const { return info; }
027. //+----------------+
028.         C_TreeNode *GetLeft(void) const { return left; }
029. //+----------------+
030.         C_TreeNode *GetRight(void) const { return right; }
031. //+----------------+
032. };
033. //+------------------------------------------------------------------+
034. #define C_TreeNode C_TreeNode<T>
035. template <typename T>
036. class C_Tree
037. {
038. //+----------------+
039.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
040.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy};
041. //+----------------+
042.     private :
043.         C_TreeNode *root;
044.         string      m_szInfo;
045. //+----------------+
046.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, T info)
047.         {
048.             if (ptr == NULL)
049.             {
050.                 ptr = new C_TreeNode;
051. 
052.                 (*ptr).SetInfo(info);
053.                 if (arg == NULL) return ptr;
054.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
055.                 else (*arg).SetRight(ptr);
056. 
057.                 return ptr;
058.             }
059.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
060.             else return Insert(ptr, (*ptr).GetRight(), info);
061.         }
062. //+----------------+
063.         C_TreeNode *EraseAndMerge(C_TreeNode *ptr)
064.         {
065.             C_TreeNode *tmp = ptr;
066. 
067.             if ((*tmp).GetRight() == NULL) ptr = (*ptr).GetLeft();
068.             else if ((*tmp).GetLeft() == NULL) ptr = (*ptr).GetRight();
069.             else
070.             {
071.                 tmp = (*ptr).GetLeft();
072.                 while ((*tmp).GetRight() != NULL) tmp = (*tmp).GetRight();
073.                 (*tmp).SetRight((*ptr).GetRight());
074.                 tmp = ptr;
075.                 ptr = (*ptr).GetLeft();
076.             }
077.             delete tmp;
078. 
079.             return ptr;
080.         }
081. //+----------------+
082.         void Seq(C_TreeNode *ptr, const E_SEQ type)
083.         {
084.             if (ptr == NULL) return;
085. 
086.             switch (type)
087.             {
088.                 case eInOrder   :
089.                 case ePostOrder :
090.                 case eDestroy   :
091.                     Seq((*ptr).GetLeft(), type);
092.                     if (type == eInOrder) break;
093.                     Seq((*ptr).GetRight(), type);
094.             }
095.             m_szInfo += def_InfoToString(ptr);
096.             switch (type)
097.             {
098.                 case ePreOrder  :
099.                     Seq((*ptr).GetLeft(), type);
100.                 case eInOrder   :
101.                     Seq((*ptr).GetRight(), type);
102.                     break;
103.                 case eDestroy   :
104.                     delete ptr;
105.             }
106.         }
107. //+----------------+
108.     public  :
109. //+----------------+
110.         C_Tree()
111.             :root(NULL)
112.         {}
113. //+----------------+
114.         ~C_Tree()
115.         {
116.             Seq(root, eDestroy);
117.         }
118. //+----------------+
119.         void Store(T info)
120.         {
121.             if (root == NULL) root = Insert(root, root, info);
122.             else Insert(root, root, info);
123.         }
124. //+----------------+
125.         string In_Order(void)
126.         {
127.             m_szInfo = "In Order: ";
128.             Seq(root, eInOrder);
129.             
130.             return m_szInfo;
131.         }
132. //+----------------+
133.         string Pre_Order(void)
134.         {
135.             m_szInfo = "Pre Order: ";
136.             Seq(root, ePreOrder);
137. 
138.             return m_szInfo;
139.         }
140. //+----------------+
141.         string Post_Order(void)
142.         {
143.             m_szInfo = "Post Order: ";
144.             Seq(root, ePostOrder);
145. 
146.             return m_szInfo;
147.         }
148. //+----------------+
149.         void DeleteNode(const T info)
150.         {
151.             C_TreeNode *tmp, *ptr = root;
152. 
153.             for (tmp = NULL; (ptr != NULL) && ((*ptr).GetInfo() != info); tmp = ptr, ptr = (info < (*ptr).GetInfo() ? (*ptr).GetLeft() : (*ptr).GetRight()));
154. 
155.             if (ptr != NULL)
156.             {
157.                 if (ptr == root) root = EraseAndMerge(ptr); else
158.                 {
159.                     if ((*tmp).GetLeft() == ptr) (*tmp).SetLeft(EraseAndMerge(ptr));
160.                     else (*tmp).SetRight(EraseAndMerge(ptr));
161.                 }
162.             }
163.         }
164. //+----------------+
165.     #undef def_InfoToString
166. //+----------------+
167. };
168. #undef C_TreeNode
169. //+------------------------------------------------------------------+
170. void OnStart(void)
171. {
172.     C_Tree <int> Tree;
173. 
174.     Tree.Store(10);
175.     Tree.Store(-6);
176.     Tree.Store(47);
177.     Tree.Store(35);
178.     Tree.Store(85);
179.     Tree.Store(40);
180. 
181.     Print(Tree.In_Order());
182.     Print(Tree.Pre_Order());
183.     Print(Tree.Post_Order());
184. 
185.     Tree.DeleteNode(10);
186.     Print("----------------");
187. 
188.     Print(Tree.In_Order());
189.     Print(Tree.Pre_Order());
190.     Print(Tree.Post_Order());
191. }
192. //+------------------------------------------------------------------+

Código 04

Observa que, en este código 04, incluido en el anexo, he eliminado la parte relacionada con la búsqueda dentro del árbol. Esto se debe a que abordaremos con más detalle esta cuestión en otro momento. Sin embargo, puedes notar que he añadido a la clase C_Tree un nuevo método, cuya definición comienza en la línea 63. Ahora presta atención, mi querido lector. El nuevo método se encargará de desvincular el nodo seleccionado para la eliminación y de reconectar los subárboles que dependían de ese nodo. El método aplica casi la misma lógica que el fragmento del código anterior utilizado para eliminar una hoja. Sin embargo, aquí presento todos los pasos de una sola vez, ya que explicarlos poco a poco resultaría demasiado tedioso y agotador.

La operación consiste en desvincular el nodo seleccionado para la eliminación y, a continuación, reconectar los subárboles que dependían del nodo seleccionado. No importa qué nodo vayamos a eliminar: la secuencia de operaciones será siempre la misma. Primero aislamos el nodo seleccionado. Después actualizamos los punteros necesarios para enlazar entre sí los subárboles restantes y ocupar la posición estructural que quedará libre. Finalmente, liberamos la memoria ocupada por el nodo eliminado.

Bien, y este es precisamente el punto principal: el método de reestructuración no se ejecuta de forma independiente. El método que identifica el nodo que debe eliminarse invoca el método de reestructuración. Por tanto, pasemos al método de eliminación, cuya definición comienza en la línea 149. Observa que el método de eliminación conserva básicamente la misma lógica; solo hemos modificado algunos detalles. Fíjate en que ahora la condición ubicada en la línea 157 comprobará si el nodo seleccionado para la eliminación es la raíz del árbol. En caso afirmativo, el método de reestructuración desvinculará la raíz actual, reconectará sus subárboles y establecerá como nueva raíz el nodo elegido por el algoritmo.

Si el nodo seleccionado para la eliminación no es la raíz, comprobaremos si el puntero izquierdo o el puntero derecho del nodo padre apunta al nodo seleccionado. A continuación, actualizaremos el puntero correspondiente para que apunte al nodo que ocupará la posición estructural del nodo eliminado. En cierto modo, esto se parece mucho a lo que hicimos al implementar la eliminación de nodos de las listas enlazadas. Como puedes ver, es muy sencillo y bastante práctico. Tal como dije al comienzo del artículo, el código de eliminación en sí es bastante simple. Sin embargo, comprender la lógica que aplica no resulta tan directo. Por eso tuvimos que seguir todos estos pasos hasta llegar a este código 04.

Bien, ¿qué salida genera este código 04? Mi querido lector, puedes verla a continuación.

Imagen 12

Ahora presta mucha atención y, en caso de duda, vuelve al comienzo del artículo para comprender lo que voy a explicar. Este árbol, que puedes observar en la imagen 12, no tiene ninguna rama a la izquierda. Esto se debe a que ahora está completamente desequilibrado, lo que reduce el rendimiento de las búsquedas en el árbol. Sin embargo, puedes ver claramente que el nodo que constituía la raíz original fue sustituido por el único nodo que formaba la rama izquierda de la raíz original. Como el nodo sustituto pasó a ocupar la raíz y no había ningún otro nodo en la rama izquierda original, la nueva raíz no tiene ninguna rama a la izquierda.

Consideraciones finales

En este artículo hemos mostrado y explicado con bastante claridad cómo se elimina un nodo de un árbol. Este proceso suele confundir a los principiantes más que ayudarlos a comprender cómo se lleva a cabo y por qué debe realizarse de una forma determinada.

Como el objetivo aquí es exclusivamente didáctico, el código de eliminación de nodos se implementó mediante uno de los muchos algoritmos destinados a este tipo de tarea. Corresponde al lector estudiar otros mecanismos que también pueden utilizarse para eliminar nodos, ya que, dependiendo de la cantidad de ramas presentes en cada nodo, el mecanismo mostrado en este artículo puede no ser el más adecuado. Para esos casos existen otros métodos mucho más sencillos y con mejores resultados, al menos en lo que respecta a la velocidad de ejecución.

Recuerda lo siguiente, mi querido lector: tareas como eliminar e insertar nodos en un árbol pueden desequilibrarlo. Hay situaciones en las que esto es conveniente. Sin embargo, en muchas otras, un árbol desequilibrado reduce el rendimiento de las búsquedas dentro de la estructura. Por esta razón, eliminé la parte encargada de realizar búsquedas en el árbol. En el próximo artículo hablaremos con más detalle sobre este tema. Entonces podrás decidir qué tipo de solución resulta más adecuada en cada caso.

Archivo MQ5	Descripción
Código 01	Árbol simple
Código 02	Árbol simple
Código 03	Árbol simple