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

Introducción

En el artículo anterior, Del básico al intermedio: Colas, listas y árboles (VII), explicamos una de las muchas formas posibles de eliminar un nodo de un árbol. Esta operación debe comprenderse muy bien para poder trabajar con árboles destinados a distintos fines. Como mencionamos en el artículo anterior, existen otras formas de implementar la eliminación. Sin embargo, a mi parecer, la que mostramos allí es una de las más sencillas entre las que no utilizan recursividad. Conviene evitar la recursividad al eliminar nodos porque, si es necesario borrar varios datos almacenados en nodos muy profundos, habrá que apilar numerosas llamadas para llegar a cada nodo y después desapilarlas. Este recorrido recursivo genera un coste computacional considerable y aumenta el tiempo necesario para ejecutar las operaciones de construcción y mantenimiento del árbol.

Bien, es necesario comprender lo explicado. De forma muy parecida, la operación de búsqueda debe diseñarse con mucho cuidado para evitar que aumente innecesariamente su tiempo de ejecución. Sin embargo, aquí surge una dificultad adicional: mantener equilibrado el árbol. Comprender esta cuestión es tan importante, o quizá incluso más, que entender los algoritmos de inserción, eliminación y búsqueda ya implementados o pendientes de implementar.

Por tanto, en este artículo veremos qué significa equilibrar un árbol y por qué es tan importante. También comenzaremos a comprender por qué a veces no podemos o no debemos reequilibrar el árbol —cuestión cuya aplicación práctica se abordará en otro artículo—, aunque la estructura conserve una diferencia de altura entre algunos subárboles. Ese desequilibrio estructural puede alargar determinados recorridos, pero no constituye por sí mismo una medida del tiempo de ejecución. Una búsqueda, inserción o eliminación tardará más o menos según la ruta que recorra y la cantidad de nodos que deba visitar. En cualquier caso, pasemos al tema principal de este artículo.

Colas, listas y árboles (VIII)

A diferencia de las colas y las listas, un árbol permite reducir el número de comparaciones necesarias durante una búsqueda. Cuando terminábamos de estudiar las listas, mencioné que sería muy útil buscar en una lista ordenada para acelerar esta operación. Para conseguirlo, necesitaríamos dividir la lista por la mitad en cada iteración. De este modo, la búsqueda se realizaría en el menor tiempo posible. Sin embargo, al organizar la lista para dividirla por la mitad en cada ciclo de búsqueda, terminábamos construyendo un árbol.

Sin embargo, esta idea nos lleva de nuevo a las listas: debemos determinar qué dato ocupará la posición central y servirá como punto de partida de la búsqueda. Parece sencillo, ¿verdad, mi querido lector? Si una lista contiene, por ejemplo, 100 datos, deberíamos utilizar el dato situado en la posición 50, porque divide la lista por la mitad.

No obstante, en la práctica, la elección del nodo que ocupará el punto central no es tan sencilla y puede generar una diferencia de altura entre los subárboles. La balanza de la imagen siguiente permite visualizar esta diferencia con facilidad.

Imagem 01

La balanza de dos platos de la imagen 01 ilustra la diferencia de altura entre los subárboles izquierdo y derecho. Si uno de los lados pesa más que el otro, la balanza se inclinará hacia ese lado. Del mismo modo, si uno de los subárboles contiene más nodos que el otro, su altura puede ser mayor. Ahora piensa en lo siguiente: cuanto mayor sea la diferencia de altura entre ambos subárboles, mayor puede ser la longitud de los recorridos que atraviesen el lado más profundo. Las búsquedas y demás operaciones que sigan esos recorridos podrán tardar más, mientras que las que terminen en rutas más cortas no sufrirán necesariamente el mismo coste. Existe además otro problema relacionado con esta diferencia de altura, que abordaremos más adelante. Por ahora, centrémonos en la balanza.

Bien, creo que he comprendido la idea. Sin embargo, tengo una duda. Si estamos insertando datos en un árbol, ¿no podemos indicar en qué nodo debe almacenarse cada uno? Esto evitaría el desequilibrio o, al menos, reduciría el problema.

En cierto modo, mi querido lector, en teoría sí podríamos indicar dónde almacenar cada dato. Sin embargo, en la práctica, esta decisión es mucho más difícil de lo que quizá hayas imaginado. Hasta ahora hemos utilizado valores discretos con fines didácticos, pero los datos almacenados en un árbol real pueden ser registros muy complejos.

En un árbol real, los datos almacenados NO SERÁN VALORES DISCRETOS; serán registros o estructuras de datos.

Ahora quizá empieces a comprender la dificultad. Una base de datos SQL puede servir como ejemplo sencillo para imaginar los datos que podrían almacenarse en un árbol, aunque una base de datos sea más compleja que un árbol aislado. Sin embargo, nos sirve como ejemplo para que puedas imaginar qué tipo de información podría almacenarse en un árbol.

Supongamos el siguiente escenario: tienes una serie de registros en una base de datos SQL, cada uno con un ID y algunos datos relacionados. Decides utilizar el ID para realizar búsquedas. Si la base de datos contiene 1.000.000 de registros, en el peor de los casos tendrás que examinarlos todos para localizar el registro buscado. Sin embargo, si utilizas un árbol perfectamente equilibrado como índice de búsqueda, tendrás que recorrer, como máximo, 20 nodos. ¿Qué? ¿Cómo es posible? ¿Qué clase de cálculo disparatado permite localizar un registro entre 1.000.000 recorriendo, como máximo, solo 20 nodos? Vamos, explícame ese truco, porque yo también quiero saber cómo hacerlo.

