2

Pessoal como fica a árvore após a remocão do número 40?

No meu entendimento, no lugar do 40 seria o número 41, direita 44 e esquerda 30. E a direita do 44 o número 49, to certo?

inserir a descrição da imagem aqui

3 Respostas 3

1

Bom, você tem que definir qual metodologia adotar. Você pode escolher o nó a esquerda, 30, como o novo nó que ficará no lugar do 40 e então neste caso você terá que buscar o nó mais a direita do nó 30, para alocar o nó que estava a direita do 40, o 44. Ou você também pode escolher o 44 como o nó que ficará no lugar do 40, e neste caso você terá que procurar o nó mais a esquerda do 44 para alocar o que estava a esquerda do 40, no caso o 30. De qualquer forma isso depende da sua metodologia, e desta forma não irá desbalancear a sua árvore. Não seria viável você tentar reorganiza-la de modo a colocar o 41 no lugar do nó removido, isso porque seria trabalhoso demais garantir que a árvore não seria desbalanceada.

Slide - Professor Marcos Caetano - UnB Slide do professor Marcos Caetano - UnB.

Como poder ver, a sua árvore continuará balanceada inserir a descrição da imagem aqui

2
  • Então baseado no que ele pediu no enunciado: "Para que se continue tendo a configuração de uma árvore binária de busca, após a remoção dos nós mostrados, abaixo, qual será a nova configuração das árvores? Redesenhe." Eu poderia colocar no lugar do 40, o número 41 igual eu fiz? Ele poderia considerar?
    – André
    Commented 15/12/2017 às 11:04
  • Não poderia, você tem que considerar que não sabe quais os valores de cada nó, até porque ela não segue uma ordem numérica, e você somente sabe que menor fica à esquerda e maior à direita. Então, você somente pode definir qual nó filho ficará no lugar, se o da esquerda ou da direita. A árvore continuará sendo uma árvore binária de busca em qualquer uma das duas opções. Commented 15/12/2017 às 20:55
1

Pelo que posso perceber esta árvore trata-se de uma árvore binária de busca (ABB).

Sempre que um nó for removido, o que substituirá sua posição na árvore deve manter a árvore como sendo ainda uma árvore binária de busca. Ou seja, números menores à esquerda e números maiores à direita. Para isso deve-se pegar o filho da subárvore à esquerda que está mais à direita e colocar no lugar do nó que será removido.

inserir a descrição da imagem aqui

No caso, como não há subárvore à esquerda, mas sim apenas um nó, é esse nó à esquerda que irá ser colocado no lugar. Ou seja, o 30 substituirá a posição do 40 na ABB.

Isso ocorre assim pelo fato de que o maior elemento na subárvore à esquerda é maior que o menor elemento da subárvore à direita.

Você pode entender mais sobre remoção em Árvore Binária de Busca nesse vídeo. Foi da lá que tirei essa imagem.

1
  • Então, mas tenho uma dúvida, ele pedi isso no exercício, na prova: "Para que se continue tendo a configuração de uma árvore binária de busca, após a remoção dos nós mostrados, abaixo, qual será a nova configuração das árvores? Redesenhe."
    – André
    Commented 15/12/2017 às 11:00
0

Apenas remova o desejado e pegue ou maior à esquerda ou o menor à direita e ponha em seu lugar.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .