Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FADESP 2018

Algoritmos e Estrutura de DadosEstrutura de Dados
Código
qq333401
Banca
FADESP
Órgão
IF-PA
Ano
2018
Nível
Superior
Cargo
Professor - Informática
Sejam [3, 1, 2, 7, 5, 4, 6], [3, 1, 2, 6, 4, 5, 7] e [4, 2, 1, 3, 6, 5, 7] as sequências produzidas pelo percurso em pré-ordem das árvores binárias de busca T1, T2 e T3, respectivamente, é correto afirmar que é(são) árvore(s) balanceada(s) do tipo AVL (Adelson-Velski e Landis)
  1. AT1.
  2. BT1 e T2.
  3. CT1 e T3.
  4. DT2 e T3.
  5. ET1, T2 e T3.
Revelar gabarito e comentário

GabaritoD — T2 e T3.

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”.

Análise de árvores AVL a partir de percursos em pré-ordem

Gabarito: letra D. Apenas as sequências de T2 e T3, quando inseridas em uma árvore binária de busca (BST) na ordem da pré-ordem, produzem árvores que satisfazem a condição AVL (diferença de altura entre subárvores esquerda e direita de cada nó ≤ 1). T1 resulta em desbalanceamento no nó 7.

Reconstrução das árvores

Dada uma sequência de pré-ordem de uma BST, podemos reconstruir a árvore inserindo os elementos nessa ordem em uma BST inicialmente vazia. Aplicamos o processo:

T1: [3, 1, 2, 7, 5, 4, 6]

Inserções:

  • 3 → raiz

  • 1 → esquerda de 3

  • 2 → direita de 1

  • 7 → direita de 3

  • 5 → esquerda de 7

  • 4 → esquerda de 5

  • 6 → direita de 5

Estrutura resultante:

        3
       / \
      1   7
       \ /
        2 5
         / \
        4   6

Cálculo das alturas e fatores de balanceamento:

  • Nó 4: altura = 1, fb = 0

  • Nó 6: altura = 1, fb = 0

  • Nó 5: altura = 2 (máx(1,1)+1), fb = |1-1| = 0 → regulado

  • Nó 2: altura = 1, fb = 0

  • Nó 1: altura = 2 (esq=0, dir=1), fb = |0-1| = 1 → regulado

  • Nó 7: altura = 3 (esq=2 (nó 5), dir=0), fb = |2-0| = 2 → DESREGULADO (fb = -2? Na verdade, fb = altura_dir - altura_esq = 0-2 = -2). Portanto, T1 não é AVL.

T2: [3, 1, 2, 6, 4, 5, 7]

Inserções:

  • 3 → raiz

  • 1 → esquerda de 3

  • 2 → direita de 1

  • 6 → direita de 3

  • 4 → esquerda de 6

  • 5 → direita de 4

  • 7 → direita de 6

Estrutura:

        3
       / \
      1   6
       \ / \
        2 4 7
           \
            5

Alturas:

  • Nó 2: altura 1, fb=0

  • Nó 1: altura 2 (esq=0, dir=1), fb=|0-1|=1 → regulado

  • Nó 5: altura 1, fb=0

  • Nó 4: altura 2 (esq=0, dir=1), fb=1 → regulado

  • Nó 7: altura 1, fb=0

  • Nó 6: altura 3 (esq=2 (nó 4), dir=1 (nó 7)), fb=|2-1|=1 → regulado

  • Nó 3: altura 4 (esq=2 (nó 1), dir=3 (nó 6)), fb=|2-3|=1 → regulado

Todos os nós com fb ∈ {-1,0,1}. T2 é AVL.

T3: [4, 2, 1, 3, 6, 5, 7]

Inserções:

  • 4 → raiz

  • 2 → esquerda de 4

  • 1 → esquerda de 2

  • 3 → direita de 2

  • 6 → direita de 4

  • 5 → esquerda de 6

  • 7 → direita de 6

Estrutura:

        4
       / \
      2   6
     / \ / \
    1  3 5  7

Alturas:

  • Nó 1: altura 1, fb=0

  • Nó 3: altura 1, fb=0

  • Nó 2: altura 2 (esq=1, dir=1), fb=0 → regulado

  • Nó 5: altura 1, fb=0

  • Nó 7: altura 1, fb=0

  • Nó 6: altura 2 (esq=1, dir=1), fb=0 → regulado

  • Nó 4: altura 3 (esq=2, dir=2), fb=0 → regulado

Todos os nós regulados. T3 é AVL.

Árvore

Sequência Pré-Ordem

Estrutura (raiz)

Nó Desbalanceado

Fator de Balanceamento (fb)

É AVL?

T1

[3, 1, 2, 7, 5, 4, 6]

3

7

|2-0| = 2

Não

T2

[3, 1, 2, 6, 4, 5, 7]

3

Nenhum

Todos |fb| ≤ 1

Sim

T3

[4, 2, 1, 3, 6, 5, 7]

4

Nenhum

Todos |fb| ≤ 1

Sim

1Balanceamento
Diferença de altura ≤ 1
Fator de balanceamento ∈ {-1,0,1}
2T1: [3,1,2,7,5,4,6]
Desbalanceada no nó 7 (fb=-2)
3T2: [3,1,2,6,4,5,7]
Balanceada (todos fb ∈ {-1,0,1})
4T3: [4,2,1,3,6,5,7]
Balanceada (todos fb ∈ {-1,0,1})
Árvore AVL
LEVELsoulevel.com.br
Árvore AVL: Balanceamento (Diferença de altura ≤ 1, Fator de balanceamento ∈ {-1,0,1}); T1: [3,1,2,7,5,4,6] (Desbalanceada no nó 7 (fb=-2)); T2: [3,1,2,6,4,5,7] (Balanceada (todos fb ∈ {-1,0,1})); T3: [4,2,1,3,6,5,7] (Balanceada (todos fb ∈ {-1,0,1}))

Verificação das alternativas

  • A) T1 – ❌ Incorreta. T1 não é balanceada (nó 7 com fb = -2).

  • B) T1 e T2 – ❌ Incorreta. T1 não é AVL.

  • C) T1 e T3 – ❌ Incorreta. T1 não é AVL.

  • D) T2 e T3 – ✅ Correta. Ambas satisfazem a condição AVL.

  • E) T1, T2 e T3 – ❌ Incorreta. T1 falha.

Gabarito: letra D (T2 e T3).

Link permanente: /questoes/qq333401