No es magia, mi querido lector, sino matemáticas. Para comprender por qué basta con recorrer tan pocos nodos para localizar un registro específico, necesitas entender cómo la diferencia de altura entre los subárboles influye en la altura total del árbol.

Supongamos que utilizas un nodo que puede tener como máximo dos nodos hijos, como hemos hecho en los códigos presentados hasta ahora. En ese caso, cada nivel puede contener la cantidad de nodos determinada por la ecuación que se muestra a continuación.

Imagem 02

En esta ecuación, n representa el nivel considerado. Por ejemplo, el nivel 1 contiene únicamente el nodo raíz, mientras que el nivel 5 puede contener un máximo de 16 nodos. Y así sucesivamente. En términos generales, la expresión mostrada en la imagen 02 puede reformularse para obtener la expresión siguiente.

Imagem 03

Aquí, P representa la cantidad máxima de nodos hijos que puede tener cada nodo. Por ejemplo, si cada nodo de nuestro árbol pudiera tener cinco hijos, la expresión se escribiría como se muestra a continuación.

Imagem 04

Como puedes ver, el número de nodos que deben recorrerse durante una búsqueda disminuye considerablemente. Sin embargo, esto tiene un coste: en cada nivel hay que determinar qué nodo hijo debe seguirse. Volvamos entonces al caso más sencillo, en el que cada nodo tiene como máximo dos hijos. Con un máximo de 20 niveles podríamos almacenar los 1.000.000 de registros mencionados, uno por nodo. Sin embargo, la cantidad de niveles utilizados siempre será inferior al valor n empleado en la expresión. La razón es muy sencilla: los nodos de cada nivel se suman al total acumulado de los niveles anteriores. Es decir, en la práctica necesitaremos 19 niveles para albergar esos 1.000.000 de nodos, suponiendo que el árbol esté bien equilibrado. Quienes tengan conocimientos de química probablemente ya habrán comprendido la idea: cada capa electrónica solo puede contener una cantidad determinada de electrones. Y para saber en qué capa se produjo el enlace, tendrás que distribuir los electrones adecuadamente.

Bien, creo que ahora he comprendido por qué necesitamos recorrer tan pocos nodos para localizar el dato buscado. Siempre me había preguntado por qué alguien dedicaría tanto tiempo a implementar un árbol si, al final, todo aquello me parecía una auténtica tontería. Sin embargo, al ver estas cifras, ahora entiendo la motivación.

Mi querido lector, muchas veces utilizamos un método de búsqueda que recorre más nodos de los necesarios simplemente por falta de conocimiento. Cuando comprendemos cómo funcionan los árboles de búsqueda, empezamos a entender por qué se desarrollaron. De este modo, finalmente puedes comprender por qué equilibrar el árbol resulta tan importante para reducir la cantidad de nodos recorridos durante las búsquedas.

Al igual que el método de eliminación presentado en el artículo anterior tiene distintas variantes, los métodos de equilibrado también tienen distintas variantes. Admito que elegir uno para mostrarlo en este artículo fue bastante difícil, ya que la elección depende del motivo o, mejor dicho, del momento en que deseas equilibrar el árbol. Existe un algoritmo bueno y bastante sencillo que permite equilibrar el árbol a medida que se insertan los datos. Aunque es muy fácil de implementar, no se ajusta al enfoque adoptado en este artículo. También existen otros algoritmos más elaborados y con objetivos bastante interesantes. Por tanto, mi querido lector, lo que mostraré aquí es solo una de las muchas alternativas posibles.

Para estudiar exclusivamente el algoritmo de equilibrado, realizaré algunos cambios en el código de implementación del árbol. De este modo, será más fácil centrarnos en las operaciones de equilibrado. Si presentáramos todo el código junto, probablemente tú, que estás empezando y quieres aprender su funcionamiento, acabarías perdido entre tantos fragmentos de código y conceptos. El código con el que trabajaremos se muestra 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(T arg)
016.             :left(NULL),
017.             right(NULL),
018.             info(arg)
019.         {}
020. //+----------------+
021.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
022. //+----------------+
023.         void SetRight(C_TreeNode *ptr) { right = ptr; }
024. //+----------------+
025.         T GetInfo(void) const { return info; }
026. //+----------------+
027.         C_TreeNode *GetLeft(void) const { return left; }
028. //+----------------+
029.         C_TreeNode *GetRight(void) const { return right; }
030. //+----------------+
031. };
032. //+------------------------------------------------------------------+
033. #define C_TreeNode C_TreeNode<T>
034. template <typename T>
035. class C_Tree
036. {
037. //+----------------+
038.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
039.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy};
040. //+----------------+
041.     private :
042.         C_TreeNode *root;
043.         string      m_szInfo;
044. //+----------------+
045.         C_TreeNode *Insert(C_TreeNode *ptr, T info)
046.         {
047.             if (ptr == NULL)
048.                 return new C_TreeNode(info);
049. 
050.             if (info < (*ptr).GetInfo()) (*ptr).SetLeft(Insert((*ptr).GetLeft(), info));
051.             else (*ptr).SetRight(Insert((*ptr).GetRight(), info));
052. 
053.             return ptr;
054.         }
055. //+----------------+
056.         void Extra(C_TreeNode *ptr, const E_SEQ type)
057.         {
058.             if (ptr == NULL) return;
059. 
060.             switch (type)
061.             {
062.                 case eInOrder   :
063.                 case ePostOrder :
064.                 case eDestroy   :
065.                     Extra((*ptr).GetLeft(), type);
066.                     if (type == eInOrder) break;
067.                     Extra((*ptr).GetRight(), type);
068.             }
069.             m_szInfo += def_InfoToString(ptr);
070.             switch (type)
071.             {
072.                 case ePreOrder  :
073.                     Extra((*ptr).GetLeft(), type);
074.                 case eInOrder   :
075.                     Extra((*ptr).GetRight(), type);
076.                     break;
077.                 case eDestroy   :
078.                     delete ptr;
079.             }
080.         }
081. //+----------------+
082.     public  :
083. //+----------------+
084.         C_Tree()
085.             :root(NULL)
086.         {}
087. //+----------------+
088.         ~C_Tree()
089.         {
090.             Extra(root, eDestroy);
091.         }
092. //+----------------+
093.         void Store(T info)
094.         {
095.             if (root == NULL) root = Insert(root, info);
096.             else Insert(root, info);
097.         }
098. //+----------------+
099.         string In_Order(void)
100.         {
101.             m_szInfo = "In Order: ";
102.             Extra(root, eInOrder);
103.             
104.             return m_szInfo;
105.         }
106. //+----------------+
107.         string Pre_Order(void)
108.         {
109.             m_szInfo = "Pre Order: ";
110.             Extra(root, ePreOrder);
111. 
112.             return m_szInfo;
113.         }
114. //+----------------+
115.         string Post_Order(void)
116.         {
117.             m_szInfo = "Post Order: ";
118.             Extra(root, ePostOrder);
119. 
120.             return m_szInfo;
121.         }
122. //+----------------+
123.     #undef def_InfoToString
124. //+----------------+
125. };
126. #undef C_TreeNode
127. //+------------------------------------------------------------------+
128. void OnStart(void)
129. {
130.     C_Tree <int> Tree;
131. 
132.     Tree.Store(10);
133.     Tree.Store(-6);
134.     Tree.Store(47);
135.     Tree.Store(35);
136.     Tree.Store(51);
137.     Tree.Store(90);
138.     Tree.Store(85);
139.     Tree.Store(40);
140. 
141.     Print(Tree.In_Order());
142.     Print(Tree.Pre_Order());
143.     Print(Tree.Post_Order());
144. }
145. //+------------------------------------------------------------------+

