Arboles binarios completos

Considere un árbol binario T. cada nodo de T puede tener como mucho dos hijos. De acuerdo con esto, se puede probar que le nivel r de T puede tener como mucho 2^r nodos. El árbol T se dice que es completo si todos sus niveles, excepto posiblemente el ultimo, tiene el máximo numero nodos posibles y si todos los nodos del último nivel están situados. Lo más posible a la izquierda.

Así solo existe un árbol completo Tn con exactamente n nodos (por supuesto, ignoramos los contenidos de los nodos). Los nodos de los árboles completos T26 ha sido intencionalmente etiquetados con los enteros 1, 2,….., 26, de izquierda a derecha y de generación en generación. Con este etiquetado, se pueden determinar fácilmente los hijos o del padre de cada nodo k son, de un árbol completo Tn. Específicamente, los hijos izquierdo y derecho de un nodo k son, respectivamente, 2*k y 2*k +, y el padre de k es el nodo [k/2]. Por ejemplo, los hijos del nodo 9 son los nodos 18 y 19 y su padre es el nodo [9/2]=4. La profundidad d _n  del árbol completo T_n de n nodos viene dada por:

D _n= [log₂ n+1]