Altura de un árbol binario completo

Question

Un árbol binario completo parece ser un árbol binario en el que cada nodo es una hoja o tiene 2 hijos. He intentado demostrar que su altura es O(logn) sin éxito. Aquí está mi trabajo hasta ahora:

Estoy considerando el peor caso de un árbol binario completo en el que cada nodo de la derecha tiene un subárbol, y cada nodo de la izquierda es una hoja. En este caso:
$N = 2x - 1$
$H = x - 1$
No voy a ninguna parte tratando de demostrar que $H = O(log(N))$

Además, sabemos que las hojas l están limitadas por $h+1 <l<2^h$ .
Los nodos internos están limitados por $h<i<2^{h-1}$ .
Todo esto demuestra que el número de nodos $n=i+e$ es $<= 2^{h+1} - 1$ es decir $log(n) <= h$ . Pero esto no me lleva a ninguna parte para demostrar que $H = O(log(n))$

Answer 1

Dado h... altura del árbol, N(h)... cuenta de nodos para la altura del árbol h. Si h = 1: N(h) = 1; h = 2: N(h) = N(1) * 2 = 1 * 2; h = 3: N(h) = N(2) * 2 = N(1) * 2 * 2 = 1 * 2 * 2 * 2; ... h = n: N(n) = N(n-1) * 2 = ... = 1 * 2 * 2 * 2 ... = 1 * 2^n = 2^n Cada nodo tiene dos hijos.

Así, el recuento de nodos si la altura del árbol es n es N(n) = 2^n. Y si el número de nodos del árbol binario completo es N, entonces la altura del árbol n es proporcional a log_2(N) o n = C(log(N)).