-
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.
-
https://www.youtube.com/watch?v=XZ0MEDhb4oE
O vídeo explica perfeitamente como resolver. O início é a parte de inserção (até 6'14'') e o restante para exclusão.
12
10 14
9 11 13 15
8
-
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
-
Leonardo Mateus, parabéns pela explicação!
Gostei do simulador, simples e fácil de usar
-
Força Guerreiro!!!!!!