Analizar Arboles Binarios

Analizar Arboles Binarios

de Guillermo Daniel Toyos Marfurt -
Número de respuestas: 2

Buenas, no entiendo muy bien como escribir la formula de recursion para arboles binarios. Princiaplemente en como escribir la formula en funcion del nro de nodos y no la altura del arbol.

Por ejemplo para calcular el peor tiempo de ejecuccion para contar los nodos de un arbol binario:

T(h)=

c_1, si h=0.

2T(h-1)+c_2, else.

siendo h, la altura.

Usando el metodo de expansion de recurrencias llegamos a que el algoritmo es 2^h.

2^k\times T(n-k)+2^{k-1}\times c_2 \rightarrow O(2^h)

Ahora bien, como el numero de nodos de un arbol (n) es n= 2^h; haciendo cambio de variable llegamos a que el algoritmo es O(n). Sin embargo la relacion n=2^h no tiene por que cumplirse. Cual es el metodo correcto usando directamente n y no h?

De antemano, gracias.
En respuesta a Guillermo Daniel Toyos Marfurt

Re: Analizar Arboles Binarios

de Carlos Luna -

Hola.

Usando en estos casos n como la cantidad de nodos del árbol binario, las recurrencias cuando el árbol no es vacío vincularían a T(i) y T(n-1-i), donde i es un valor entre 0 y n-1 (considerando que un subárbol tiene i nodos y el otro n-1-i).

Se puede demostrar luego por inducción que T(n) <= cte . n, para alguna contante n0 tal que n >= n0.

En estos casos también se podría justificar que para analizar el peor caso uno puede considerar directamente el caso cuando i=0 (árbol degenerado). Esto es, quedaría esencialmente T(n-1) en la recurrencia, que al igual que el factorial visto en el teórico, nos da O(n).

Si quedan más dudas, sugiero discutirlo en las clases de práctico de esta semana.

Saludos, Carlos