¿Qué es un árbol AVL?
Un árbol AVL es un subtipo de árbol de búsqueda binaria. Los árboles AVL, que llevan el nombre de sus inventores Adelson, Velskii y Landis, tienen la propiedad de autoequilibrio dinámico además de todas las propiedades que muestran los árboles de búsqueda binaria.
Un BST es una estructura de datos compuesta por nodos. Tiene las siguientes garantías:
- Cada árbol tiene un nodo raíz (en la parte superior).
- El nodo raíz tiene cero, uno o dos nodos secundarios.
- Cada nodo secundario tiene cero, uno o dos nodos secundarios, etc.
- Cada nodo tiene hasta dos hijos.
- Para cada nodo, sus descendientes izquierdos son menores que el nodo actual, que es menor que los descendientes derechos.
Los árboles AVL tienen una garantía adicional:
- La diferencia entre la profundidad de los subárboles derecho e izquierdo no puede ser más de uno. Para mantener esta garantía, una implementación de un AVL incluirá un algoritmo para reequilibrar el árbol cuando la adición de un elemento adicional altere esta garantía.
Los árboles AVL tienen el peor tiempo de búsqueda, inserción y eliminación de O (log n).
Rotación Derecha
Rotación izquierda
Proceso de inserción AVL
Hará una inserción similar a la inserción normal del árbol de búsqueda binaria. Después de insertar, corrige la propiedad AVL usando rotaciones hacia la izquierda o hacia la derecha.
- Si hay un desequilibrio en el hijo izquierdo del subárbol derecho, realiza una rotación de izquierda a derecha.
- Si hay un desequilibrio en el hijo izquierdo del subárbol izquierdo, realiza una rotación a la derecha.
- Si hay un desequilibrio en el hijo derecho del subárbol derecho, realiza una rotación a la izquierda.
- Si hay un desequilibrio en el hijo derecho del subárbol izquierdo, realiza una rotación derecha-izquierda.
Un árbol AVL es un árbol de búsqueda binario autoequilibrado. Un árbol AVL es un árbol de búsqueda binario que tiene las siguientes propiedades: -> Los subárboles de cada nodo difieren en altura como máximo en uno. -> Cada subárbol es un árbol AVL.
El árbol AVL verifica la altura de los subárboles izquierdo y derecho y asegura que la diferencia no sea mayor a 1. Esta diferencia se llama Factor de Equilibrio. La altura de un árbol AVL es siempre O (Logn) donde n es el número de nodos del árbol.
Rotaciones de árboles AVL
En el árbol AVL, después de realizar todas las operaciones, como inserción y eliminación, debemos verificar el factor de equilibrio de cada nodo del árbol. Si cada nodo satisface la condición del factor de equilibrio, concluimos la operación; de lo contrario, debemos equilibrarla. Usamos operaciones de rotación para equilibrar el árbol cuando el árbol se desequilibra debido a cualquier operación.
Las operaciones de rotación se utilizan para equilibrar un árbol. Hay cuatro rotaciones y se clasifican en dos tipos:
Rotación única a la izquierda (Rotación LL)
En LL Rotation, cada nodo se mueve una posición a la izquierda desde la posición actual.
Rotación derecha única (rotación RR)
En RR Rotation, cada nodo se mueve una posición a la derecha desde la posición actual.
Rotación izquierda derecha (Rotación LR)
La rotación LR es una combinación de una sola rotación a la izquierda seguida de una única rotación a la derecha. En Rotación LR, primero cada nodo se mueve una posición a la izquierda y luego una posición a la derecha desde la posición actual.
Rotación derecha izquierda (rotación RL)
La rotación RL es una combinación de una sola rotación hacia la derecha seguida de una sola rotación hacia la izquierda. En RL Rotation, primero cada nodo se mueve una posición a la derecha y luego una posición a la izquierda desde la posición actual.
Análisis de tiempo de árboles AVL
El árbol AVL es un árbol de búsqueda binario con la propiedad adicional de que la diferencia entre la altura del subárbol izquierdo y el subárbol derecho de cualquier nodo no puede ser superior a 1.
Promedio del algoritmo Peor caso: Espacio:, O(n)Tiempo:O(n)
Aplicación de árboles AVL
Los árboles AVL son beneficiosos en los casos en que está diseñando una base de datos donde las inserciones y eliminaciones no son tan frecuentes, pero debe buscar con frecuencia los elementos presentes allí.