A respeito de estrutura de dados, julgue o item que se segue...
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.
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 nó é 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