Questão 21 · Informática: Programação e algoritmos

Gabarito: C.

A árvore S tem raiz 12, subárvore esquerda 10(9(8))(11) e subárvore direita 14(13)(15). Ao excluir a raiz (nó com dois filhos), substitui-se seu valor pelo predecessor, o maior valor da subárvore esquerda. Esse valor é 11, filho direito de 10 e folha.

1. Coloca-se 11 na raiz.
2. Remove-se o 11 de sua posição original, e 10 fica só com o filho esquerdo 9(8).
3. Resultado: raiz 11, esquerda 10(9(8)) e direita 14(13)(15), que é a alternativa C (a notação da alternativa vem com um parêntese a menos, mas a estrutura pretendida é essa).

• A: errada. A raiz passa a ser 10, que não é o predecessor nem o sucessor do 12, e a subárvore do 14 é reposicionada abaixo do 11; não corresponde à exclusão.
• B: errada. A raiz 11 está certa, mas a subárvore esquerda foi reorganizada com 9 como raiz e 10 como filho; a exclusão só retira o 11 de seu lugar, sem reestruturar a subárvore esquerda desse modo.
• D: errada. A raiz 13 é o sucessor, mas o resultado perde o nó 8 e muda a subárvore de 10, que deveria permanecer 10(9(8))(11).
• E: errada. Também usa a raiz 13, perde o nó 8 e coloca o 10 como filho direito do 11, o que viola a ordem de uma árvore de busca (10 é menor que 11).

Dica: na exclusão de nó com dois filhos em árvore de busca, troque pelo predecessor (maior da esquerda) ou pelo sucessor (menor da direita) e confira se nenhum nó desapareceu.