SóProvas


ID
4112881
Banca
CESPE / CEBRASPE
Órgão
Prefeitura de Boa Vista - RR
Ano
2004
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

A respeito de estrutura de dados, julgue o item que se segue.


Uma árvore binária é dita equilibrada se a diferença entre as alturas das subárvores de cada nó — valor absoluto da diferença entre as alturas da subárvore direita e da subárvore esquerda — é, no máximo, igual a 1.

Alternativas
Comentários
  • Obrigado pelos comentários caros colegas, e obrigado ao quadrado pra equipe do QCONCURSOS que não deixa nenhuma questão sem explicação lógica.

  • certa, para os que não são assinantes

  • Gabarito: Certo

    Primeiro, conceitos importantes de uma estrutura de árvore:

    1) Uma estrutura de árvore é constituída de um conjunto finito de elementos, em que cada elemento é um nó que se subdivide em subárvores.

    2) Existe um nó chamado de raiz, que dá início à árvore, e os outros nós geram subconjuntos denominados de subárvores.

    3) A altura de uma árvore (ou de subárvore) corresponde ao maior nível. Em outras palavras, é a maior distância entre o nó e o seu último elemento.

    Agora conceituando uma árvore binária:

    1) Uma árvore binária é um conjunto finito de elementos que ou é vazio ou é composto de três conjuntos disjuntos

    ● Árvore binária vazia: Só contém um único elemento, a raiz.

    ● Árvore binária não vazia: Composta da raiz e de outros dois subconjuntos -> a subárvore da esquerda e subárvore da direita. As subárvores da esquerda ou da direita podem estar vazias.

    Agora a definição de árvore binária balanceada: Uma árvore binária é considerada balanceada quando as alturas das duas subárvores (esquerda e direita) nunca difere em mais de 1, ou seja, é no máximo igual a 1. O balanceamento de um é definido como a altura de sua subárvore esquerda menos a altura de sua subárvore direita.

    Com isso, pode-se concluir que a questão traz exatamente a definição de árvore binária balanceada estando, portanto, correta.

    Fonte:

    1) http://www.ic.uff.br/~boeres/slides_ed/ed_ArvoresPercursos.pdf

    2) http://wiki.icmc.usp.br/images/f/f0/AVL.pdf

    Espero ter ajudado. Qualquer erro, me mandem mensagem.

    Bons estudos!