Código 01

En este Code 01 puedes observar que he eliminado algunas partes para adaptarlo al estudio del algoritmo de equilibrado. Al mismo tiempo, he realizado pequeños ajustes para dejarlo lo más compacto posible. En cualquier caso, la estructura del árbol generada por el código 01 se muestra en la imagen siguiente.

Imagem 05

Ahora, a partir de los conocimientos presentados en el artículo anterior, podrás examinar la estructura mostrada en la imagen 05 e imaginar cómo está construido el árbol. Es extremadamente importante que puedas hacerlo. De lo contrario, lo que veremos e implementaremos a continuación no tendrá ningún sentido. En cualquier caso, puedes notar claramente que los subárboles de la raíz tienen alturas diferentes. La pregunta es: ¿cuál es la diferencia entre ambas alturas?

Bien, esta es la parte interesante y divertida del artículo, porque, para calcular la diferencia de altura entre los subárboles, primero debes saber cómo está construido el árbol. Sin embargo, incluso sin conocer su disposición exacta, podemos implementar un fragmento de código que calcule el factor de equilibrio local de la raíz. El cálculo es bastante sencillo y directo. Solo tenemos que avanzar desde la raíz hasta la hoja más profunda del subárbol izquierdo y repetir el recorrido en el subárbol derecho. Si ambos subárboles tienen la misma altura, el factor será cero; si uno es más alto que el otro, el resultado será distinto de cero. Para comprobarlo, utilizaremos el fragmento de código que se muestra 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(T arg)
016.             :left(NULL),
017.             right(NULL),
018.             info(arg)
019.         {}
020. //+----------------+
021.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
022. //+----------------+
023.         void SetRight(C_TreeNode *ptr) { right = ptr; }
024. //+----------------+
025.         T GetInfo(void) const { return info; }
026. //+----------------+
027.         C_TreeNode *GetLeft(void) const { return left; }
028. //+----------------+
029.         C_TreeNode *GetRight(void) const { return right; }
030. //+----------------+
031. };
032. //+------------------------------------------------------------------+
033. #define C_TreeNode C_TreeNode<T>
034. template <typename T>
035. class C_Tree
036. {
037. //+----------------+
038.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
039.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy};
040. //+----------------+
041.     private :
042.         C_TreeNode *root;
043.         string      m_szInfo;
044. //+----------------+
045.         int countL(C_TreeNode *ptr)
046.         {
047.             int count = 0;
048. 
049.             while ((*ptr).GetLeft() != NULL)
050.             {
051.                 ptr = (*ptr).GetLeft();
052.                 count++;
053.                 if (((*ptr).GetLeft() == NULL) && ((*ptr).GetRight() != NULL)) while ((*ptr).GetRight() != NULL)
054.                 {
055.                     ptr = (*ptr).GetRight();
056.                     count++;
057.                 }
058.             }
059. 
060.             return count;
061.         }
062. //+----------------+
063.         int countR(C_TreeNode *ptr)
064.         {
065.             int count = 0;
066. 
067.             while ((*ptr).GetRight() != NULL)
068.             {
069.                 ptr = (*ptr).GetRight();
070.                 count++;
071.                 if (((*ptr).GetRight() == NULL) && ((*ptr).GetLeft() != NULL)) while ((*ptr).GetLeft() != NULL)
072.                 {
073.                     ptr = (*ptr).GetLeft();
074.                     count++;
075.                 }
076.             }
077. 
078.             return count;
079.         }
080. //+----------------+
081.         C_TreeNode *Insert(C_TreeNode *ptr, T info)
082.         {
083.             if (ptr == NULL)
084.                 return new C_TreeNode(info);
085. 
086.             if (info < (*ptr).GetInfo()) (*ptr).SetLeft(Insert((*ptr).GetLeft(), info));
087.             else (*ptr).SetRight(Insert((*ptr).GetRight(), info));
088. 
089.             return ptr;
090.         }
091. //+----------------+
092.         void Seq(C_TreeNode *ptr, const E_SEQ type)
093.         {
094.             if (ptr == NULL) return;
095. 
096.             switch (type)
097.             {
098.                 case eInOrder   :
099.                 case ePostOrder :
100.                 case eDestroy   :
101.                     Seq((*ptr).GetLeft(), type);
102.                     if (type == eInOrder) break;
103.                     Seq((*ptr).GetRight(), type);
104.             }
105.             m_szInfo += def_InfoToString(ptr);
106.             switch (type)
107.             {
108.                 case ePreOrder  :
109.                     Seq((*ptr).GetLeft(), type);
110.                 case eInOrder   :
111.                     Seq((*ptr).GetRight(), type);
112.                     break;
113.                 case eDestroy   :
114.                     delete ptr;
115.             }
116.         }
117. //+----------------+
118.     public  :
119. //+----------------+
120.         C_Tree()
121.             :root(NULL)
122.         {}
123. //+----------------+
124.         ~C_Tree()
125.         {
126.             Seq(root, eDestroy);
127.         }
128. //+----------------+
129.         void Store(T info)
130.         {
131.             if (root == NULL) root = Insert(root, info);
132.             else Insert(root, info);
133.         }
134. //+----------------+
135.         void CheckBalance(void)
136.         {
137.             Print("Balance: ", countR(root) - countL(root));
138.         }
139. //+----------------+
140.         string In_Order(void)
141.         {
142.             m_szInfo = "In Order: ";
143.             Seq(root, eInOrder);
144.             
145.             return m_szInfo;
146.         }
147. //+----------------+
148.         string Pre_Order(void)
149.         {
150.             m_szInfo = "Pre Order: ";
151.             Seq(root, ePreOrder);
152. 
153.             return m_szInfo;
154.         }
155. //+----------------+
156.         string Post_Order(void)
157.         {
158.             m_szInfo = "Post Order: ";
159.             Seq(root, ePostOrder);
160. 
161.             return m_szInfo;
162.         }
163. //+----------------+
164.     #undef def_InfoToString
165. //+----------------+
166. };
167. #undef C_TreeNode
168. //+------------------------------------------------------------------+
169. void OnStart(void)
170. {
171.     C_Tree <int> Tree;
172. 
173.     Tree.Store(10);
174.     Tree.Store(-6);
175.     Tree.Store(47);
176.     Tree.Store(35);
177.     Tree.Store(51);
178.     Tree.Store(90);
179.     Tree.Store(85);
180.     Tree.Store(40);
181. 
182.     Print(Tree.In_Order());
183.     Print(Tree.Pre_Order());
184.     Print(Tree.Post_Order());
185.     
186.     Tree.CheckBalance();
187. }
188. //+------------------------------------------------------------------+

