23. Árboles Binarios de Búsqueda Balanceados

Una de las propiedades fundamentales de los árboles binarios de búsqueda es que preservan al orden de los elementos, y por lo tanto se pueden usar como contenedores de datos para implementar estructuras más complejas que requieran mantener el orden de los elementos, como por ejemplo diccionarios, listas ordenadas, etc.

La eficiencia de las operaciones de búsqueda, inserción y eliminación en un árbol binario de búsqueda depende en gran medida de su altura. En el peor de los casos, las operaciones pueden ser de orden lineal \(O(n)\). Para evitar esto, se utilizan árboles binarios de búsqueda balanceados, que mantienen la altura del árbol en un nivel logarítmico \(O(log (n))\) al garantizar que la diferencia entre las alturas de los subárboles izquierdo y derecho sea mínima.

Existen diferentes tipos de árboles binarios de búsqueda balanceados, como los árboles AVL y los árboles rojo y negro. Estos árboles implementan diferentes algoritmos de balanceo para garantizar que la altura del árbol se mantenga equilibrada después de cada operación de inserción o eliminación.

23.1. Árboles AVL

En 1962, dos científicos soviéticos, Georgy Adelson-Velsky y Evgenii Landis, publicaron un artículo titulado “An algorithm for the organization of information” (Un algoritmo para la organización de la información). En este trabajo, introdujeron la primera estructura de datos de árbol binario de búsqueda auto-balanceado conocido como árbol AVL.

El nombre “AVL” proviene de las iniciales de sus inventores. Su principal innovación fue definir una condición de balanceo estricta que debía mantenerse en cada nodo del árbol:

La diferencia en la altura entre los subárboles izquierdo y derecho de cualquier nodo no puede ser mayor que uno.

Formalmente:

Definición de Árbol AVL

\[\begin{split}\text{AVL } \text{si} \begin{cases} \text{ ABB nulo} \\ \text{}\\ \text{ABB no nulo} \begin{cases} |h_{izq} - h_{der}| \leq 1 \\ \text{subárbol izquierdo} \text{ es AVL} \\ \text{subárbol derecho} \text{ es AVL} \\ \end{cases} \end{cases}\end{split}\]

En esta definición aparece el concepto de factor de balanceo o factor de equilibrio de un nodo, que se define como la diferencia entre las alturas de los subárboles izquierdo y derecho:

\[fb(n) = h_{izq} - h_{der}\]

En la siguiente figura se muestra un árbol binario de búsqueda y los factores de balanceo de cada uno de sus nodos.

Si bien la raíz está balanceada, el árbol no es AVL ya que hay varios nodos que están desbalanceados. En este caso, el nodo 54 tiene un factor de balanceo de -2, lo que significa que su subárbol derecho es dos veces más alto que su subárbol izquierdo. Por lo tanto, el árbol no cumple con la condición de balanceo.

Figura 23.1 Factores de balanceo de cada nodo de un ABB

Los árboles AVL son árboles autobalanceados, es decir que se ajustan automáticamente después de cada operación de inserción o eliminación para mantener la propiedad de balanceo. Esto se logra mediante rotaciones, que son operaciones que cambian la estructura del árbol sin afectar el orden de los elementos. Las rotaciones son de orden \(O(1)\) y por lo tanto no afectan la complejidad de las operaciones de búsqueda, inserción y eliminación, que siguen siendo \(O(log (n))\).

23.2. Rotaciones

Las rotaciones pueden ser simples o dobles. Las rotaciones simples son suficientes para corregir la mayoría de los desbalances, pero en algunos casos se requieren rotaciones dobles.

Supongamos que tenemos un árbol AVL como el de la figura que usaremos para graficar las rotaciones.

Figura 23.2 Árbol AVL balanceado

23.2.1. Rotación simple a derecha

Supongamos que en {AVL} se inserta el (18), lo que desbalancea el nodo (23). Si observamos el (23) se desbalanceo cuando se insertó un elemento a la izquierda de su subárbol izquierdo y este desbalanceo solo es local, ya que tanto el (17) como el (50) permanecen balanceados.

Figura 23.3 Desbalanceo Izquierda-Izquierda de un nodo

Para restaurar el equilibrio del nodo (23) se debe realizar una rotación simple a la derecha del (23). Esta rotación involucra a tres nodos el (23), el (19) y el recién insertado (18). En la siguiente figura se observa la rotación simple a derecha.

Figura 23.4 Rotación simple a derecha

Una vez realizada la rotación, todo el árbol queda restaurado, como se observa en la siguiente figura.

Figura 23.5 AVL restaurado luego de una rotación simple a derecha

23.2.2. Rotación simple a izquierda

