6.17. Desempeño de un árbol AVL

Antes de continuar, analicemos el resultado de aplicar este nuevo requisito de factor de equilibrio. Nuestra afirmación es que al garantizar que un árbol tenga siempre un factor de equilibrio de -1, 0 ó 1, podremos obtener un mejor desempeño de las operaciones clave. Comencemos por pensar en cómo esta condición de equilibrio cambia al árbol del peor de los casos. Hay dos posibilidades a considerar, un árbol pesado a la izquierda y un árbol pesado a la derecha. Si consideramos árboles de alturas 0, 1, 2 y 3, la Figura 2 ilustra el árbol más desequilibrado y pesado a la izquierda posible bajo las nuevas reglas.

Figura 2: Árboles AVL pesados a la izquierda del peor caso

Figura 2: Árboles AVL pesados a la izquierda del peor caso

Observando el número total de nodos en el árbol vemos que para un árbol de altura 0 hay 1 nodo, para un árbol de altura 1 hay \(1 + 1 = 2\) nodos, para un árbol de altura 2 hay \(1 + 1 + 2 = 4\) y para un árbol de altura 3 hay \(1 + 2 + 4 = 7\) nodos. Más en general, el patrón que vemos para el número de nodos en un árbol de altura h (\(N_h\)) es:

\[N_h = 1 + N_{h-1} + N_{h-2}\]

Esta recurrencia quizás le parezca familiar porque es muy similar a la secuencia de Fibonacci. Podemos utilizar este hecho para derivar una fórmula para la altura de un árbol AVL dado el número de nodos en el árbol. Recordemos que, para la secuencia de Fibonacci, el \(i_{ésimo}\) número de Fibonacci está dado por:

\[\begin{split}F_0 = 0 \\ F_1 = 1 \\ F_i = F_{i-1} + F_{i-2} \text{ para todo } i \ge 2\end{split}\]

Un resultado matemático importante es que a medida que los números de la secuencia de Fibonacci se hacen más y más grandes, la relación de \(F_i / F_{i-1}\) se aproxima cada vez más a la proporción áurea \(\Phi\) que se define como \(\Phi = \frac{1 + \sqrt {5}}{2}\). Usted puede consultar un texto de matemáticas si desea examinar una derivación de la ecuación anterior. Simplemente utilizaremos esta ecuación para aproximar \(F_i\) como \(F_i = \Phi^i /\sqrt{5}\). Si hacemos uso de esta aproximación podemos reescribir la ecuación para \(N_h\) como:

\[N_h = F_{h+2} - 1, h \ge 1\]

Al reemplazar la referencia de Fibonacci por su aproximación de la proporción áurea obtenemos:

\[N_h = \frac{\Phi^{h+2}}{\sqrt{5}} - 1\]

Si reordenamos los términos y tomamos el logaritmo en base 2 de ambos lados y luego despejamos \(h\) obtenemos la siguiente derivación:

\[\begin{split}\log{N_h+1} = (H+2)\log{\Phi} - \frac{1}{2} \log{5} \\ h = \frac{\log{N_h+1} - 2 \log{\Phi} + \frac{1}{2} \log{5}}{\log{\Phi}} \\ h = 1.44 \log{N_h}\end{split}\]

Esta derivación nos muestra que en cualquier momento la altura de nuestro árbol AVL es igual a una constante (1.44) veces el logaritmo del número de nodos en el árbol. Ésta es una gran noticia para buscar en nuestro árbol AVL porque limita la búsqueda a \(O(\log{N})\).

You have attempted of activities on this page