Before you keep reading...

Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.

Support Runestone Academy Today

Before you keep reading...

Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.

Support Runestone Academy Today

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{array}{r}{F}_0=0\\ F_1=1\\ F_i=F_{i-1}+F_{i-2}\text{ para todo }i\ge 2\end{array}$$

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 $\mathrm{\Phi }$ que se define como $\mathrm{\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={\mathrm{\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{{\mathrm{\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{array}{r}\log N_h+1=(H+2)\log \mathrm{\Phi }-\frac{1}{2}\log 5\\ h=\frac{\log N_h+1-2\log \mathrm{\Phi }+\frac{1}{2}\log 5}{\log \mathrm{\Phi }}\\ h=1.44\log N_h\end{array}$$

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 1 of 1 activities on this page