Propriedades de árvores binárias

---

Uma árvore binária não vazia com altura $h$ tem:

• Mínimo de $h+1$ nós (quando todos os nós estão distribuídos ao longo de uma única “linha”, ou seja, cada nó tem no máximo um filho).

• Máximo de $2^{h+1}-1$ nós (quando a árvore é completa, ou seja, todos os níveis estão preenchidos com o número máximo de nós).

A altura de uma árvore com $n$ elementos ($n>0$) é:

• No mínimo $\lfloor {\log }_{2}n\rfloor$
• No máximo $n-1$

Dessa forma, a altura da árvore sempre estará dentro do seguinte intervalo:

$$\lfloor {\log }_{2}n\rfloor \le h\le n-1$$

Exemplo para $h=2$

1. Mínimo de nós:

Quando a árvore tem altura $h=2$, a quantidade mínima de nós é calculada pela fórmula:

$$\text{Mıˊnimo}=h+1$$

Substituindo $h=2$:

$$\text{Mıˊnimo}=2+1=3\text{ noˊs}$$

Isso significa que a árvore terá no mínimo 3 nós, caso ela seja um caminho linear com os nós ao longo de uma única “linha”.

2. Máximo de nós:

A quantidade máxima de nós em uma árvore binária completa é dada pela fórmula:

$$\text{Maˊximo}=2^{h+1}-1$$

Substituindo $h=2$:

$$\text{Maˊximo}=2^{2+1}-1=2^3-1=8-1=7\text{ noˊs}$$

Ou seja, se a árvore for completa, ela terá no máximo 7 nós.

Referências

---

Aula 2 - TAD Árvores Binárias e BST