Código 02

Al ejecutar este Code 02, verás el resultado que aparece a continuación.

Imagem 06

Observa el valor resaltado en la imagen 06. Corresponde al factor de equilibrio local de la raíz, calculado como la diferencia entre la altura de su subárbol derecho y la de su subárbol izquierdo. Como el valor es positivo, el subárbol derecho tiene mayor altura. En este caso, su altura supera en tres niveles la del subárbol izquierdo. El valor resaltado indica precisamente el factor local de la raíz; por sí solo, no describe el estado global del árbol. ¿Cómo puedo estar seguro de que no me estás engañando? Bien, mi querido lector, en el artículo anterior expliqué cómo reconstruir la estructura del árbol a partir de las salidas mostradas en las imágenes 05 y 06. Hazlo y comprenderás cómo logró el fragmento de código calcular el factor de equilibrio local de la raíz. Solo entonces el código 02 cobrará sentido para ti. Como quiero que estudies los artículos, no mostraré la estructura del árbol que puede reconstruirse a partir de esas dos salidas.

Muy bien, volviendo al código, podemos observar que utilizamos dos funciones para calcular la altura. Las declaraciones de las líneas 45 y 63 inician, respectivamente, cada una de esas funciones. La única diferencia entre ellas es el subárbol en el que se inicia la búsqueda de la hoja más profunda. Como ambas realizan el mismo recorrido, podemos sustituirlas por una única función parametrizada que calcule la altura del subárbol indicado. Esta función unificada se muestra en el fragmento siguiente.

                   .
                   .
                   .
044. //+----------------+
045.         int countLayers(C_TreeNode *ptr, const bool branchR)
046.         {
047.             int count = 0;
048. 
049.             while ((branchR ? (*ptr).GetRight() : (*ptr).GetLeft()) != NULL)
050.             {
051.                 ptr = (branchR ? (*ptr).GetRight() : (*ptr).GetLeft());
052.                 count++;
053.                 if (((branchR?(*ptr).GetRight():(*ptr).GetLeft())==NULL)&&((branchR?(*ptr).GetLeft():(*ptr).GetRight())!= NULL)) while((branchR?(*ptr).GetLeft():(*ptr).GetRight())!= NULL)
054.                 {
055.                     ptr = (branchR ? (*ptr).GetLeft() : (*ptr).GetRight());
056.                     count++;
057.                 }
058.             }
059. 
060.             return count;
061.         }
062. //+----------------+
                   .
                   .
                   .
