Como dije en la entrada anterior, el problema de los árboles binarios de búsqueda (ABB) es que si no están bien balanceados pierden mucha efectividad, el caso extremo es introducir los datos en orden, ya que estamos generando una lista pero con la ocupación y la mayor complejidad de un árbol.
Balancear el árbol significa que en cada nodo los elementos que cuelguen por su izquierda sean los mismos que los que cuelgan por su derecha, esta circunstancia ideal es compleja, por lo que se mira que la profundidad de las dos ramas sea la misma, un sistema un poco mas sencillo de conseguir y que sigue manteniendo el balanceo. Si una rama tiene elementos de mas profundidad que la otra, el árbol se balancea para compensarlo mediante lo que se denomina una rotación.
Aunque existen varias formas de montar los ABB balanceados, las formas mas utilizadas en general son los siguientes (aunque en general se usan solo los tres primeros):
- Los árboles AVL son los ABB auto-balanceados mas antiguos y los que consiguen mantener el mejor balanceo.
- Los montículos son ABB balanceados almacenados en forma de arreglo, mas adelante los usaremos en el conocido algoritmo de ordenación Heapsort.
- Los árboles rojo-negro son menos estrictos en el balanceo, permitiendo ligeras descompensaciones, por lo que son un poco mas ágiles en inserciones.
- Los árboles AA son una variación de los rojo-negro que simplifica mas las inserciones.
- Los árboles biselados son ABB balanceados cuyos nodos recientemente visitados se rotan para que aparezcan lo antes posible en las búsquedas.
- Los árboles de Fibonacci son una variante de los AVL.
En una árbol AVL hay que conocer la profuncidad de cada rama del árbol, para poder mantenerlo siempre balanceado. Si la profundidad de la rama izquierda difiere en más de una unidad de la profundidad de la rama derecha, el árbol está desbalanceado y se procede a efectuar una rotación para equilibrarlo, se retrocede al padre de ese nodo y se repite la operación, subiendo hacia la raíz hasta que no se requieran mas balanceos. Para poder ir subiendo por las ramas del árbol debemos guardar el camino recorrido, lo que se consigue de forma sencilla usando recursividad en lugar de iteración, por eso cambiaremos el algoritmo de inserción para convertirlo en recursivo.
Para equilibrar un árbol hay que mover nodos, en lo que se denominan rotaciones, se basan en ver la diferencia de profundidad de un nodo entre sus ramas izquierda y derecha, y si la diferencia es mayor de 1 realizar una rotación en el nodo, intercambiándolo con su hijo. Depende del hijo que usemos para rotar se denominará rotación a la izquierda o rotación a la derecha, pero ambas son equivalentes. También dependiendo del nodo ocupado del elemento hijo se usará una rotación simple o una doble. Pongo un ejemplo sencillo de rotación simple a la derecha y otro de rotación doble izquierda-derecha:
Vemos que en primer caso el nodo 1 es el que usamos para rotar, ya que tiene cero hijos por su izquierda y dos por su derecha necesita una rotación derecha. Colgamos el nodo (1) a la izquierda de su nodo hijo (2), y luego colgamos el nodo hijo (2) en lugar del nodo seleccionado. Podemos imaginar que estiramos hacia arriba del nodo (2).
Si el nodo izquierdo está ocupado, no es posible poner allí el nodo seleccionado, por lo que necesitamos dos pasos, primero colgamos el nodo hijo (3) a la derecha de su sub-nodo izquierdo (2), y luego colgamos el sub-nodo izquierdo del nodo seleccionado (1). Ahora tenemos ya el caso anterior y usando el mismo sistema equilibramos el árbol.
Entendiendo bien esto es muy sencillo equilibrar los árboles en las altas y bajas, solo hay que ir subiendo por el árbol a partir del nodo seleccionado, ver las profundidades de ambos nodos, y actuar en consecuencia. Hay varios sistemas para mantener las alturas en el árbol, lo mas sencillo es guardar la altura de las sub-ramas izquierda y derecha pero necesitamos dos valores en cada nodo, la otra forma es mantener solo la diferencia de alturas y así usamos un solo valor en cada nodo.
No hay comentarios:
Publicar un comentario