Considere uma estrutura de dados T como sendo uma árvore bi...

A alternativa correta é a A: balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) diferem de até uma unidade.

Vamos entender o tema da questão e justificar as alternativas:

Árvore AVL

Uma árvore AVL é um tipo de árvore binária de busca que possui a característica de ser balanceada. O nome AVL vem dos criadores da estrutura, Adelson-Velsky e Landis. O balanceamento é crucial para manter as operações de busca, inserção e remoção eficientes, garantindo, no pior caso, uma complexidade de tempo O(log n).

Um nó em uma árvore AVL é balanceado se, para qualquer nó, a altura das subárvores esquerda e direita diferem em, no máximo, uma unidade. Isso é conhecido como a propriedade de balanceamento. Quando essa propriedade é violada após uma inserção ou remoção, a árvore deve ser reestruturada por meio de rotações para restaurar o balanceamento.

Agora, vamos analisar as alternativas:

Alternativa A: balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) diferem de até uma unidade.

Esta alternativa está correta. Esta é a definição exata da propriedade de balanceamento de uma árvore AVL.

Alternativa B: balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) são sempre idênticas.

Esta alternativa está incorreta. Em uma árvore AVL, as alturas das subárvores podem diferir em até uma unidade, e não precisam ser sempre idênticas.

Alternativa C: não balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) diferem de até uma unidade.

Esta alternativa está incorreta. A árvore AVL é, por definição, balanceada. Além disso, a descrição da diferença de altura está correta, mas a afirmação de que a árvore é "não balanceada" está errada.

Alternativa D: não balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) são sempre idênticas.

Esta alternativa está incorreta. Assim como na alternativa B, a afirmação de que as alturas devem ser idênticas está errada. Adicionalmente, a árvore AVL é balanceada, ao contrário do que é dito na alternativa.

Alternativa E: não balanceada, em que, para qualquer nó de T, as alturas de suas duas subárvores (esquerda e direita) diferem exatamente de uma unidade.

Esta alternativa está incorreta. Em uma árvore AVL, as alturas das subárvores podem diferir em até uma unidade, não exatamente uma unidade. Além disso, a árvore AVL é balanceada.

Espero que esta explicação tenha esclarecido suas dúvidas sobre árvores AVL. Caso precise de mais alguma explicação, estou à disposição!

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.

Pela definição fica estabelecido que todos os nós de uma árvore AVL devem respeitar a seguinte propriedade:

|h(u) - h(u)| ≤ 1, onde h(u) é a altura da subárvore direita do nó u e h(u) é a altura da subárvore esquerda do nó u.

O valor h(u) - h(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.

GABARITO A

Balanceamento Dinâmico (AVL): São árvores binárias de busca auto balanceada;

• 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;
• Para cada nó da árvore, a diferença entre as alturas das suas subárvores (direita e esquerda) sempre será igual a -1, 0 ou 1.

GABARITO A

Balanceamento Dinâmico (AVL): São árvores binárias de busca auto balanceada;

• 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;
• Para cada nó da árvore, a diferença entre as alturas das suas subárvores (direita e esquerda) sempre será igual a -1, 0 ou 1.