116. //+----------------+
117.         void CheckBalance(void)
118.         {
119.             Print("Balance: ", countLayers(root, true) - countLayers(root, false));
120.         }
121. //+----------------+
                   .
                   .
                   .

Fragmento 01

Como el resto del código permanece sin cambios, no veo ningún motivo para repetirlo constantemente. Al mostrar únicamente las partes modificadas, será más fácil centrarnos en lo esencial. Bien, ya estamos calculando el factor de equilibrio local de la raíz. Ahora surge la pregunta: ¿en qué nos ayudará este factor? Lo que hemos hecho hasta aquí es solo una parte del cálculo necesario. Comparar las alturas de los subárboles izquierdo y derecho permite detectar el desequilibrio local de la raíz; para determinar el estado global del árbol, habrá que realizar el mismo cálculo en los demás nodos. La cuestión es: ¿cómo podemos corregir los factores locales que queden fuera del intervalo admitido? Existen varios métodos posibles, cada uno con sus ventajas y desventajas. Aquí utilizaremos rotaciones.

El equilibrado mediante rotaciones es relativamente sencillo. Cuando el factor de equilibrio local de un nodo queda fuera del intervalo admitido, se aplica una rotación a la izquierda o a la derecha sobre el subárbol cuya raíz es ese nodo. La rotación reasigna las relaciones padre-hijo dentro del subárbol afectado para restablecer su equilibrio local, sin alterar el criterio de ordenación: después de la reorganización, las claves menores siguen situadas a la izquierda y las mayores, a la derecha. Esta corrección local no implica por sí sola que todo el árbol haya recuperado el equilibrio global.

Para que puedas visualizarlo con mayor claridad, mi querido lector, observa la imagen siguiente.

Imagem 07

La clave que debes comprender, mi querido lector, es que una rotación cambia las relaciones padre-hijo, pero conserva la secuencia de claves obtenida mediante un recorrido en orden. En el ejemplo, los nodos con los valores 35 y 47 dejan de mantener la misma relación jerárquica, pero 35 sigue precediendo a 47 durante el recorrido. Al aplicar una rotación en un nodo cuyo factor de equilibrio local queda fuera del intervalo admitido, puede cambiar la raíz del subárbol y se corrigen los factores locales de los nodos afectados. Después deben actualizarse los factores de sus antecesores. El árbol solo queda equilibrado en su conjunto cuando el factor local de todos sus nodos se mantiene dentro del intervalo admitido.

Espera un momento. Antes de implementar el código de rotación, me preocupa el coste de calcular los factores de equilibrio locales. Supongamos que tenemos un árbol perfectamente equilibrado con una altura de unos 30 niveles. Y estamos hablando de un árbol que considero relativamente poco profundo. Si cada vez que insertamos un dato nuevo tenemos que recorrer todo el árbol para recalcular las alturas y comprobar si algún nodo presenta un factor de equilibrio fuera del límite admitido, la comprobación posterior a cada inserción acabará siendo bastante lenta. Para calcular el factor de un nodo, tendríamos que ejecutar la función mostrada en el fragmento 01 sobre sus dos subárboles. Repetir estos recorridos después de cada inserción sería ineficiente. Entonces, mi amigo autor, aunque el código se vuelva un poco más complejo, ¿no habría una forma más eficiente de actualizar la altura de cada nodo y calcular a partir de ella su factor de equilibrio? ¿No podría cada nodo almacenar la altura de su propio subárbol?

Hum, déjame pensarlo un momento. Sí, mi querido lector, tu planteamiento es completamente válido. Y sí, existe una forma de simplificar un poco las cosas. Para ello tendremos que realizar algunos cambios. Aun así, espero que hayas comprendido el plan que seguiremos. En cualquier caso, hagamos lo siguiente: como el objetivo aquí es didáctico, podemos añadir una variable adicional en cada nodo para registrar la altura del subárbol que tiene ese nodo como raíz. Aunque no vayamos a actualizarla constantemente, será mucho más rápido calcular el factor de equilibrio local a partir de las alturas registradas en los nodos hijos y determinar si debe aplicarse una rotación al subárbol. Y cuando sea necesario, lo haremos de la forma más eficiente posible. Por tanto, lo primero que debemos hacer es modificar la clase C_TreeNode, como se muestra en el fragmento siguiente. Trabajaremos con fragmentos para facilitar la comprensión de los cambios.

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. template <typename T>
05. class C_TreeNode
06. {
07.     private :
08. //+----------------+
09.         T           info;
10.         C_TreeNode  *left,
11.                     *right;
12.         int         prof;
13. //+----------------+
14.     public  :
15. //+----------------+
16.         C_TreeNode(T arg)
17.             :left(NULL),
18.             right(NULL),
19.             info(arg),
20.             prof(1)
21.         {}
22. //+----------------+
23.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
24. //+----------------+
25.         void SetRight(C_TreeNode *ptr) { right = ptr; }
26. //+----------------+
27.         void SetProf(const int arg) { prof = arg; }
28. //+----------------+
29.         int GetProf(void) { return prof; }
30. //+----------------+
31.         T GetInfo(void) const { return info; }
32. //+----------------+
33.         C_TreeNode *GetLeft(void) const { return left; }
34. //+----------------+
35.         C_TreeNode *GetRight(void) const { return right; }
36. //+----------------+
37. };
38. //+------------------------------------------------------------------+
                   .
                   .
                   .

Fragmento 02

Bien, ahora tenemos una nueva variable en la clase C_TreeNode. La instrucción de la línea 20 inicializa la variable que almacena la altura. Sin embargo, el valor asignado tiene una particularidad que explicaré más adelante, ya que en este momento no tendría sentido mencionar el efecto de modificarlo.

