SóProvas


ID
1229248
Banca
IBFC
Órgão
TRE-AM
Ano
2014
Provas
Disciplina
Algoritmos e Estrutura de Dados

Quanto ao Algoritmo e estrutura de dados no caso de árvore AVL (ou árvore balanceada pela altura), analise as afirmativas abaixo, dê valores Verdadeiro (V) ou Falso (F) e assinale a alternativa que apresenta a sequencia correta de cima para baixo:

( ) Uma árvore AVL é dita balanceada quando, para cada nó da árvore, a diferença entre as alturas das suas sub- árvores (direita e esquerda) não é maior do que um.

( ) Caso a árvore não esteja balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla.

Assinale a alternativa correta:

Alternativas
Comentários
  • Discordo da primeira afirmação, pois para ser balanceada a diferença entre as alturas das suas sub- árvores (direita e esquerda) tem que ser -1, 0 ou 1. Logo, colocando que não é maior do que um, se for -2 estará correto, de acordo com essa alternativa. O que realmente não é verdadeiro.

  • Gabarito errado!!

    A primeira afirmação é FALSA

    "Se o fator de balanceamento de qualquer nó ficar menor do que -1 ou maior do que 1 então a árvore tem que ser balanceada."

  • V-V

    Uma árvore binária T é denominada AVL quando, para qualquer nó de T, as alturas de suas duas subárvores, esquerda e direita, diferem em módulo de até uma unidade.

    O valor hd(u) - he(u) é denominado fator de balanço do nó. Quando um nó possui fator de balanço com valor -1, 0 ou 1 então o mesmo é um nó regulado. Todos os nós de uma árvore AVL são regulados, caso contrário a árvore não é AVL.

    a questão diz não e maior do que um.

    se maior do que 1 então a árvore tem que ser balanceada.

  • Árvores AVL

    - São árvores binárias de busca autobalanceada.

    - Mais eficientes para buscas

    - A cada nó que é inserido, alterado ou excluído, é necessário realizar todo o trabalho de balanceamento de novo para que permaneça com as características da árvore AVL.

    - Possuem complexidade O(log n).

    - Inserções e exclusões podem requerer um rebalanceamento, por meio de rotações.

    - Toda árvore completa é AVL.

    - Uma arvore AVL verifica a altura das subárvores da esquerda e da direita, garantindo que essa diferença seja menor ou igual a 1.

    - Caso a árvore não esteja balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla.

    Alternativa: D

  • Força Guerreiro!!!!!!