Árbol AVL

Un árbol AVL es 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ó.

Descripción

Un ejemplo de árbol binario no equilibrado (no es AVL)
Un ejemplo de árbol binario equilibrado (sí es AVL)

El árbol AVL toma su nombre de las iniciales de los apellidos de sus inventores, Georgii Adelson-Velskii y Yevgeniy 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 o viceversa. 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.

Other Languages
العربية: شجرة AVL
български: АВЛ Дърво
bosanski: AVL stabla
čeština: AVL-strom
dansk: AVL-træ
Deutsch: AVL-Baum
English: AVL tree
suomi: AVL-puu
français: Arbre AVL
עברית: עץ AVL
hrvatski: AVL stablo
magyar: AVL-fa
Bahasa Indonesia: Pohon AVL
italiano: Albero AVL
日本語: AVL木
한국어: AVL 트리
lietuvių: AVL medis
polski: Drzewo AVL
português: Árvore AVL
русский: АВЛ-дерево
slovenčina: AVL strom
slovenščina: AVL-drevo
српски / srpski: АВЛ-стабло
svenska: AVL-träd
українська: АВЛ-дерево
Tiếng Việt: Cây AVL
中文: AVL树