Com relação a estruturas de dados e árvores, julgue os próxi...

A alternativa correta é C - certo.

Vamos entender primeiramente o conceito das árvores AVL. Uma árvore AVL é um tipo de árvore binária balanceada em altura, onde a diferença de altura entre as sub-árvores de qualquer nó é, no máximo, igual a 1. Esse balanceamento garante que as operações de inserção, remoção e busca sejam realizadas de forma eficiente, com complexidade O(log n).

Quando inserimos ou removemos um nó em uma árvore AVL, a árvore pode se desbalancear. Para corrigir esse desbalanceamento, utilizamos rotações. Existem quatro tipos de rotações possíveis: rotação simples à direita, rotação simples à esquerda, rotação dupla à direita e rotação dupla à esquerda.

A questão em pauta trata de um cenário específico de desbalanceamento em uma árvore AVL. Quando a diferença de altura entre as sub-árvores de um nó é igual a 2 (ou seja, a árvore está desbalanceada), precisamos verificar o filho do nó desbalanceado. Se a diferença de altura entre as sub-árvores desse filho for igual a -1, realizamos uma rotação dupla.

A rotação dupla mencionada na questão é composta por:

1. Rotação à direita do filho: Altera a estrutura da sub-árvore para que a rotação subsequente corrija o desbalanceamento.
2. Rotação à esquerda do pai: Finaliza o balanceamento, garantindo que a árvore AVL esteja novamente balanceada.

Portanto, a afirmação está correta quando diz que, havendo uma diferença de altura de 2 entre as sub-árvores de um nó e uma diferença de -1 entre as sub-árvores de seu filho, deve-se realizar a rotação dupla (primeiro para a direita e depois para a esquerda) para que a árvore volte a ser balanceada.

Agora, vamos revisar rapidamente as alternativas incorretas:

E - errado: Se a questão afirmasse qualquer outro tipo de rotação ou descrevesse um cenário diferente, a alternativa estaria errada. Por exemplo, se a diferença de altura do filho fosse positiva ou zero, a rotação dupla não seria necessária, e a árvore poderia estar balanceada por outros tipos de rotações.

Em resumo, a afirmação está correta porque descreve adequadamente o processo de rotação dupla necessário para corrigir um desbalanceamento específico em uma árvore AVL. Esse entendimento é essencial para resolver questões sobre árvores balanceadas em concursos públicos.

Concordo que seria uma rotação dupla. Porém, ele não disse qual árvore está desbalanceada (direita ou esquerda). Logo, el enão pode dizer que o filho vai para a direita e o pai para a esquerda.

Rosana, eu acho que é o seguinte:

Primeiro ele afirma que a diferença de altura do nó pai para o nó desbalanceado é 2 ( árvore da direita do nó pai [2] - árvore da esquerda do nó pai [0] = 2 )

Depois ele afirma que a diferença de altura do nó filho do nó desbalanceado é igual a -1 ( árvore da direita do nó filho [0] - árvore da esquerda do nó filho [1] = -1 )

Ficou:

         Pai

Filho

       Desb.

Balanceando faz uma rotação dupla

1° 

        Pai

   Desb

Filho

2º 

           Desb

Filho              Pai

Portanto, filho ficou na direito e o pai ficou na esquerda.

Acho que é isso, bons estudos

Rotação dupla à direita

Deve ser efetuada quando a diferença das alturas h dos filhos de P é igual a 2 e a diferença das alturas h dos filhos de FE é igual a -1. Nesse caso devemos aplicar uma rotação à esquerda no nó FE e, em seguida, uma rotação à direita no nó P.

fonte: https://pt.wikipedia.org/w/index.php?title=%C3%81rvore_AVL§ion=18#Rota.C3.A7.C3.A3o_dupla_.C3.A0_direita

ÁRVORES AVL

Uma árvore binária T é denominada AVL quando todos os seus nós estão regulados.

O nó de uma árvore binária é considerado regulado quando as alturas de suas subárvores esquerda e direita diferem em até uma
unidade. Caso contrário, consideramos que o nó esta desregulado.

Um nó regulado tem fator de balanceamento igual a: -1, 0 ou 1.

Fonte: Provas de TI

CERTO

A princípio dei a questão como errada, porém há um peguinha nela.

Notem que o CESPE usa a fórmula Altura da Sub-Árvore à Direita - Altura da Sub-Àrvore à Esquerda, sendo que o usual é usarmos a fórmula contrário ASAE - ASAD. As duas fórmulas produzem o mesmo resultado no final, uma árvore balanceada, então uma não é mais certa do que a outra.

Baseado nisso podemos dizer que o Lado Direito da Árvore está desbalanceado e partir daí usamos o raciocínio do SS Concurseiro, mudando a apenas do formato do Joelho:

10 10

7 -> 13

9 12

A questão descreve a situação apresentada na segunda árvore, logo a resposta está correta.