Questão 960994

• Banca: Marinha
• Órgão: Quadro Técnico
• Ano: 2011
• Provas: Marinha - 2011 - Quadro Técnico - Primeiro Tenente - Informática
• Disciplina: Algoritmos e Estrutura de Dados

Assinale a opção que apresenta dois exemplos de árvores binárias classificadas como Balanceadas.

• A. Ziguezague e Ternária.
• B. Ziguezague e Partilha.
• C. AVL e Partilha.
• D. AVL e Graduada.
• E. Graduada e Partilha.

Gabarito: D

Comentários

• Árvore AVL (ou árvore balanceada pela altura), em Ciência da Computação, é uma árvore de busca binária auto-balanceada. Em tal árvore, as alturas das duas sub-árvores a partir de cada nó diferem no máximo em uma unidade. As operações de busca, inserção e remoção de elementos possuem complexidade O( log2 n ) (no qual  é o número de elementos da árvore)1 . Inserções e remoções podem também requerer o rebalanceamento da árvore, exigindo uma ou mais rotações.

• Uma árvore rubro-negra é um tipo de árvore de busca binária balanceada onde cada nó tem um atributo de cor, vermelho ou preto.
  

  Árvores Graduadas

  Preservam a característica de balanceamento. São equivalentes às Rubro-Negras. Diferenciam-se só na representação(rubro-negra por cor e graduada por inteiro).
  

  
  

  
  

  
  

  
  

  GABARITO D.

• Tipos de Árvores Balanceadas: AVL, Graduadas, Rubro-Negras e B.