Un árbol AVL definido como un autoequilibrio La diferencia entre las alturas del subárbol izquierdo y el subárbol derecho para cualquier nodo se conoce como factor de equilibrio del nodo.

El árbol AVL lleva el nombre de sus inventores, Georgy Adelson-Velsky y Evgenii Landis, quienes lo publicaron en su artículo de 1962 Un algoritmo para la organización de la información.

clasificación de lista de matrices java

Ejemplo de árboles AVL:

árbol AVL

El árbol anterior es AVL porque las diferencias entre las alturas de los subárboles izquierdo y derecho para cada nodo son menores o iguales a 1.

Operaciones en un árbol AVL:

• Inserción
• Supresión
• buscando [Es similar a realizar una búsqueda en BST]

Rotar los subárboles en un árbol AVL:

Un árbol AVL puede rotar de una de las cuatro formas siguientes para mantenerse equilibrado:

fecha local

Rotación izquierda :

Cuando se agrega un nodo al subárbol derecho del subárbol derecho, si el árbol se desequilibra, hacemos una sola rotación hacia la izquierda.

Rotación a la izquierda en el árbol AVL

Rotación derecha :

Si se agrega un nodo al subárbol izquierdo del subárbol izquierdo, el árbol AVL puede desequilibrarse, hacemos una sola rotación hacia la derecha.

Rotación a la derecha en el árbol AVL

Rotación izquierda-derecha :

¿Qué es el mapa de Java?

Una rotación de izquierda a derecha es una combinación en la que la primera rotación a la izquierda tiene lugar después de que se ejecuta la rotación a la derecha.

fecha java ahora

Rotación izquierda-derecha en el árbol AVL

Rotación derecha-izquierda :

Una rotación de derecha a izquierda es una combinación en la que la primera rotación a la derecha tiene lugar después de que se ejecuta la rotación a la izquierda.

Rotación derecha-izquierda en el árbol AVL

Aplicaciones del árbol AVL:

1. Se utiliza para indexar registros enormes en una base de datos y también para buscar de manera eficiente en ella.
2. Para todo tipo de colecciones en memoria, incluidos conjuntos y diccionarios, se utilizan árboles AVL.
3. Aplicaciones de bases de datos, donde las inserciones y eliminaciones son menos comunes pero son necesarias búsquedas frecuentes de datos.
4. Software que necesita búsqueda optimizada.
5. Se aplica en áreas corporativas y juegos argumentales.

Ventajas del árbol AVL:

1. Los árboles AVL pueden autoequilibrarse.
2. Seguramente no está sesgado.
3. Proporciona búsquedas más rápidas que los árboles rojo-negro.
4. Mejor complejidad del tiempo de búsqueda en comparación con otros árboles como el árbol binario.
5. La altura no puede exceder log(N), donde N es el número total de nodos en el árbol.

Desventajas del árbol AVL:

1. Es difícil de implementar.
2. Tiene factores constantes altos para algunas de las operaciones.
3. Menos utilizado en comparación con los árboles Rojo-Negro.
4. Debido a su equilibrio bastante estricto, los árboles AVL proporcionan operaciones complicadas de inserción y eliminación a medida que se realizan más rotaciones.
5. Tome más procesamiento para equilibrar.

Artículos relacionados:

• Introducción a los árboles de búsqueda binaria: tutoriales de algoritmos y estructura de datos
• Inserción en un árbol AVL
• Eliminación en un árbol AVL