Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — CESPE / CEBRASPE 2017

Exclusão em Árvore Binária de Busca (ABB)

Gabarito: letra C. A remoção do nó 12 (raiz com dois filhos) em uma ABB é feita substituindo-o pelo seu predecessor inordem (o maior nó da subárvore esquerda, que é 11) e, em seguida, excluindo o nó original 11 (folha). A estrutura resultante é (11(10(9(8))(14(13)(15))), exatamente como na alternativa C.

A questão testa o algoritmo de remoção em uma árvore binária de busca representada pela notação parentética. A árvore original S = (12(10(9(8))(11))(14(13)(15))) corresponde a:

        12
       /  \
      10   14
     /  \   / \
    9   11 13 15
   /
  8

Como a árvore é uma ABB (todos os valores da esquerda são menores que a raiz e os da direita, maiores), a exclusão de um nó com dois filhos segue o procedimento padrão:

1. Localizar o predecessor inordem do nó a remover (maior valor na subárvore esquerda) ou o sucessor inordem (menor valor na subárvore direita).

2. Copiar o valor do predecessor/sucessor para o nó que será removido.

3. Excluir o nó original do predecessor/sucessor (que agora será uma folha ou terá apenas um filho).

No caso, o predecessor de 12 é 11 (vai para a direita a partir de 10). Após copiar 11 para a raiz, remove-se o nó 11 original (folha), o que faz com que a subárvore esquerda de 12 se torne (10(9(8))), pois 10 perde seu filho direito. A subárvore direita (14(13)(15)) permanece inalterada. O resultado é a árvore com raiz 11: filho esquerdo = (10(9(8))) e filho direito = (14(13)(15)).

Alternativa A — ❌ Incorreta

(10(9(8))(11(14(13)(15))) — Coloca 10 como raiz, e o antigo nó 11 passa a ter como filho esquerdo a subárvore direita do 12 (14...). Isso viola a propriedade da ABB (14 > 11, deveria estar à direita) e não corresponde a nenhum algoritmo de remoção.

Alternativa B — ❌ Incorreta

(11(9(8)(10))(14(13)(15))) — Tem raiz 11, mas a subárvore esquerda é (9(8)(10)), quando deveria ser (10(9(8))). Essa configuração só seria obtida se o predecessor usado fosse 10 ou se houvesse uma rotação desnecessária. O procedimento correto mantém 10 como raiz da subárvore esquerda, não 9.

Alternativa C — ✅ Correta ⟵ GABARITO

(11(10(9(8))(14(13)(15))) — Exatamente a árvore resultante da substituição de 12 por 11 e remoção do nó 11 original. A subárvore esquerda (10(9(8))) é a mesma da árvore original, mas com 10 perdendo seu filho direito (11 foi removido). A subárvore direita (14(13)(15)) permanece. Tudo consistente com a ABB.

Alternativa D — ❌ Incorreta

(13(10(9)(11))(14(15))) — Usa o sucessor 13 como nova raiz, mas a subárvore esquerda fica (10(9)(11)) — o nó 8 desaparece, e 15 aparece como filho esquerdo de 14 (erro de ordem). Além disso, a subárvore direita (14(15)) não reflete a original (que tem 13 e 15 como filhos de 14).

Alternativa E — ❌ Incorreta

(13(11(9)(10))(14(15))) — Também usa 13 como raiz, mas a subárvore esquerda (11(9)(10)) perde o 8 e reorganiza 9,10,11 de forma incorreta. A subárvore direita (14(15)) novamente erra a posição de 15 (deveria ser filho direito, não esquerdo).

Gabarito: letra C