As árvores AVL são um tipo específico de árvore binária balanceada, garantindo que o balanceamento s...

Alternativa E - 1- um; 2 - rotações; 3 - balanceamento

Introdução

A questão aborda as Árvores AVL (Adelson-Velsky e Landis), que são um tipo fundamental de estrutura de dados na ciência da computação. Elas são uma variação das árvores binárias de busca (BSTs) que se destacam por sua capacidade de manter-se balanceadas, garantindo assim que as operações de busca, inserção e remoção de nós ocorram em tempo logarítmico (O(log n)), mesmo no pior caso. O balanceamento é crucial para evitar que a árvore se degenere em uma lista encadeada, o que resultaria em um desempenho linear (O(n)).

Desenvolvimento

Para manter o desempenho eficiente, as árvores AVL impõem uma condição de balanceamento rigorosa. A principal propriedade de uma árvore AVL é que, para qualquer nó na árvore, a diferença entre a altura de sua subárvore esquerda e a altura de sua subárvore direita (conhecida como fator de balanceamento) deve ser, no máximo, 1 em valor absoluto. Isso significa que o fator de balanceamento de um nó pode ser -1, 0 ou 1.

Quando uma operação de inserção ou deleção causa um desbalanceamento (ou seja, o fator de balanceamento de algum nó se torna 2 ou -2), a árvore precisa ser re-equilibrada. Este re-equilíbrio é realizado através de um conjunto de operações chamadas rotações. As rotações rearranjam os nós da árvore de forma eficiente, restaurando a propriedade AVL sem violar a propriedade de uma árvore binária de busca. Existem quatro tipos básicos de rotações: rotação simples à esquerda (LL), rotação simples à direita (RR), rotação dupla à esquerda-direita (LR) e rotação dupla à direita-esquerda (RL).

O "fator de balanceamento" de cada nó é a métrica que indica precisamente o estado de balanceamento local daquele nó. Ele é calculado como: altura(subárvore esquerda) - altura(subárvore direita).

Análise

A questão pede para preencher três lacunas, que se referem a propriedades chave das árvores AVL. Vamos analisar cada preenchimento e comparar com as alternativas:

1. preencher 1: "a diferença de altura entre as subárvores esquerda e direita de qualquer nó seja, no máximo, preencher 1."

   • Conforme explicado, a propriedade AVL estabelece que a diferença absoluta de altura entre as subárvores esquerda e direita de qualquer nó deve ser no máximo 1.
   • Portanto, o termo correto é "um".

2. preencher 2: "Estas árvores podem ser desbalanceadas durante a inserção, mas devem ser re-equilibradas automaticamente através de preencher 2."

   • O mecanismo fundamental para re-equilibrar uma árvore AVL após inserções ou deleções que causam desbalanceamento são as rotações.
   • Portanto, o termo correto é "rotações".

3. preencher 3: "Cada nó em uma árvore AVL possui um fator de preencher 3, ou seja, é o fator que indica a diferença entre a altura da subárvore esquerda e a altura da subárvore direita."

   • O nome desse fator que mede a diferença de altura entre as subárvores esquerda e direita é o fator de balanceamento.
   • Portanto, o termo correto é "balanceamento".

Com base nesta análise, os termos corretos para preencher as lacunas são:

Vamos agora verificar as alternativas:

| Alternativa | preencher 1 | preencher 2 | preencher 3 | Análise | | :---------- | :------------ | :------------ | :------------ | :--------------------------------------------------------------------------------------------------------- | | (A) | dois | inserções | altura | Incorreta. [1] deve ser 'um', [2] 'rotações', [3] 'balanceamento'. | | (B) | um | rotações | altura | Incorreta. [3] deve ser 'balanceamento'. | | (C) | dois | deleções | balanceamento | Incorreta. [1] deve ser 'um', [2] 'rotações'. O re-equilíbrio ocorre após inserções e deleções. | | (D) | um | inserções | balanceamento | Incorreta. [2] deve ser 'rotações'. As 'inserções' são a causa do desbalanceamento, não o mecanismo de re-equilíbrio. | | (E) | um | rotações | balanceamento | Correta. Todos os termos estão de acordo com a definição e o funcionamento das árvores AVL. |

Conclusão

A compreensão dos conceitos de fator de balanceamento, a regra de diferença máxima de altura (1) e o uso de rotações para re-equilibrar a árvore são fundamentais para entender como as Árvores AVL garantem eficiência logarítmica em operações. A alternativa (E) preenche corretamente todas as lacunas, descrevendo precisamente os mecanismos que definem e mantêm a propriedade de balanceamento dessas importantes estruturas de dados.

Alternativa E.