Para resolver o problema do desbalanceamento de árvores binárias de busca, os pesquisadores Adelson-Velskii e Landis, em 1962, criaram um algoritmo que leva as iniciais de seus nomes. Com base na árvore ilustrada a seguir, avalie as afirmações que se seguem.
I - É possível afirmar, com certeza que o desbalanceamento foi causado pela inserção do 63.
II - O nó 63 está desbalanceado.
III - É preciso realizar uma rotação dupla esquerda-direita para balancear essa árvore.
Com base no exposto é possível concluir que estão corretas as afirmações:
Alternativas
Alternativa 1:
I, apenas.
Alternativa 2:
III, apenas.
Alternativa 3:
I e II, apenas.
Alternativa 4:
I e III, apenas.
Alternativa 5:
I e III, apenas. E) I, II e III.
Soluções para a tarefa
Respondido por
1
Resposta:
Marquei a opção 1, apenas
Explicação:
eak18:
eu penso que a opção II também é correta. pois o 63 deveria estar antes do 88, sendo 56, 63 e 88 e não 56, 88 e 63 como exibe figura. e na minha opiniao também a alternativa III seria correta se fosse feita uma rotação dupla "direita-esquerda". Marquei então a alternativa I e II que é a opção 3
Se repararmos a última árvore balanceada da segunda aula ao vivo, por exemplo, ela não está com os nós "balanceados" pela ordem numérica, pois é o seu Fator Balanceamento que irá indicar se está desbalanceado e a sua necessidade de rotação(ões), consequentemente.
*Necessidade de rotação baseada na localização do nó que desbalanceou um determinado nó raiz.
Baseado no que eu compreendi das aulas, a resolução é a seguinte:
I - Verdadeira, pois se retirarmos o nó 63 o Fator balanceamento do nó 56 será igual a -1, não fazendo dele um nó desbalanceado;
II - Falsa, pois as alturas das subárvores esquerda e direita do nó folha 63 são -1, logo:
-1 - (-1) = 0, fazendo com que o seu Fator Balanceamento seja igual a 0;
I - Verdadeira, pois se retirarmos o nó 63 o Fator balanceamento do nó 56 será igual a -1, não fazendo dele um nó desbalanceado;
II - Falsa, pois as alturas das subárvores esquerda e direita do nó folha 63 são -1, logo:
-1 - (-1) = 0, fazendo com que o seu Fator Balanceamento seja igual a 0;
III - Verdadeira, pois como o nó "desbalanceador" 63 foi inserido na subárvore à direita ao lado esquerdo, a rotação dupla será a esquerda-direita, fazendo com que as árvores sejam as seguintes:
a. Árvore original
56
88
63
b. Rotação para a esquerda
88
56
63
a. Árvore original
56
88
63
b. Rotação para a esquerda
88
56
63
c. Rotação para a direita
56
63 88
As subárvores dos nós folhas 63 e 88 têm alturas iguais a -1, fazendo com que cada Fator Balanceamento destes dois nós seja igual a 0.
Os nós folhas têm alturas iguais a zero, logo o Fator Balanceamento do nó raiz 56 é igual a 0;
*Fator Balanceamento = Altura subárvore esquerda - Altura subárvore direita.
56
63 88
As subárvores dos nós folhas 63 e 88 têm alturas iguais a -1, fazendo com que cada Fator Balanceamento destes dois nós seja igual a 0.
Os nós folhas têm alturas iguais a zero, logo o Fator Balanceamento do nó raiz 56 é igual a 0;
*Fator Balanceamento = Altura subárvore esquerda - Altura subárvore direita.
A RESPOSTA DADA FOI CORRIGIDA NA RESPOSTA ACIMA!
Respondido por
0
Resposta:
I , apenas.
Explicação:
A explicação foi posta em um comentário meu abaixo, mas corrigindo, devemos começar a avaliação da inserção de baixo para cima, tendo sido feita na subárvore esquerda do filho à direita, então as rotações serão nos sentidos contrários: direita-esquerda. Segue uma captura de tela das árvores citadas:
Anexos:
ficou confuso... é apenas 1 está correta?
Desculpa. Foi a minha primeira vez nesta plataforma. rsrsrs.
Mas sim. Após rever o assunto percebi que é a alternativa em que diz " I, apenas."
Considere, no "comentário confuso", as explicações sobre as alternativas I e II. Para a alternativa III, a explicação que coloquei na resposta à questão com as novas ordenações da árvore, na qual diz que será necessária a rotação direita-esquerda.
Mas sim. Após rever o assunto percebi que é a alternativa em que diz " I, apenas."
Considere, no "comentário confuso", as explicações sobre as alternativas I e II. Para a alternativa III, a explicação que coloquei na resposta à questão com as novas ordenações da árvore, na qual diz que será necessária a rotação direita-esquerda.
Somente a I está correte. Na III a rotação necessária é a dupla direita-esquerda.
Perguntas interessantes