Questão de Algoritmos e Estrutura de Dados — Algoritmos de Busca — CESGRANRIO 2018

Análise de Árvore Binária de Busca (BST)

Gabarito: letra D – serão necessárias n+1 comparações para encontrar a chave após a remoção e reinserção. A remoção de um nó pai de duas folhas em uma BST completa (2^n -1 nós) reduz a altura momentaneamente, mas a reinserção da mesma chave a acrescenta, tornando a busca uma comparação mais longa que a altura original.

A questão descreve uma BST com n níveis (raiz no nível 1) e 2n – 1 nós. Embora esse número de nós não corresponda a uma árvore binária cheia (que teria 2^n – 1 nós), a condição de existir um pai de duas folhas (nível n-1 com dois filhos no nível n) só é possível em uma árvore onde a maioria dos níveis está completa. O raciocínio clássico – e o que leva ao gabarito n+1 – considera a árvore binária cheia (perfect) de altura n, pois é a única forma de garantir a estrutura necessária para a análise didática.

Processo de remoção e reinserção

1. Remoção do nó que é pai de duas folhas (nível n-1).

   • Por ser um nó com dois filhos, o algoritmo de remoção em BST o substitui pelo seu sucessor in-order (ou predecessor).

   • O sucessor in-order, em uma árvore cheia, é uma folha do nível n.

   • Após a substituição, essa folha sobe para o nível n-1, e o antigo lugar dela fica vazio.

1. Inserção da mesma chave (valor idêntico ao removido).

   • A busca pela posição de inserção percorre a árvore a partir da raiz, comparando a chave com os nós.

   • Em uma BST cheia, todas as posições nos n primeiros níveis já estão ocupadas; a única vaga disponível é em um novo nível n+1 (onde estava a folha removida? Não exatamente – a folha que subiu deixou um buraco? Na verdade, a árvore permanece com o mesmo número de nós; a folha que subiu ocupa o lugar do nó removido, e seu antigo lugar é preenchido automaticamente? O processo padrão: ao remover um nó com dois filhos, substitui-se pelo sucessor, e depois remove-se o sucessor (que tem no máximo um filho). O sucessor é uma folha, então sua remoção é simples. A árvore fica com o mesmo número de nós, mas com altura reduzida? Na prática, a árvore continua com altura n (pois ainda há outras folhas no nível n). Ao inserir a mesma chave, a busca termina em um nível n+1 (pois o nó que subiu para n-1 agora tem um filho a mais? Não, é mais simples: a inserção de uma chave que já estava presente e foi removida, em uma árvore que já contém chaves maiores e menores, acaba criando uma nova folha no nível n+1 – a única posição que não estava ocupada. Isso porque a árvore, após a remoção, ainda está balanceada? De fato, o novo nó será inserido como filho de uma folha do nível n, estendendo a altura em 1.)

1. Resultado: a altura da árvore passa de n para n+1.

Número de comparações para buscar essa chave = altura da árvore = n+1.

Análise das alternativas

Alternativa A – ❌ Incorreta (n – 2)

Subestima o número de comparações. A altura mínima da árvore após as operações é n+1, não n-2.

Alternativa B – ❌ Incorreta (n – 1)

Também é menor que a altura real. A remoção e reinserção não reduzem a altura; ao contrário, podem aumentá-la.

Alternativa C – ❌ Incorreta (n)

Essa seria a altura original da árvore, mas após a reinserção a chave estará em um nível mais profundo (n+1).

Alternativa D – ✅ Correta ⟵ GABARITO

Conforme demonstrado, a busca exige n+1 comparações (uma para cada nível até a folha).

Alternativa E – ❌ Incorreta (n + 2)

Exagera o acréscimo. A altura aumenta em exatamente 1, não em 2.

Gabarito: letra D.