-
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
-
Olá meus queridos colegas de auditório!
Infelizmente o CESPE deu essa assertiva como CORRETA... Vi outros guerreiros de auditório questionando essa afirmativa em alguns sites e realmente o final dela está COMPLETAMENTE EQUIVOCADO, vejam:
Em uma árvore AVL (Adelson-Velsky e Landis), caso a diferença de altura entre as sub-árvores de um nó seja igual a 2 e a diferença de altura entre o nó filho do nó desbalanceado seja igual a -1, deve-se realizar uma rotação dupla (ATÉ AQUI CORRETO) com o filho para a direita e o pai para a esquerda (ERRADO... trocou as bolas) a fim de que a árvore volte a ser balanceada.
O CESPE propôs isso (a forma do "JOELHO"): --> Pai só com nó esquerdo, Filho só com nó direito
PAI (+2)
FILHO (-1)
NÓ DIREITO FILHO (0)
Lembrando que em uma árvore AVL, para qualquer nó, as alturas de suas duas subárvores, esquerda e direita, diferem em módulo de até uma unidade. Então no caso proposto pelo CESPE realmente precisamos utilizar rotações para voltar ao equilíbrio (não pode ter um nó +2).
Nesse caso realmente aplicamos uma ROTAÇÃO DUPLA (forma de "joelho", sinais diferentes +2, -1).
(PRA QUEM NÃO ESTÁ ENTENDENDO DIREITO, OU QUISER APRIMORAR ESSES CONCEITOS, ESSE VÍDEO É MUITO BOM: https://www.youtube.com/watch?v=JAeQuNsKQWk)
Bom agora vamos para as rotações utilizadas para o equilíbrio e percebam o ERRO GROSSEIRO do CESPE:
1) Primeira Rotação --> FILHO para ESQUERDA
PAI (+2)
NÓ DIREITO FILHO (+1)
FILHO (0)
Rodando o filho pela esquerda voltamos a ter uma reta (sinais iguais), porém ainda em desiquilíbrio!
2) Segunda Rotação --> PAI para DIREITA
NÓ DIREITO FILHO (0)
FILHO (0) PAI (0)
Pronto, alcançamos o equilíbrio na AVL (todos aqui estão com fator de balanceamento 0!).
CONCLUINDO: Ao contrário do que o CESPE escreveu, na rotação, o FILHO vai para ESQUERDA, depois o PAI vai para DIREITA.
Não sou nenhum EINSTEIN em Estrutura de Dados (tanto que minha especialidade é vender carnês do baú), e apesar de gostar da banca, infelizmente percebo nas diversas questões do tema que os examinadores do CESPE são muito fracos em estrutura de dados...
Não podemos deixar gabaritos absurdos como esse passar, nas próximas vamos todos "fazer chover" de recursos!
Continuem persistindo, forte abraço, fiquem com Deus, e não se esqueçam de comprar a Nova TeleSena de Natal, suas chances de ganhar 1 milhão dobraram
-
Á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.
-
A questão está correta, a CESPE não inverteu a fórmula de cálculo de balanceamento, a fórmula original segundo o autor é: FB(n) = H(D) - A(E), ou seja, é altura da sub árvore DA DIREITA menos altura da sub árvore DA ESQUERDA, e não ao contrário, NÃO EXISTE ISSO DE USUAL, EXISTE O QUE É REALMENTE DEFINIDO PELO AUTOR QUE CRIOU O ALGORITMO. Dessa forma, considerando os números dos desbalanceamento que a questão informou isso vai formar uma sub-árvore da direita desbalanceada (número 2). Logo é realizada uma rotação a direita e esquerda para balancear.
-
Força Guerreiro!!!!!!