Ir al contenido

Estructuras de datos dinámicas/Soporte teórico

De Wikilibros, la colección de libros de texto de contenido libre.

Cantidad de nodos en un árbol

[editar]

Sea un árbol n-ario completo de altura h.

En el nivel 0 tendrá un solo nodo: la raíz. En el segundo tendrá n nodos, en el tercero n2; en general, en el nivel h tendrá nh nodos.

Para saber la cantidad total C de nodos que tiene el árbol completo de altura h, tendremos que sumar la cantidad de nodos de cada uno de los niveles:

C=∑k=0hnk

Simplificando la expresión

[editar]

C=∑k=0hnk=n0+n1+n2+⋯+nh−1+nh

Multiplicando ambos lados por n:

n.C=n1+n2+⋯+nh−1+nh+nh+1

Restando miembro a miembro:

n.C−C=n1+n2+⋯+nh−1+nh+nh+1−(n0+n1+n2+⋯+nh−1+nh)

n.C−C=−n0+nh+1

(n−1).C=nh+1−1

C=nh+1−1n−1