Ver el código de «Estructuras de datos dinámicas/Soporte teórico»

= Cantidad de nodos en un árbol =
Sea un árbol n-ario completo de altura h.

En el nivel 0 tendrá un solo nodo: la raíz. En el segundo tendrá <math>n</math> nodos, en el tercero <math>n^2</math>; en general, en el nivel h tendrá <math>n^h</math> 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:

<math>C = \sum_{k=0}^h n^k </math>

== Simplificando la expresión ==
<math>C = \sum_{k=0}^h n^k = n^0 + n^1 + n^2 + \cdots + n^{h-1} + n^h </math>

Multiplicando ambos lados por n:

<math>n.C =  n^1 + n^2 + \cdots + n^{h-1} + n^h + n^{h+1}</math>

Restando miembro a miembro:

<math>n.C - C= n^1 + n^2 + \cdots + n^{h-1} + n^h + n^{h+1} - (n^0 + n^1 + n^2 + \cdots + n^{h-1} + n^h) </math>

<math>n.C - C = - n^0 + n^{h+1} </math>

<math>(n - 1).C = n^{h+1} - 1 </math>

<math>C = \cfrac{n^{h+1} - 1}{n - 1} </math>