Analogamente cuando en un nodo se produce un desbalance por la inserción de un elemento a la derecha de su hijo derecho, se puede reestablecer el balance con una rotación simple a izquierda.

Figura 23.6 Desbalanceo Derecha-Derecha de un nodo

En la figura al insertar el nodo (70) de desbalancea el nodo (54), que se puede volver a balancear con una rotación a la izquierda del nodo (54)

Figura 23.7 Rotación simple a izquierda

Figura 23.8 AVL restaurado luego de una rotación simple a izquierda

23.2.3. Rotación doble izquierda-derecha

Cuando el desbalance se produce al insertar un elemento a la derecha del hijo izquierdo de un nodo se debe realizar una rotación doble. Las rotaciones doble se componen de dos rotaciones simples, en este caso de una rotación simple a la izquierda seguida de una rotación simple a la derecha.

En la siguiente figura al insertar el (16), se desbalanceó el (17). Parados en el (17) el desbalance se produce al insertar un elemento a la derecha de su hijo izquierdo.

Figura 23.9 Desbalanceo Izquierda-Derecha de un nodo

Para restaurar el balance se preciso realizar dos rotaciones simples, la primera es rotar el hijo izquierdo del nodo desbalanceado, es decir el (12) a la izquierda (aunque el (12) se encuentre balanceado) y luego rotar el nodo desbalanceado originalmente a la derecha.

Figura 23.10 Desbalanceo Izquierda-Derecha, rotación a izquierda del hijo del nodo desbalanceado

Luego de la primera rotación a izquierda queda:

Figura 23.11 Desbalanceo Izquierda-Derecha, luego de la rotación a izquierda.

Luego se rota el (17) a derecha. Se observa que el (14) que pasará a ocupar la posición actual del (17) ya tiene un hijo derecho (16) que deberá reacomodarse como hijo izquierdo del (17)

Figura 23.12 Desbalanceo Izquierda-Derecha, rotación a derecha del nodo desbalanceado

Finalmente el árbol rebalanceado queda como en la siguiente figura

Figura 23.13 Desbalanceo Izquierda-Derecha, árbol rebalanceado

23.2.4. Rotación doble derecha-izquierda

En la siguiente figura se observa que al insertar el (73) se desbalancea el nodo (72). El (73) se insertó bajando una vez a la derecha y dos veces a la izquierda desde el (72), es decir la inserción fue derecha-izquierda, por lo que para reestablecer el balance se deberá realizar una rotación doble derecha-izquierda del (72)

Figura 23.14 Desbalanceo Derecha-Izquierda de un nodo

En la siguiente figura se observa los nodos involucrados en la rotación doble; que se puede realizar como dos rotaciones simples como en el ejemplo anterior o directamente en un único paso, donde el (74) pasará a ocupar la posición del (72).

Figura 23.15 Desbalanceo Derecha-Izquierda, nodos involucrados en la rotación derecha-izquierda

Como (74) tiene un hijo izquierdo, el nodo (73) recién agregado, entonces deberá ir al subárbol derecho del (72) para mantener la propiedad de búsqueda del ABB, y la única ubicación posible es como hijo derecho del (72), como se observa en la siguiente figura.

Figura 23.16 Desbalanceo Derecha-Izquierda, árbol rebalanceado

Importante

Las rotaciones son operaciones locales que solo afectan a un pequeño número de nodos en el árbol. Cuando se inserta un nuevo nodo, en el camino de regreso a la raíz, se verifica el balanceo de cada nodo y se realizan las rotaciones necesarias. Siempre las rotaciones se realizan en el camino de regreso a la raíz, es decir, desde el nodo recién insertado hasta la raíz del árbol.

En el siguiente enlace encontrarán un visualizador de árboles AVL que permite ver cómo se realizan las rotaciones y el balanceo del árbol en tiempo real:

Visualizador de Árboles AVL.

23.3. Ejercicios

1. Dado el siguiente árbol AVL, inserte los siguientes elementos en el árbol y dibuje el árbol resultante después de cada inserción: 10, 20, 30, 40, 50, 25.

2. Dado el siguiente árbol AVL, elimine los siguientes elementos del árbol y dibuje el árbol resultante después de cada eliminación: 30, 20, 10.

3. Dado el siguiente árbol AVL, determine el factor de balanceo de cada nodo y dibuje el árbol resultante después de cada rotación necesaria para mantener el equilibrio: 10, 20, 30, 40, 50, 25.

4. Escribir un método en árbol binario de búsqueda con el nombre esAVLque devuelva True si el árbol es AVL y False en caso contrario.

5. Implementar un árbol AVL en Go y realizar las operaciones de inserción, eliminación y búsqueda.