A imagem abaixo apresenta uma árvore AVL durante o processo de inserção da chave G.O processo se encontra no segundo passo,marque a alternativa certa

Imagem sem legenda

()Ao atualizar as alturas será verificado que o fator de balanço do nó com chave D estará negativo, necessitando de uma rotação simples esquerda para regular a estrutura.

()Ao atualizar as alturas será verificado que o fator de balanço do nó com chave C será positivo. Necessitando de uma rotação simples para esquerda.

()Ao atualizar as alturas será verificado que o fator de balanço do nó com chave D estará negativo, necessitando de uma rotação simples direita para regular a estrutura.

()As alturas serão atualizadas e não existirá nó desregulado, finalizando o processo de inserção.

Estrutura de Dados I

•

USP-SP

0

6

Juan Carlos Batista Leonel

09/04/2019

💡 6 Respostas

Andre Smaira

30.09.2019

Nesse exercício vamos estudar árvores AVL.

---

Uma árvore AVL é uma árvore binária balanceada, no sentido em que o chamado fator de balanço, que nada mais é que a diferença entre a altura da sub-árvore da esquerda menos a altura da sub-árvore da direita:

$\[f=h_L-h_R\]$

deve ter módulo sempre inferior a 2.

---

Analisando a imagem é possível determinar o fator de balanço de cada vértice:

$f_A=0-0=0\ \checkmark$

$f_C=1-3=-2\ \times$

$f_D=0-2=-2\ \times$

$f_E=0-1=-1\ \checkmark$

$f_G=0-0=0\ \checkmark$

Esses resultados nos mostram que as únicas alternativas possivelmente corretas até o momento são A e C, visto que indicam o fator de balanço negativo para o nó D.

---

Quando o fator de balanço é menor que -1, devemos rotacionar para a esquerda, logo a alternativa A é a correta.

2

0

Paulo Santos

10.04.2019

null

0

Vitinho Radikal

05.04.2023

)Ao atualizar as alturas será verificado que o fator de balanço do nó com chave D estará negativo, necessitando de uma rotação simples esquerda para regular a estrutura.

0