Matéria: Informática
Autor: androceu
Perguntado 7 anos atrás

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.

Respostas

respondido por: radioativojogo

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

vicregina1: 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.

vicregina1: *Necessidade de rotação baseada na localização do nó que desbalanceou um determinado nó raiz.

vicregina1: 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;

vicregina1: 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

vicregina1: 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.

vicregina1: A RESPOSTA DADA FOI CORRIGIDA NA RESPOSTA ACIMA!

respondido por: vicregina1

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:

eak18: ficou confuso... é apenas 1 está correta?

vicregina1: 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.

NhoQUin: Somente a I está correte. Na III a rotação necessária é a dupla direita-esquerda.

Perguntas similares

Matemática

5 anos atrás

Uma equipe de basquete disputou 40 partidas e ganhou 28.Qual a razão do número de partidas ganhas para o número de partidas disputadas? A)7/10 B)10/7 C)40/28 D)40/20 E)12/40

Inglês

5 anos atrás

Assinale a alternativa em que os ADVERBS estejam na ordem correta, quanto a intensidade, do mais para o menos frequente: always, never, usually always, usually, never usually, never, always never, usually, always

Matemática

5 anos atrás

calcule o valor das expressões 15+(-1)1-2

Informática