Árboles AVL

Árboles AVL (estructura dinámica de datos) Concepto: Un árbol AVL es un árbol binario de búsqueda en el que para cada nodo, las alturas de sus subárboles izquierdo y derecho no difieren en más de 1.

Árbol AVL. Llamado así por las iniciales de sus inventores: Adelson-Velskii y Landis. No se trata de árboles perfectamente equilibrados, pero sí son lo suficientemente equilibrados como para que su comportamiento sea lo bastante bueno como para usarlos donde los ABB no garantizan tiempos de búsqueda óptimos.

Operaciones en AVL

Los AVL son también ABB, de modo que mantienen todas las operaciones que poseen éstos. Las nuevas operaciones son las de equilibrar el árbol, pero eso se hace como parte de las operaciones de insertado y borrado.

Factor de equilibro

Cada nodo, además de la información que se pretende almacenar, debe tener los dos punteros a los árboles derecho e izquierdo, igual que los ABB, y además un miembro nuevo: el factor de equilibrio. El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo:

• FE = altura subárbol derecho - altura subárbol izquierdo;

Por definición, para un árbol AVL, este valor debe ser -1, 0 ó 1.

Rotaciones simples de nodos

Los reequilibrados se realizan mediante rotaciones, posibles rotaciones que se pueden aplicar.

• Rotación simple a la derecha (SD): Esta rotación se usará cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el derecho, es decir, cuando su FE sea de -2. Y además, la raíz del subárbol izquierdo tenga una FE de -1, es decir, que esté cargado a la izquierda.
• Rotación simple a la izquierda (SI): Se trata del caso simétrico del anterior. Esta rotación se usará cuando el subárbol derecho de un nodo sea 2 unidades más alto que el izquierdo, es decir, cuando su FE sea de 2. Y además, la raíz del subárbol derecho tenga una FE de 1, es decir, que esté cargado a la derecha.

Rotaciones dobles de nodos

• Rotación doble a la derecha (DD): Esta rotación se usará cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el derecho, es decir, cuando su FE sea de -2. Y además, la raíz del subárbol izquierdo tenga una FE de 1, es decir, que esté cargado a la derecha.
• Rotación doble a la izquierda (DI): Esta rotación se usará cuando el subárbol derecho de un nodo sea 2 unidades más alto que el izquierdo, es decir, cuando su FE sea de 2. Y además, la raíz del subárbol derecho tenga una FE de -1, es decir, que esté cargado a la izquierda. Se trata del caso simétrico del anterior.

Fuente

• Pozo Salvador. Estructura Dinámica de datos. Disponible en:Con Clase: http://www.conclase.net