Muy bien, lo siguiente que debemos implementar es una forma de obtener la altura del subárbol cuya raíz es el nodo. Esto equivale al cálculo realizado en el fragmento 01, pero ahora lo haremos de una forma mucho más eficiente. Para ello, utilizaremos la función que se muestra a continuación.

                   .
                   .
                   .
50. //+----------------+
51.         int WhatProf(C_TreeNode *ptr)
52.         {
53.             C_TreeNode *p1, *p2;
54. 
55.             p1 = (*ptr).GetLeft();
56.             p2 = (*ptr).GetRight();
57. 
58.             if (p1 && p2)
59.                 return MathMax((*p1).GetProf(), (*p2).GetProf()) + 1;
60.             return  (p1 && (p2 == NULL) ? (*p1).GetProf() : (*p2).GetProf()) + 1;
61.         }
62. //+----------------+
                   .
                   .
                   .

Fragmento 03

Bien, observa que la función mostrada en el fragmento devolverá la altura registrada en el nodo. Volveremos sobre este punto más adelante. Por tanto, para calcular el factor de equilibrio local, tendremos que implementar otra función. Sin embargo, a diferencia de lo que hicimos antes, ahora NO UTILIZAREMOS EL FACTOR DE LA RAÍZ COMO MEDIDA GLOBAL DEL ÁRBOL, SINO QUE CALCULAREMOS EL FACTOR LOCAL DE CADA NODO. Este factor se obtiene a partir de la diferencia entre las alturas de los subárboles izquierdo y derecho del nodo correspondiente. El estado global de equilibrio no se expresa mediante un único factor: el árbol estará equilibrado en su conjunto cuando el factor local de todos sus nodos se mantenga dentro del intervalo admitido. Para realizar este cálculo, utilizaremos la función que se muestra en el fragmento siguiente.

                   .
                   .
                   .
62. //+----------------+
63.         int BalanceFactor(C_TreeNode *ptr)
64.         {
65.             C_TreeNode *p1, *p2;
66. 
67.             p1 = (*ptr).GetLeft();
68.             p2 = (*ptr).GetRight();
69. 
70.             if (p1 && p2) return ((*p1).GetProf() - (*p2).GetProf());
71.             return (p1 && (p2 == NULL) ? (*p1).GetProf() : -(*p2).GetProf());
72.         }
73. //+----------------+
                   .
                   .
                   .

Fragmento 04

Ahora presta atención, mi querido lector. La función mostrada en el fragmento 04 devolverá el factor de equilibrio local del nodo. Su signo indica cuál de sus subárboles tiene mayor altura, y su magnitud indica la diferencia entre ambas alturas. Con este factor podremos determinar qué rotación debe aplicarse al subárbol cuya raíz es ese nodo. Según la configuración de sus hijos, tendremos que realizar uno de los cuatro tipos de rotación. El fragmento de código correspondiente a cada rotación se muestra a continuación.

                   .
                   .
                   .
073. //+----------------+
074.         C_TreeNode *Rotation_R(C_TreeNode *ptr)
075.         {
076.             C_TreeNode *p1;
077.             
078.             p1 = (*ptr).GetRight();
079.             (*ptr).SetRight((*p1).GetLeft());
080.             (*p1).SetLeft(ptr);
081. 
082.             return p1;
083.         }
084. //+----------------+
085.         C_TreeNode *Rotation_L(C_TreeNode *ptr)
086.         {
087.             C_TreeNode *p1;
088.             
089.             p1 = (*ptr).GetLeft();
090.             (*ptr).SetLeft((*p1).GetRight());
091.             (*p1).SetRight(ptr);
092. 
093.             return p1;
094.         }
095. //+----------------+
096.         C_TreeNode *Rotation_2R(C_TreeNode *ptr)
097.         {
098.             C_TreeNode *p1, *p2;
099. 
100.             p1 = (*ptr).GetRight();
101.             p2 = (*p1).GetLeft();
102.             (*ptr).SetRight((*p2).GetLeft());
103.             (*p1).SetLeft((*p2).GetRight());
104.             (*p2).SetLeft(ptr);
105.             (*p2).SetRight(p1);
106. 
107.             return p2;
108.         }
109. //+----------------+
110.         C_TreeNode *Rotation_2L(C_TreeNode *ptr)
111.         {
112.             C_TreeNode *p1, *p2;
113. 
114.             p1 = (*ptr).GetLeft();
115.             p2 = (*p1).GetRight();
116.             (*ptr).SetLeft((*p2).GetRight());
117.             (*p1).SetRight((*p2).GetLeft());
118.             (*p2).SetRight(ptr);
119.             (*p2).SetLeft(p1);
120. 
121.             return p2;
122.         }
123. //+----------------+
                   .
                   .
                   .

Fragmento 05

Muy bien, para comprender este fragmento 05, utilizaremos las imágenes que aparecen a continuación.

Imagem 08

La imagen 08 muestra cómo la función cuya declaración comienza en la línea 74 reasigna las relaciones padre-hijo dentro del subárbol cuya raíz es el nodo marcado en rojo.

Imagem 09

La imagen 09 muestra cómo la función cuya declaración comienza en la línea 85 reasigna las relaciones padre-hijo dentro del subárbol afectado, sin modificar el orden de las claves.

Imagem 10

La imagen 10 muestra la reorganización de las relaciones padre-hijo que realiza la función cuya declaración comienza en la línea 96.

Imagem 11

Por último, la imagen 11 muestra cómo la función cuya declaración comienza en la línea 110 reorganiza las relaciones padre-hijo del subárbol. En las cuatro representaciones, el círculo rojo identifica el nodo que se pasa como argumento a las funciones del fragmento 05 y que actúa como raíz del subárbol antes de la rotación.

