Definición
Un árbol AVL (Adelson–Velskii y Landis) es un árbol binario de búsqueda que satisface la condición de estar balanceado.
- Por ser un Árbol Binario de Búsqueda respeta la propiedad de orden en todos sus nodos, es decir, todas las claves en su subárbol izquierdo son menores que la clave del nodo y todas las claves en el subárbol derecho son mayores.
- La propiedad de balanceo dice que para cada nodo del árbol, la diferencia de altura entre el subárbol izquierdo y el subárbol derecho es a lo sumo 1
Por ejemplo, la siguiente figura muestra un árbol de altura h y puede verse que sus subárboles tienen la máxima diferencia de altura permitida porque uno de los subárboles tiene altura h-1 y el otro altura h-2. Tenga presente que los subárboles x e y son también árboles AVL.
|
Árbol AVL válido
La diferencia de las alturas de todos los subárboles de los nodos es menor o igual a 1. |
Árbol AVL válido
La diferencia de las alturas de todos los subárboles de los nodos es menor o igual a 1. |
|
No es un Árbol AVL válido
Obsérvese que la diferencia de las alturas de los subárboles del nodo 20 es 1, pero su subárbol derecho no es AVL (porque la diferencia de alturas entre los subárboles de la clave 40 es 2). |
No es un Árbol AVL válido
La diferencia de alturas entre los subárboles de la clave 20 es 2 porque la altura del subárbol izquierdo de 20 es 1 y la altura del subárbol derecho es -1. |
