RBOLES AVL INTRODUCCIN

- Supongamos que deseamos construir un ABB para la siguiente tabla de datos:

- Ha resultado un rbol muy poco balanceado y con caractersticas muy pobres para la bsqueda. Los ABB trabajan muy bien para una amplia variedad de aplicaciones, pero tienen el problema de que la eficiencia en el peor caso es O(n). Los rboles APO nos darn una idea de cmo podra resolverse el problema garantizando en el peor caso un tiempo O(log2 n).

RBOLES EQUILIBRADOS AVL

- Diremos que un rbol binario est equilibrado (en el sentido de Addelson-Velskii y Landis) si, para cada uno de sus nodos ocurre que las alturas de sus dos subrboles difieren como mucho en 1. Los rboles que cumplen esta condicin son denominados a menudo rboles AVL.

- A travs de los rboles AVL llegaremos a un procedimiento de bsqueda anlogo al de los ABB pero con la ventaja de garantizaremos un caso peor de O(log2 n), manteniendo el rbol en todo momento equilibrado.

- Veamos ahora la forma en que puede afectar una insercin en un rbol AVL y la forma en que deberamos reorganizar los nodos de manera que siga equilibrado. Consideremos el esquema general de la siguiente figura, supongamos que la insercin ha provocado que el subrbol que cuelga de Ai pasa a tener una altura 2 unidades mayor que el subrbol que cuelga de Ad . Qu operaciones son necesarias para que el nodo r tenga 2 subrboles que cumplan la propiedad de rboles AVL?.

La insercin se ha realizado en el rbol A. La operacin a realizar es la de una rotacin simple a la derecha sobre el nodo r resultando el rbol mostrado en la siguiente figura.

La insercin se ha realizado en el rbol B. (supongamos tiene raz b, subrbol izquierdo B1 y subrbol derecho B2). La operacin a realizar es la rotacin doble izquierda-derecha la cual es equivalente a realizar una rotacin simple a la izquierda sobre el nodo Ai y despus una rotacin simple a la derecha sobre el nodo r (por tanto, el rbol B queda dividido). El resultado se muestra en la figura siguiente:

- En el caso de que la insercin se realice en el subrbol Ad la situacin es la simtrica y para las posibles violaciones de equilibrio se aplicar la misma tcnica mediante la rotacin simple a la izquierda o la rotacin doble izquierda-derecha. Se puede comprobar que si los subrboles Ad y Ai son rboles AVL, estas operaciones hacen que el rbol resultante tambin sea AVL.