Sé que esto parece una de esas instrucciones para resolver un cubo de Rubik. Sin embargo, aunque a primera vista resulte bastante extraño, las cuatro imágenes anteriores muestran cómo cada rotación reasigna las relaciones padre-hijo del subárbol afectado para situar el factor de equilibrio local dentro del intervalo admitido, sin alterar el orden de las claves. Y hay un detalle: el algoritmo intentará mantener dentro de ese intervalo el factor local de cada nodo. Solo cuando esta condición se cumple en todos los nodos puede afirmarse que el árbol está equilibrado en su conjunto. Esto resulta bastante sorprendente, teniendo en cuenta la sencillez de estas rotaciones.

Bien, ¿cómo conseguirá el código restablecer el equilibrio global del árbol? Hasta ahora no he visto ninguna operación que actualice los factores locales a lo largo de la ruta de inserción y aplique las rotaciones necesarias en los subárboles afectados. Pues bien, mi querido lector, ahora viene la clave. Tendremos que realizar una pequeña modificación en el fragmento de código encargado de insertar datos en el árbol. Recuerda que, hasta este momento, hemos retirado temporalmente el fragmento encargado de eliminar nodos. Esto se debe a que quiero que comprendas muy bien cómo se actualizarán las alturas y se rotarán los subárboles afectados a medida que modifiquemos el árbol.

                   .
                   .
                   .
123. //+----------------+
124.         C_TreeNode *Insert(C_TreeNode *ptr, T info)
125.         {
126.             if (ptr == NULL)
127.                 return new C_TreeNode(info);
128. 
129.             if (info < (*ptr).GetInfo()) (*ptr).SetLeft(Insert((*ptr).GetLeft(), info));
130.             else (*ptr).SetRight(Insert((*ptr).GetRight(), info));
131. 
132.             (*ptr).SetProf(WhatProf(ptr));
133.             if ((BalanceFactor(ptr) == 2) && (BalanceFactor((*ptr).GetLeft()) == 1)) ptr = Rotation_L(ptr);
134.             else if ((BalanceFactor(ptr) == -2) && (BalanceFactor((*ptr).GetRight()) == -1)) ptr = Rotation_R(ptr);
135.             else if ((BalanceFactor(ptr) == -2) && (BalanceFactor((*ptr).GetRight()) == 1)) ptr = Rotation_2R(ptr);
136.             else if ((BalanceFactor(ptr) == 2) && (BalanceFactor((*ptr).GetLeft()) == -1)) ptr = Rotation_2L(ptr);
137. 
138.             return ptr;
139.         }
140. //+----------------+
                   .
                   .
                   .
177. //+----------------+
178.         void Store(T info)
179.         {
180.             root = Insert(root, info);
181.         }
182. //+----------------+
                   .
                   .
                   .
211. //+------------------------------------------------------------------+
212. void OnStart(void)
213. {
214.     C_Tree <int> Tree;
215. 
216.     Tree.Store(10);
217.     Tree.Store(-6);
218.     Tree.Store(47);
219.     Tree.Store(35);
220.     Tree.Store(51);
221.     Tree.Store(90);
222.     Tree.Store(85);
223.     Tree.Store(40);
224. 
225.     Print(Tree.In_Order());
226.     Print(Tree.Pre_Order());
227.     Print(Tree.Post_Order());
228. }
229. //+------------------------------------------------------------------+

Fragmento 06

Ahora observa las modificaciones realizadas en el fragmento de código encargado de insertar nuevos datos en el árbol. Ten en cuenta que, a medida que se construye el árbol, su raíz puede cambiar. Por este motivo, modificamos la instrucción de la línea 180, encargada de actualizar la referencia a la raíz. Quiero que comprendas especialmente las instrucciones comprendidas entre las líneas 132 y 136: actualizan la altura del nodo, calculan su factor de equilibrio local y determinan si debe rotarse el subárbol. Estas operaciones se repiten en los antecesores del nodo insertado, de modo que las correcciones locales terminan restableciendo el equilibrio global del árbol. Resulta impresionante que la actualización de la altura, el cálculo del factor local y la selección de la rotación requieran tan pocas instrucciones. Por eso no me detendré a explicar cada una; solo quiero que observes cómo se aplican a los antecesores del nodo insertado. Y no, no fui yo quien desarrolló este algoritmo. La estrategia aplicada corresponde al algoritmo de equilibrado AVL, denominado así en homenaje a los investigadores y matemáticos Adelson-Velsky y Landis, quienes publicaron este concepto en 1962. La implementación en MQL5 puro que ves aquí produce un árbol AVL.

Antes de terminar, quiero llamar tu atención sobre un detalle, mi querido lector. ¿Recuerdas la instrucción de la línea 20 del fragmento 02? Pues bien, si esa instrucción inicializa en uno la propiedad de altura del nodo, al compilar el código obtendremos la estructura del árbol mostrada en la imagen siguiente.

Imagem 12

Ahora presta atención al siguiente punto, porque esta es la parte sorprendente del algoritmo. Si cambias a cero el valor con el que la instrucción de la línea 20 del fragmento 02 inicializa la propiedad de altura, en lugar de asignarle uno, la estructura del árbol mostrada en la imagen 12 será distinta. Por tanto, realizando únicamente esta modificación en el código incluido en el anexo, obtendremos la nueva estructura que se muestra a continuación.

Imagem 13

Esto es sorprendente. Y precisamente por eso decidí presentar este algoritmo en el artículo.

