Árbol AVL
Keywords: Árbol AVL, 1962, Complejidad computacional, Cota superior asintótica, Wikipedia, Árbol binario, Árbol de búsqueda binario auto-balanceable
En computación, el Árbol AVL es un tipo especial de árbol binario ideado por Adelson-Velskii y Landin. Fue el primer árbol de búsqueda binario auto-balanceable que se inventó.
Los árboles AVL están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiera en más de una unidad de la altura de la rama derecha. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n). El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles.
Para conseguir esta propiedad, la inserción y el borrado de los nodos de un árbol AVL se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibirio, hay que realizar una serie de rotaciones de los nodos.
El árbol AVL se denomina así en honor a sus inventores, G.M. Adelson-Velsky y E.M. Landis, que lo publicaron en su artículo de 1962 "An algorithm for the organization of information" (Un algoritmo para la organización de la información).
Los árboles AVL más profundos son los árboles de Fibonacci.
| Tabla de contenidos |
Factor de equilibrio
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.
Operaciones
Las operaciones básicas de un árbol AVL implican generalmente el realizar los mismos algoritmos que serían realizados en un árbol binario de búsqueda desequilibrado, pero precedido o seguido por una o más de las llamadas "rotaciones AVL".
Inserción
La inserción en un árbol de AVL puede ser realizada insertando el valor dado en el árbol como si fuera un árbol de busqueda binaria desequilibrado, y después retrocediendo hacia la raíz, rotando sobre cualquier nodo que pueda haberse desequilibrado durante la inserción. Dado que como mucho un nodo es rotado 1,5 veces log n en la vuelta hacia la raíz, y cada rotación AVL tarda el mismo tiempo, el proceso de inserción tarda un tiempo total de O(log n) .
Borrado
Búsqueda
Enlaces externos
| WikiLetra | Este artículo es, por ahora, sólo un esbozo. Ampliándolo ayudarás a mejorar Wikipedia. Puedes encontrar fuentes en las wikipedias en otras lenguas. Si lo amplias hasta el punto de que este cartel no sea necesario por favor, elimínalo. |