Árbol AVL
De Wikipedia, la enciclopedia libre
Árbol AVL es un término usado en computación para referirse a un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó.
Tabla de contenidos |
[editar] Descripción
El árbol AVL toma su nombre de las iniciales de los apellidos de sus inventores, Adelson-Velskii y Landis. Lo dieron a conocer en la publicación de un artículo en 1962: "An algorithm for the organization of information" ("Un algoritmo para la organización de la información").
Los árboles AVL están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere 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 de equilibrio, la inserción y el borrado de los nodos 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 equilibrio, hay que realizar una serie de rotaciones de los nodos.
Los árboles AVL más profundos son los árboles de Fibonacci.
[editar] Definición formal
[editar] Definición del altura de un árbol
Sea T un árbol binario de búsqueda y sean Ti y Td sus subárboles, su altura H(T), es:
- 0 si el árbol T está vacío
- 1 + max(H(Ti),H(Td)) si no lo está
[editar] Definición de árbol AVL
Sea T un árbol binario de búsqueda con Ti y Td siendo sus subárboles izquierdo y derecho respectivamente, tenemos que:
- Si T es vacío, es un árbol AVL
- Si T es un ABB no vacío, es AVL si (si y sólo si):
- Ti y Td son AVL y
- H(Ti) − H(Td) = − 1, 0 ó + 1 (factor de equilibrio)
Por esta definición tenemos que el árbol de la figura de arriba no es AVL, mientras que el de abajo sí lo es. Véase también que se trata de un árbol ordenado, en el cual para cada nodo todos los nodos de su subárbol izquierdo tienen un valor de clave menor y todos los nodos de su subárbol derecho tienen un valor de clave mayor que el suyo, cumpliendo así la propiedad de los ABB.
[editar] 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 árboles binarios de búsqueda (ABB), y además el dato que controla 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.
[editar] 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".
[editar] 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 búsqueda binario 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) .
[editar] Extracción
El problema de la extracción puede resolverse en O(log n) pasos. Una extracción trae consigo una disminución de la altura de la rama donde se extrajo y tendrá como efecto un cambio en el factor de equilibrio del nodo padre de la rama en cuestión, pudiendo necesitarse una rotación.
Esta disminución de la altura y la corrección de los factores de equilibrio con sus posibles rotaciones asociadas pueden propagarse hasta la raíz.
[editar] Búsqueda
Las búsquedas se realizan de la misma manera que en los ABB, pero al estar el árbol equilibrado la complejidad de la búsqueda nunca excederá de O(log n).