Bien, ahora que ya sabes cómo se modifica el árbol a medida que se insertan nuevos datos, ¿qué te parece si vemos una propuesta para implementar la eliminación de nodos? Mi propuesta se muestra en el fragmento siguiente.

142. //+----------------+
143.         C_TreeNode *Erase(C_TreeNode *ptr, T info)
144.         {
145.             C_TreeNode *tmp;
146.             int         i;
147. 
148.             if (((*ptr).GetLeft() == NULL) && ((*ptr).GetRight() == NULL))
149.             {
150.                 delete ptr;
151.                 return NULL;
152.             }
153.             if ((*ptr).GetInfo() < info) (*ptr).SetRight(Erase((*ptr).GetRight(), info)); else
154.             if ((*ptr).GetInfo() > info) (*ptr).SetLeft(Erase((*ptr).GetLeft(), info)); else
155.             {
156.                 if ((*ptr).GetLeft() != NULL)
157.                 {
158.                     tmp = (*ptr).GetLeft();
159.                     while ((*tmp).GetRight() != NULL) tmp = (*tmp).GetRight();
160.                     (*ptr).SetInfo((*tmp).GetInfo());
161.                     (*ptr).SetLeft(Erase((*ptr).GetLeft(), (*tmp).GetInfo()));
162.                 }else
163.                 {
164.                     tmp = (*ptr).GetRight();
165.                     while ((*tmp).GetLeft() != NULL) tmp = (*tmp).GetLeft();
166.                     (*ptr).SetInfo((*tmp).GetInfo());
167.                     (*ptr).SetRight(Erase((*ptr).GetRight(), (*tmp).GetInfo()));
168.                 }
169.             }
170.             i = BalanceFactor(ptr);
171.             if (i > 1) ptr = (BalanceFactor((*ptr).GetLeft()) >= 0 ? Rotation_L(ptr) : Rotation_2L(ptr)); 
172.             else if (i < -1) ptr = (BalanceFactor((*ptr).GetRight()) <= 0 ? Rotation_R(ptr) : Rotation_2R(ptr)); 
173. 
174.             return ptr;
175.         }
176. //+----------------+
                   .
                   .
                   .
242. //+----------------+
243.         void DeleteNode(const T info)
244.         {
245.             root = Erase(root, info);
246.         }
247. //+----------------+
                   .
                   .
                   .
252. //+------------------------------------------------------------------+
253. void OnStart(void)
254. {
255.     C_Tree <int> Tree;
256. 
257.     Tree.Store(10);
258.     Tree.Store(-6);
259.     Tree.Store(47);
260.     Tree.Store(35);
261.     Tree.Store(51);
262.     Tree.Store(90);
263.     Tree.Store(85);
264.     Tree.Store(40);
265. 
266.     Print(Tree.In_Order());
267.     Print(Tree.Pre_Order());
268.     Print(Tree.Post_Order());
269. 
270.     Tree.DeleteNode(10);
271.     Tree.DeleteNode(-6);
272.     Print("-----------");
273.     Print(Tree.In_Order());
274.     Print(Tree.Pre_Order());
275.     Print(Tree.Post_Order());
276. }
277. //+------------------------------------------------------------------+

Fragmento 07

Por supuesto, también se modificaron algunas instrucciones en otras partes del código para evitar que falle al intentar eliminar un nodo. Sin embargo, como son cambios menores y dispondrás del código completo en el archivo adjunto para estudiar su funcionamiento, no considero necesario mostrarlos ni explicarlos. No obstante, quiero que observes que las instrucciones de las líneas 270 y 271 eliminan por completo el subárbol izquierdo de la raíz. Si no aplicáramos nuevas rotaciones, no quedaría ningún nodo en ese lado. Sin embargo, las rotaciones posteriores a la eliminación reasignarán las relaciones padre-hijo de los subárboles afectados y volverán a situar dentro del intervalo admitido los factores locales de los nodos modificados y de sus antecesores. Cuando finalicen esas actualizaciones, el árbol recuperará el equilibrio global y adoptará la configuración que se muestra en la imagen siguiente.

Imagem 14

Consideraciones finales

En este artículo hemos mostrado cómo funciona un algoritmo de equilibrado de un árbol. El algoritmo presentado aquí es solo uno de los muchos que pueden implementarse. Esta versión concreta corresponde únicamente a mi propuesta de implementación. Existen métodos más o menos elaborados: algunos reducen la altura del árbol y, con ello, la longitud máxima de los recorridos; otros limitan la diferencia de altura entre los subárboles de cada nodo. Sin embargo, lo importante es que comprendas la importancia de equilibrar el árbol y cómo puede hacerse. El método concreto importa poco, siempre que distingas entre el factor de equilibrio local de cada nodo y el estado global de la estructura. El árbol queda equilibrado en su conjunto cuando los factores locales de todos sus nodos se mantienen dentro del intervalo admitido; no existe un único factor global que describa por sí solo ese estado. La altura del árbol establece un límite para la cantidad de nodos que puede recorrer una búsqueda, mientras que su tiempo de ejecución concreto depende de la ruta seguida y del trabajo realizado en cada nodo.

La parte relacionada con los algoritmos de búsqueda y los recorridos de árboles es muy interesante. Sin embargo, la veremos en otro momento, ya que, por ahora, creo que necesitas tiempo para asimilar las operaciones de inserción, actualización de alturas, cálculo de factores de equilibrio y rotación estudiadas hasta aquí. Por tanto, en el próximo artículo trataremos otro tema, lo que te permitirá estudiar con calma este material.

Además, todavía debemos abordar otros conceptos sobre la implementación de árboles. Esto será necesario cuando estudiemos las operaciones de búsqueda en el árbol.

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