Por Jocselyn Cortez Lacayo - Estudiante de la carrera de Informática

Un árbol AVL es un árbol binario de búsqueda, eso quiere decir que está estructurado a través de nodos donde el subárbol izquierdo cumple con que todos los nodos son menores que la raíz, y el subárbol derecho cumple con que todos los nodos son mayores a la raíz. Sin embargo, cumplen una misma condición: la diferencia de las alturas de los subárboles va a ser máximo de 1, por lo general, eso definiría el equilibrio. Las siglas AVL (Adelson-Velskii y Landis) vienen del derivado de los creadores.

El árbol AVL, tanto en la parte izquierda como la derecha, tiene que cumplir con el mismo equilibrio, por lo tanto, cuando hay un desequilibrio, por ejemplo (+2 o -2), la complejidad que brinda va a ser en desorden, por lo cual se han creado varios métodos para llevarlos al equilibrio. Según Estructura de datos II, el reequilibrado recorre los ascendientes del nodo que ha sufrido modificación recalculando sus factores de equilibrio y aplicando las rotaciones adecuadas cuando es necesario. También es necesario controlar el cambio de altura de los subárboles dH a lo largo del recorrido; por ejemplo, cuando hay un factor de equilibrio, la parte izquierda es -1, eso define que hay más nodo de ese lado; el 0 tienen los mismos nodos ambas partes y la parte derecha 1, conforme a ellos nos damos cuenta de que tienen más al lado derecho.

Para poder controlar el cambio existe dos maneras: una de ellas es la inserción, que se basa en agregar un elemento para modificar la estructura para llevar un balance (Inserción en árboles AVL, s.f.). Esto se lleva a cabo aplicando solo una rotación que corresponda, según la forma que le quedó al árbol. La otra manera es la extracción o el borrado, que también se basa en llevar un equilibrio cuando se excede alguna de las partes.

En la siguiente figura vemos un ejemplo del árbol AVL.

Nota: En la figura 1 se muestra la diferencia de las alturas de todos los subárboles de los nodos es menor o igual a 1.

Fuente: Inserción en árboles AVL, s.f.

 

Rotación simple izquierda
Rotación simple izquierda es cuando un nodo está cargado a la derecha, pero no está cargado a la izquierda.

Rotación simple derecha
Rotación simple derecha es cuando un nodo está cargado a la izquierda, pero no está cargado a la derecha. Según Pozo (2001), 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 o 0, es decir, que esté cargado a la izquierda o equilibrado.

Rotación doble izquierda
Rotación doble izquierda es una rotación simple a la derecha y una rotación simple a la izquierda. Según Pozo (2001) 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.

Rotación doble derecha
Rotación doble derecha es una rotación simple a la izquierda y luego una simple a la derecha. En este caso, se trata de lo contrario de rotación doble izquierda.

En fin, todo este proceso es para llevar un orden en la estructura de datos con el fin de tener un mejor acceso a ellos. Esto, proporciona mejor tiempo y mayor eficacia a la hora de crear códigos, por ejemplo en los arreglos o listas donde la complejidad sea mejor y en caso de no serlo hay métodos que faciliten el arreglo de la complejidad.

 

MOXIE es el Canal de ULACIT (www.ulacit.ac.cr), producido por y para los estudiantes universitarios, en alianza con el medio periodístico independiente Delfino.cr, con el propósito de brindarles un espacio para generar y difundir sus ideas.  Se llama Moxie - que en inglés urbano significa tener la capacidad de enfrentar las dificultades con inteligencia, audacia y valentía - en honor a nuestros alumnos, cuyo “moxie” los caracteriza.

Referencias bibliográficas:
• Estructura de datos ll. (s.f.). Árbol AVL. Recuperado de https://estructurasite.wordpress.com/arbol-avl/
• Inserción de árboles AVL. (s.f.). Definición. Recuperado de http://163.10.22.82/OAS/AVL_Insercion/definicin.html
• Pozo, S (2001). Estructura de datos. Recuperado de http://www.conclase.net/c/edd/?cap=000#inicio