No estabelecimento de uma estrutura hierárquica, foi defini...

A alternativa correta é a alternativa C: (11(10(9(8))(14(13)(15))).

Vamos entender o porquê:

Para resolver essa questão, é necessário compreender o conceito de árvore binária e como funciona a remoção de nós em uma árvore binária de busca. Uma árvore binária de busca é uma estrutura de dados na qual cada nó tem no máximo dois filhos, e para cada nó, o valor do filho à esquerda é menor que o valor do nó e o valor do filho à direita é maior que o valor do nó.

Quando removemos um nó de uma árvore binária de busca, existem três casos principais a considerar:

1. O nó a ser removido é uma folha (não tem filhos): Simplesmente removemos o nó.

2. O nó a ser removido tem um único filho: Substituímos o nó pelo seu único filho.

3. O nó a ser removido tem dois filhos: Substituímos o nó pelo seu sucessor ou predecessor in-order (o menor nó na subárvore direita ou o maior nó na subárvore esquerda).

No caso da questão apresentada, o nó a ser removido é o 12, que possui dois filhos: 10 e 14. Portanto, devemos substituir o nó 12 pelo seu sucessor in-order, que é o menor nó na subárvore direita, ou seja, o nó 11. Após a remoção e substituição, a nova estrutura da árvore fica:

11 como raiz, com 10 à esquerda e 14 à direita. O nó 10 permanece com seus filhos 9 (com filho 8) e 11 é colocado na posição de 12, enquanto 14 mantém seus filhos 13 e 15.

Dessa forma, a estrutura da árvore resultante é: 11(10(9(8))(14(13)(15))).

Justificativa das alternativas incorretas:

A: (10(9(8))(11(14(13)(15))) - Nesta alternativa, 10 é colocado como raiz, o que não é correto, pois não segue a regra de substituição pelo sucessor ou predecessor in-order.

B: (11(9(8)(10))(14(13)(15))) - Esta estrutura coloca 9 diretamente como filho de 11, o que não preserva a estrutura original da árvore binária de busca.

D: (13(10(9)(11))(14(15))) - Nesta alternativa, 13 é utilizado como nova raiz, mas ele não é o sucessor in-order de 12.

E: (13(11(9)(10))(14(15))) - Aqui novamente, 13 é utilizado incorretamente como raiz, além de não preservar a ordem correta dos nós da subárvore original.

Espero que esta explicação tenha ajudado a esclarecer o processo de remoção de nós em uma árvore binária de busca!

Em primeiro lugar, você teria que saber/lembrar da representação de árvore binária por parênteses aninhados.

Esse link explica essa representação, com isso você consegue desenhar a árvore: http://equipe.nce.ufrj.br/adriano/c/apostila/arvore.htm

Após desenhar a árvore você verá que 12 é o elemento raiz e que ele está pedindo para você remover o elemento raiz.

 

Em segundo lugar, você teria que saber/lembrar do algoritmo para remover a raiz de uma árvore.

Se a raiz não tem um dos filhos, basta que o outro filho assuma o papel de raiz. Senão, faça com que o nó anterior à raiz na ordem e-r-d (esquerda-raiz-direita) assuma o papel de raiz.

Esse link tem um exemplo de remoção da raiz: https://www.ime.usp.br/~pf/algoritmos/aulas/binst.html

 

Aplicando o algoritmo você conclue que o 11 será a nova raiz.

Note que as opções d) e e) você já elimina de cara porque nelas faltam os nós 8 e 12 - ele só removeu o nó 12.

A resposta fica entre a letra b) e c) que tem o nó 11 como raiz - aplicando o algoritmo corretamente você sabe que o 8 continua sendo folha, portanto GABARITO = c)

 

Detalhe: eu não lembraria de nada disso se tivesse feito essa prova e só acertaria chutando entre as letras a, b e c.

 

A substituição seria:
Maior número do lado esquerdo ou menor número do lado direito - Elimina-se a alternativa A)

Como o colega informou abaixo, elimina-se D) e E) por conta do número 8.

 

O erro da B) é modificar o local de 9. Que na aninhagem original é filho de 10.

 

Agora me expliquem porque não foi removido promovido o 13 já que pode ser o maior ou menor, qual critério para escolha? Durante a faculdade sempre fui orientado a promover o imediatamente maior!

nunca ouvi falar dessa regra de pegar o antecessor (salvo algo ligado a balanceamento, o que não é citado na questão), não entendo o erro da A, que gera uma árvore binária correta em termos de suas propriedades assim como a C , mas a escolha da raiz seguiu o raciocínio mencionado nos comentários, o que não entendo porque é obrigatório...

Essa questão possui 2 respostas, porém apenas um gabarito, que é C).

 

As regras são:

 

1) Remoção de um nó folha (sem filhos): 

Basta substituir o nó pai, que apontava para este elemento, para NULL

Ex:          B                              B

           /      \              =       /       \

       A           C                   A        null

 

2) Se possui apenas um filho:

Basta apontar o nó pai que apontava para este elemento para o seu filho

Ex:          B                                        B

           /         \              =             /           \

       A              C                        A                D

                           \

                             D

 

3) Se o nó possui dois filhos. Então temos 2 casos:

3.1)  Se um desses dois filhos não possui filhos, então esse nó para substituir o nó removido

Ex:          B                                     A

           /         \              =                     \

       A              C                                     C

                           \                                      \

                             D                                      D

 

3.2) Caso contrário, substitua este com o elemento cuja chave é imediatamente MAIOR ou MENOR (E aqui está o que a questão quis cobrar)

Ex: com valor imediatamente Menor (isto é, o nó mais a direita da sub-arvore à esquerda)

                  D                                                    C

           /                \              =                   /               \

       B                     G                                B                 G

    /        \              /         \                     /                   /       \

 A           C          F           H                A                   F          H

                        /                                                    /

                      E                                                 E

 

Ex: com valor imediatamente Maior (isto é, o nó mais a esquerda da sub-arvore à direta)

                  D                                                    E

           /                \              =                    /                \

       B                     G                               B                     G

    /        \              /         \                    /      \              /       \

 A           C          F           H               A         C         F            H

                        /                                                   

                      E                               

 

Portanto, para a questão, apenas 2 respostas seriam possíveis:

( 11 (10 (9 (8) )  (14 (13) (15) ) )   -- Regra de substituição pelo imediatamente menor (mais à direita) da sub-arvore à esquerda  (Gabarito!)

 

(13 (10 (9 (8) ) (11) ) (14 (15) ) )  -- Regra de subsituição pelo imediatamente maior (mais à esquerda) da sub-árvore à direta 

 

 

Aqui está um simulador bacana pra conferir a questão:  https://www.cs.usfca.edu/~galles/visualization/BST.html