Qual o número mínimo e máximo de nós em uma árvore AVL de altura h ? Justifique sua resposta.

Passo 1

Beleza! A questão está pedindo para a gente descobrir qual é o número mínimo e máximo de nós que uma árvore AVL pode ter quando sua altura é h. Uma árvore AVL é uma árvore binária balanceada, o que significa que ela mantém seus ramos equilibrados para garantir que as operações sejam rápidas. Para resolver isso, vamos precisar entender como o balanceamento influencia o número de nós e usar algumas fórmulas matemáticas.

Passo 2

Vamos começar encontrando o número mínimo de nós em uma árvore AVL de altura h. Em uma árvore AVL, a diferença de altura entre as subárvores direita e esquerda de qualquer nó não pode ser maior que 1. Para ter o mínimo de nós, queremos que a árvore seja o mais “enrugada” possível, mantendo esse equilíbrio.
A relação de recorrência para o número mínimo de nós, N(h), em uma árvore AVL é:
N(h) = N(h-1) + N(h-2) + 1
Isso significa que para uma altura h, o número mínimo de nós é a soma dos números mínimos das alturas h-1 e h-2, mais 1 (que é o nó da raiz).

Passo 3

Vamos calcular alguns valores para entender melhor:
  • Para h = 0: Não há nós, então N(0) = 0
  • Para h = 1: Só a raiz, então N(1) = 1
  • Para h = 2: N(2) = N(1) + N(0) + 1 = 1 + 0 + 1 = 2
  • Para h = 3: N(3) = N(2) + N(1) + 1 = 2 + 1 + 1 = 4
Isso mostra que o número mínimo de nós cresce de forma semelhante à sequência de Fibonacci.

Passo 4

Agora, vamos descobrir o número máximo de nós em uma árvore AVL de altura h. Como a árvore AVL é balanceada, o número máximo de nós ocorre quando ela está completamente cheia, ou seja, todos os níveis estão totalmente preenchidos.
A fórmula para o número máximo de nós, M(h), em uma árvore binária (incluindo AVL) de altura h é:
M(h) = 2^h+1 - 1
Isso acontece porque em cada nível i, há até 2^i nós, e somando todos os níveis até a altura h resulta em 2^h+1 - 1 nós no total.

Resposta

Em uma árvore AVL de altura h, o número mínimo de nós é dado por N(h) = N(h-1) + N(h-2) + 1, e o número máximo de nós é 2^h+1 - 1.

Exercícios relacionados