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

Próximas questões
Com base no mesmo assunto
Q1370958 Algoritmos e Estrutura de Dados

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

Gabarito comentado

Confira o gabarito comentado por um dos nossos professores

Alternativa correta: C - certo

Explicação: A questão aborda o conceito de árvore binária equilibrada. Esse é um tipo específico de árvore binária onde a diferença entre as alturas das subárvores esquerda e direita de cada nó é, no máximo, igual a 1.

Vamos entender melhor:

Uma árvore binária é uma estrutura de dados em que cada nó possui, no máximo, dois filhos. Pode ser um nó à esquerda e/ou um nó à direita.

Altura da árvore é o número de arestas no caminho mais longo entre o nó raiz e uma folha (um nó sem filhos).

Uma árvore binária é dita equilibrada se, para cada nó, a diferença absoluta entre a altura das suas subárvores esquerda e direita é, no máximo, igual a 1. Isso significa que nenhuma subárvore é significativamente mais profunda que a outra.

Justificativa da alternativa correta: A alternativa correta é C - certo, porque a definição fornecida na questão está de acordo com a definição técnica de uma árvore binária equilibrada.

Por que a alternativa errada estaria incorreta?

Se a alternativa fosse E - errada, isso significaria que a definição dada para a árvore binária equilibrada estaria incorreta. No entanto, como a definição fornecida está correta, a alternativa errada não se aplica.

Entender o conceito de equilíbrio em árvores binárias é essencial para otimização em operações de busca, inserção e remoção em estruturas de dados, como AVL trees e red-black trees, que utilizam esse princípio para manter a eficiência.

Espero que essa explicação tenha facilitado a compreensão do tema. Se tiver mais dúvidas ou precisar de mais detalhes, estou à disposição!

Clique para visualizar este gabarito

Visualize o gabarito desta questão clicando no botão abaixo

Comentários

Veja os comentários dos nossos alunos

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!

Clique para visualizar este comentário

Visualize os comentários desta questão clicando no botão abaixo