Arboles

1

Capítulo 11

Árboles binarios balanceados de búsqueda. AVL.
El alto de un árbol es el largo de la trayectoria más larga de una hoja hasta la raíz. Adel'son-Vel'skii y Landis (1962) definieron árboles AVL en los cuales, para cada nodo, el alto del subárbol derecho difiere del alto del subárbol izquierdo a lo más en uno. El desarrollo del algoritmo muestra la necesidad de un análisisexhaustivo de los diferentes casos que se presentan. Dicho análisis facilita la posterior codificación.

11.1 Análisis de complejidad.
Se define el factor de balance como el alto del subárbol derecho menos el alto del subárbol izquierdo. Entonces en un árbol AVL, todos los nodos cumplen la propiedad de tener valores del factor de balance iguales a: -1, 0, ó +1. Sea nh el mínimo número de nodos en unárbol AVL de altura h dada, que se encuentra en su peor caso de desbalance, si se agrega un nodo, tal que la nueva altura sea (h+1), dejan de ser AVL. Los siguientes diagramas ilustran dichos árboles, denominados de Fibonacci, y los factores de balance de sus nodos, para alturas 0, 1 y 2. Se muestran todos los casos, separados por un eje de simetría; a la derecha del eje se muestran losdesbalanceados por la derecha; y a la izquierda los desbalanceados por la izquierda. Las imágenes en ambos lados del eje se obtienen como imágenes especulares de las del otro lado. Lo que se desea encontrar es la altura máxima h de todos los árboles balanceados de n nodos. Para resolver esto se da una altura h determinada y se intenta construir árboles balanceados AVL con el mínimo número de nodos, éstos sonlos árboles de Fibonacci.

Profesor Leopoldo Silva Bijit

22-02-2008

2 n0 = 1 n1 = 2
0

Estructuras de Datos y Algoritmos

-1 0

1 0

h=1

Figura 11.1 Árboles Fibonacci AVL, con alturas 0, 1. n2 = 4
-1 1 0 0 0 -1 -1 0 0 1 1 0 0 1 -1 0

Figura 11.1.a. Árboles Fibonacci AVL, con altura 2. Se cumple que: n2 = n1 + n0 + 1

Se pueden generar 4 árboles de Fibonacci con alturados. Existen adicionalmente varios árboles AVL de altura dos (los con 5, 6, y 7 nodos) pero se consideran “más balanceados” que los de Fibonacci. Para construir el árbol de Fibonacci de altura h, a la raíz se agrega un subárbol de altura (h-1) y otro de altura (h-2). La Figura 11.2 ilustra un ejemplo, de los 16 posibles, de la generación de un árbol de Fibonacci de altura 3, mediante dos subárbolesde altura 1 y 2. n3 = 7 Se tiene: n3 = n2 + n1 + 1
1 1 0 1 0 1 0

h=3

Figura 11.2 Ejemplo árbol AVL Fibonacci, con altura 3. Se destaca el hecho de que estos árboles son el peor caso: logran máxima altura, con el mínimo número de nodos.

Árboles balanceados AVL n4 = 12 Se tiene n4 = n3 + n2 + 1

3

Como ejemplo de árbol con altura 4, a la raíz se agrega por la derecha un árbol deFibonacci de altura 3, y por la izquierda uno de altura 2, resulta la Figura 11.3.
1

1 0 1 0_ 1 0

1 1 0 1 0

Figura 11.3 Árbol AVL Fibonacci, con altura 4. Mediante inducción puede demostrarse que en general, se tiene la recurrencia:

nh = nh −1 + nh − 2 + 1 con n0 = 1 y n1 = 2
Lo cual implica que un árbol AVL está formado por dos subárboles AVL. La secuencia generada es: 1, 2, 4, 7, 12,20, 33, 54… para h=0, 1, 2…. Empleando el siguiente comando Maple, se puede obtener la solución de la recurrencia:
> n[h]:= rsolve( { n(h) = n(h-1) + n(h-2) + 1, n(0)=1,n(1)=2}, n(h));

El término general de la serie n(h) es:

1 ⎛ − 1 − 1 5 ⎞ ⎛ −2 ⎞ ⎟⎜ ⎜ ⎟ ⎟⎜ ⎜ 5 1− 5 ⎟ ⎠⎝ ⎝ ⎠ + n h := 1− 5

h

1 ⎛ 1 5 − 1 ⎞ ⎛ −2 ⎞ ⎟⎜ ⎜ ⎟ ⎟⎜ ⎜5 1+ 5 ⎟ ⎠⎝ ⎝ ⎠ −1 1+ 5

h

−

2 5

1 5 ⎛ −2 ⎜ ⎜ 1− 5 ⎝1− 5

2 1 ⎞ 5 ⎛ −2 ⎟ ⎜ ⎟ ⎜ 1+ 5 ⎠ + 5 ⎝ 1+ 5

h

⎞ ⎟ ⎟ ⎠

h

Evaluado numéricamente:

n(h) = 1.894427191(1.618033988)h +.1055728091(-.6180339886) h − 1
El segundo término tiende a cero, según muestra la secuencia: > seq( evalf(subs( h =j, .1055728091*(-.6180339886)^h)), j = 0..6);

4
.1055728091 , -.06524758430 , .04032522477 -.009519494246 , .005883370999

Estructuras de...