DEMOSTRACION

TEMA 6
La recurrencia que describe el costo de la altura es
T(n)=


C

n=null.



T(p) + T(q) + d

n!=null.

Donde n es el número total de nodos, p y q son el número de nodos del hijoizquierdo y el
hijo derecho respectivamente, cumpliendo p+q=n-1 y “c” y “a” son constantes reales
positivas.
Vamos a demostrar que el coste de altura es lineal con respecto al número de nodos.Dado T(n) que denota el tiempo de ALTURA(X) cuando es llamado en la raíz de un
subárbol de tamaño n. T(0) = c para alguna constante positiva c.
Para n>0, suponga que ALTURA es llamado de unnodo X donde el subárbol izquierdo
tiene p nodos y el subárbol derecho tiene q nodos. El tiempo de ALTURA(X) es T(n) = T(p)
+ T(q) + d para alguna constante d que refleja el tiempo deejecutar la función en cada
recursión (por ejemplo imprimir). Y siendo n=p+q+1, entonces q=n-p-1.
Usando sustitución mostraremos que T(n) = O(n).

La ecuación tentativa siempre tiene algunafundamentación.
Teorema: el número de subárboles vacíos
en un árbol binario es uno más que el nro.
de nodos del árbol.
Prueba: por definición, cada nodo en un árbol T binario tiene dos hijos, paraun total de 2n
hijos en árbol de n nodos. Cada nodo, excepto la raíz, tiene un padre, para un total de n-1
nodos con padre. En otras palabras, hay n-1 nodos hijos no vacíos. Ya que el nro.total de
hijos es 2n, el resto n+1 hijos deben estar vacíos. Así podemos decir que el nro. de nodos
vacíos es n+1. Verificar cada nodo vacío lleva un tiempo c y el procesarlo un tiempo d.Así
el tiempo total para n nodos es T(n) = (c+d)n + d.
Recurrencia: T(n) = T (p) + T (q) + d
Supuesto: T(n) = (c+d)n + c

Reemplazamos el supuesto en la recurrencia.
Para n=0 tenemos que(c+d).0 + c = c = T (0)
Para n>0 tenemos
T (n)= T(p)+T(q)+d
T(n)=T(p)+T(n-p-1)+d
T(n)=(c+d)p + c+(c+d)( n-p-1)+c+d
T(n)= cp+dp+c+cn-cp-c+dn-dp-d+c+d
T(n)= cn+dn-d+c+d
T(n)= (c+d)n+c
T(n)=O(n)