Por que a altura mínima de um

Na minha aula de Java, estamos aprendendo sobre a complexidade de diferentes tipos de coleções.

Em breve estaremos discutindo árvores binárias, sobre as quais tenho lido. O livro afirma que a altura mínima de uma árvore binária é , mas não oferece mais explicações.$\log_2(n+1) - 1$

Alguém pode explicar o porquê?

Uma árvore binária possui 1 ou 2 filhos nos nós não foliares e 0 nós nos nós foliares. Haja nós em uma árvore e temos que organizá-los de tal maneira que eles ainda formam uma árvore binária válido.$n$

Sem provar, estou afirmando que, para maximizar a altura, determinados nós devem ser organizados linearmente, ou seja, cada nó não-folha deve ter apenas um filho:

                              O 1
                              |
                              O 2
                              |
                              O 3
                              |
                              O 4
                              |
                              O 5
                              |
                              O 6
                              |
                              O 7
                              |
                              O 8

Aqui, a fórmula para calcular a relação da altura em termos de número de nós é direta. Se é a altura da árvore, então h = n - 1 .$h$$h = n-1$

$n$

                              O
                              |1
                              |
                       O------+-----O
                       |2           |3
                       |            |
                   O---+---O    O---+----O
                   |4      |5    6        7
                   |       |
               O---+--O    O
                8      9    10

$n = 2^m - 1$

$$2^0 + 2^1 + 2^2 + ... + 2^{m-1} = 2^m - 1$$

$i$$2^i$

$i$$0$$m$$2^{i-1}$$2^m - 1$$2^m - 1$$h(2^m-1) = m-1$$h(n) =$$n$

$h(2^m) = m$$2^m-1$$(2^m-1)+1 = 2^m$$m$$m-1$$m$

$$h(2^m) = m,$$ $$h(2^{m+1}) = m+1$$ $$h(2^{m+1} -1) = m$$

$\forall n \in \mathbb{Z}, 2^m \leq n < 2^{m+1}$

$$m \leq h(n) < m+1$$

$$m \leq \log_2(n) < m+1$$ $$m = \lfloor \log_2(n) \rfloor$$

$\forall n, n \in [2^m, 2^{m+1})$

$$h(n) = m = \lfloor \log_2(n) \rfloor$$

$\forall n \in \mathbb{Z}$

$\log_2(n+1)-1$$n$$\log_2(n)$$n$

$n$

$4$$1+1\cdot2+1\cdot2\cdot2+1\cdot2\cdot2\cdot2$$3$

$$\text{nodes}=1+2+2^{2}+2^{3}+...+2^{\text{depth}}=\sum_{k=0}^{\text{depth}} 2^{k}=\frac{1-2^{\text{depth}+1}}{1-2}.$$

$$\text{nodes}=2^{\text{depth}+1}-1,$$ $$\begin{eqnarray} \text{nodes}+1&=&2^{\text{depth}+1}\\ \log_{2}(\text{nodes}+1)&=&\log_{2}(2^{\text{depth}+1})=\text{depth}+1\\ \log_{2}(\text{nodes}+1)-1&=&\text{depth}. \end{eqnarray}$$

Para manter a altura mínima, é fácil ver que precisamos preencher todos os níveis, exceto possivelmente o último. Por quê? caso contrário, poderíamos simplesmente mover os nós do último nível para os slots vazios nos níveis superiores.

Agora, imagine que eu tenho um número não especificado de beans e lhe dou um bean de cada vez e peço que você construa uma árvore binária com a altura mínima possível. Eu posso ficar sem feijão no momento em que você preencheu o último nível completamente ou pelo menos tem um feijão no último nível. Digamos que você tenha a altura da sua árvore h neste momento.

$$2^{0}+2^{1}+2^{2}+2^{3}+\dots+2^{h}=2^{h+1}-1 \leq n\,.$$ $$h = \lg(n+1)-1\,.$$