1. 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ó v:
  • Se o tamanho da subárvore esquerda de v for igual a k-1, então v é o elemento desejado.
  • Se for maior que k-1, repetimos a busca na subárvore esquerda.
  • Caso contrário, ajustamos k para k - (\text{tamanho da esquerda de }v) - 1 e buscamos na subárvore direita.
Esse procedimento faz, no máximo, um caminho da raiz até uma folha, executando O(1) operações em cada nó. Logo, o custo fica proporcional à altura da árvore, isto é, O(h).

Passo 3

Na BST não balanceada, em média h = \Theta(\log n) se as chaves forem inseridas em ordem aleatória, mas no pior caso h = \Theta(n) (por exemplo, se as chaves chegarem já ordenadas). Já numa árvore AVL, sempre vale que h = O(\log n) 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 O(\log n) 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á O(\log n) em média e não há diferença prática significativa no tempo médio, mas corre o risco de degradação para O(n).

Resposta

Sim. Em uma BST não balanceada o tempo no pior caso pode chegar a O(n), enquanto na AVL é sempre O(\log n). Se você precisar de garantias de desempenho, deve usar AVL; para comportamento médio em dados aleatórios, ambas têm complexidade média O(\log n).

Exercícios relacionados