Qual o número mínimo e máximo de nós em uma árvore AVL de altura
? 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 é
. 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
. 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,
, em uma árvore AVL é:
Isso significa que para uma altura
, o número mínimo de nós é a soma dos números mínimos das alturas
e
, mais 1 (que é o nó da raiz).
Passo 3
Vamos calcular alguns valores para entender melhor:
- Para
: Não há nós, então - Para
: Só a raiz, então - Para
: - Para
:
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
. 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,
, em uma árvore binária (incluindo AVL) de altura
é:
Isso acontece porque em cada nível
, há até
nós, e somando todos os níveis até a altura
resulta em
nós no total.
Resposta
Em uma árvore AVL de altura
, o número mínimo de nós é dado por
, e o número máximo de nós é
.