Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — CETAP 2023

Algoritmos e Estrutura de DadosEstrutura de Dados
Código
qq843165
Banca
CETAP
Órgão
SANTA CASA-PA
Ano
2023
Nível
Superior
Cargo
Analista de Sistemas
Árvores AVL são uma estrutura de dados de árvore binária de busca balanceada, onde a diferença de altura entre assubárvores esquerda e direita de qualquer nó não deve ser maior que 1. Considere as seguintes operações de rotação para balancear a árvore AVL:I. Rotação simples à direita (RR).II. Rotação simples à esquerda (RL).III. Rotação dupla à direita (DRR).IV. Rotação dupla à esquerda (DRL).Dado o seguinte trecho de pseudocódigo para uma inserção em uma árvore AVL:função inserir_avl(T, chave)se T é vaziacriar novo nó com chavesenão se chave< T.chaveT.esquerda = inserir_avl(T.esquerda, chave)se laltura(T.esquerda) - altura(T.direita)| > 1realizar operação de rotação necessáriasenão se chave> T.chaveT.direita = inserir_avl(T.direita, chave)se laltura(T.esquerda)- altura(T.direita)| > 1realizar operação de rotação necessáriaQual das seguintes opções descreve corretamente quando a rotação simples à direita (RR) deve ser aplicada durante a inserção?
  1. AA rotação simples à direita (RR) não é usada durante a inserção em árvores AVL.
  2. BQuando a chave é inserida na subárvore esquerda do filho esquerdo do nó desbalanceado.
  3. CQuando a chave é inserida na subárvore direita do filho esquerdo do nó desbalanceado.
  4. DQuando a chave é inserida na subárvore esquerda do filho direito do nó desbalanceado.
  5. EQuando a chave é inserida na subárvore direita do filho direito do nó desbalanceado.
Revelar gabarito e comentário

GabaritoB — Quando a chave é inserida na subárvore esquerda do filho esquerdo do nó desbalanceado.

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Árvores AVL: rotações

Gabarito: letra B. A rotação simples à direita (RR) é aplicada quando o nó desbalanceado tem fator de balanço +2 (subárvore esquerda mais alta) e seu filho esquerdo também tem fator +1, o que caracteriza inserção na subárvore esquerda do filho esquerdo. Essa é a descrição exata da alternativa B.

Alternativa A — ❌ Incorreta

Afirma que RR não é usada na inserção, o que é falso. A rotação simples à direita é uma das operações fundamentais de balanceamento em AVL, aplicada no caso descrito acima.

Alternativa B — ✅ Correta ⟵ GABARITO

Conforme a teoria, quando a chave é inserida na subárvore esquerda do filho esquerdo do nó desbalanceado, ocorre uma "linha reta" à esquerda, exigindo uma rotação simples à direita (RR). O nó desbalanceado vira filho direito do seu filho esquerdo, restaurando o equilíbrio.

Alternativa C — ❌ Incorreta

Descreve a inserção na subárvore direita do filho esquerdo. Essa configuração (esquerda-direita) requer uma rotação dupla (primeiro à esquerda no filho, depois à direita no nó), e não uma rotação simples à direita.

Alternativa D — ❌ Incorreta

Descreve a inserção na subárvore esquerda do filho direito (direita-esquerda), que também exige rotação dupla (primeiro à direita no filho, depois à esquerda no nó), não RR.

Alternativa E — ❌ Incorreta

Descreve a inserção na subárvore direita do filho direito (direita-direita), que necessita de rotação simples à esquerda (LL), e não RR.

NÃO CAIA NESSA!

A banca confunde os casos de rotação simples com dupla e inverte a direção. Lembre-se: RR = esquerda-esquerda (EE); LL = direita-direita (DD). As duplas são os casos mistos (ED e DE). Decore: "Rotações simples têm o mesmo lado; duplas têm lados opostos".

Gabarito: letra B.

Link permanente: /questoes/qq843165