- Imagine que você tem um problema de calcular a k-ésima estatística de ordem de um conjunto de dados. Faria alguma diferença se você usasse uma BST ou uma AVL para resolver esse problema? Justifique sua resposta.
Passo 1
O enunciado pede para comparar o desempenho de uma árvore de busca binária simples (BST) e de uma árvore AVL ao calcular a k-ésima estatística de ordem, isto é, o k-ésimo menor elemento de um conjunto de dados. O conteúdo envolvido é estruturas de dados balanceadas e não balanceadas, e análise de complexidade em função da altura da árvore.
Passo 2
Para encontrar a k-ésima estatística de ordem em uma árvore binária de busca, a ideia é manter em cada nó um campo adicional :
tamanho
que indica o número de nós na sua subárvore. Então, dado um nó
- Se o tamanho da subárvore esquerda de
for igual a , então é o elemento desejado. - Se for maior que
, repetimos a busca na subárvore esquerda. - Caso contrário, ajustamos
para e buscamos na subárvore direita.
Esse procedimento faz, no máximo, um caminho da raiz até uma folha, executando
operações em cada nó. Logo, o custo fica proporcional à altura da árvore, isto é,
.
Passo 3
Na BST não balanceada, em média
se as chaves forem inseridas em ordem aleatória, mas no pior caso
(por exemplo, se as chaves chegarem já ordenadas). Já numa árvore AVL, sempre vale que
mesmo no pior caso, pois as rotações garantem que a diferença de alturas entre subárvores seja limitada.
Passo 4
Portanto, se você precisa de garantia de tempo de resposta no pior caso, usar uma AVL é melhor pois garante
para cada busca da k-ésima estatística. Se você aceita apenas comportamento médio sob entradas aleatórias, uma BST simples também dá
em média e não há diferença prática significativa no tempo médio, mas corre o risco de degradação para
.
Resposta
Sim. Em uma BST não balanceada o tempo no pior caso pode chegar a
, enquanto na AVL é sempre
. Se você precisar de garantias de desempenho, deve usar AVL; para comportamento médio em dados aleatórios, ambas têm complexidade média
.