Qual é a profundidade de uma árvore binária completa com

Esta pergunta usa a seguinte definição de uma árvore binária completa ^† :

Uma árvore binária $T$ com $N$ Os níveis estarão completos se todos os níveis, exceto possivelmente o último, estiverem completamente cheios e o último nível tiver todos os seus nós no lado esquerdo.

A seguir, um trecho de Algoritmos :

Isto ($\log N$) também é a profundidade de uma árvore binária completa com $N$nós. (Mais precisamente:$⌊\log N⌋$.)

Por que o trecho acima é verdadeiro?

^† Originalmente definido aqui

Considere como uma árvore binária completa de altura $h$ é construído, um vértice no nível da raiz, dois no primeiro nível abaixo da raiz, quatro no segundo nível abaixo e assim por diante, até $h^{th}$nível, que possui pelo menos um vértice, mas no máximo o dobro do nível anterior. Observe que o número de vértices em cada nível é uma potência de dois (excluindo o último, que é um caso especial). Então nós temos:

$$1+\sum_{i=0}^{h-1}2^{i} \leq n \leq \sum_{i=0}^{h}2^{i}$$ Usando a identidade que a soma da primeira $k$ poderes de dois é $2^{k+1}-1$ Nós temos: $$1+2^{h}-1 \leq n \leq 2^{h+1}-1\\ 2^{h} \leq n \leq 2^{h+1}-1$$ e, portanto $$2^{h} \leq n < 2^{h+1}$$

Tomando o logaritmo da base 2:

$$h \leq \log n < h+1$$ Para que possamos concluir $$h = \lfloor\log n\rfloor$$ Como $\log n$ é maior do que $h$, mas menor que o próximo número inteiro $h+1$.