Un árbol AVL es un árbol binario de búsqueda que cumple con la condición de que la diferencia entre las alturas de los subárboles de cada uno de sus nodos es, como mucho 1. La denominación de árbol AVL viene dada por los creadores de tal estructura (Adelson-Velskii y Landis). Formalmente se define un árbol AVL como un árbol binario de búsqueda auto balanceado en el cual se debe cumplir la siguiente condición: “Para todo nodo del árbol, la altura de la rama derecha e izquierda no debe diferir en más de una unidad”. La condición anterior es la que define al término «factor de equilibrio». (Caicedo, Wagner & Méndez, 2010) FE = HRD – HRI
Por lo tanto, el factor de equilibro de todos los nodos de un árbol AVL puede ser -1, 0 o +1. (Gómez & Ania, 2008).
Las operaciones básicas de un árbol AVL implican generalmente el realizar los mismos algoritmos que serían realizados en un árbol binario de búsqueda desequilibrado, pero precedido o seguido por una o más de las llamadas "rotaciones AVL".
ROTACIÓN SIMPLE A LA DERECHA.
De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i’) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (r), el hijo derecho de i (d’) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d).
ROTACIÓN SIMPLE A LA IZQUIERDA.
De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), consiste en formar un nuevo árbol cuya raíz sea la raíz del hijo derecho, como hijo derecho colocamos el hijo derecho de d (nuestro d’) y como hijo izquierdo construimos un nuevo árbol que tendrá como raíz la raíz del árbol (r), el hijo izquierdo de d será el hijo derecho (i’) y el hijo izquierdo será el hijo izquierdo del árbol (i).
ROTACIÓN DOBLE A LA DERECHA.
La Rotación doble a la Derecha son dos rotaciones simples, primero rotación simple izquierda y luego rotación simple derecha.
ROTACIÓN DOBLE A LA IZQUIERDA.
La Rotación doble a la Izquierda son dos rotaciones simples, primero rotación simple derecha y luego rotación simple izquierda.
Operaciones:
Para la inserción es necesario buscar hasta encontrar la posición de inserción o modificación, insertar el nuevo nodo con factor de equilibrio “equilibrado”, desandar el camino de búsqueda, verificando el equilibrio de los nodos, reequilibrando si es necesario.
El procedimiento de borrado es el mismo que en el caso de árbol binario de búsqueda, la diferencia se encuentra en el proceso de reequilibrado posterior.
Un ejemplo de la utilización e importancia del árbol avl:
Se quiere enriquecer el teléfono celular para que muestre información de la persona que está llamando cuando el mismo no se encuentra en la agenda de contactos. Para esto, cuando el teléfono suena, se debe obtener inmediatamente la información del abonado a partir de su número telefónico. Supongamos que la lista de abonados contiene 800.000 abonados. En este caso de uso puede verse claramente la importancia de obtener los datos en el menor tiempo posible. Esto no sería posible utilizando un árbol binario de búsqueda, ya que, en el peor de los casos, será necesario recorrer los N abonados, es decir, los 800.000 abonados para obtener la información. Si utilizamos un árbol AVL será necesario recorrer a lo sumo log2 (N), es decir, 20 abonados.
Referencias
Sebastián Gurin, 2004, Árbol avl, http://www.ibiblio.org/pub/Linux/docs/LuCaS/Tutoriales/doc-programacion-arboles-avl/avl-trees.pdf