Question

MAPA | ESTRUTURA DE DADOS - 02


Em 1962, os pesquisadores Adelson-Velskii e Landis (AVL) percebendo que algumas árvores binárias de busca, mesmo que ordenadas, apresentavam uma configuração ruim. Sabe-se que, dependendo da configuração na qual os dados encontram-se distribuídos em uma árvore binária, as operações de busca, inserção e remoção podem se tornar extremamente ineficientes. Em casos extremos, operações em uma árvore binária podem ser tão ineficientes quanto operar sobre listas encadeadas.


Você, enquanto um(a) estudante dedicado(a), deve ter percebido que, para evitar o desbalanceamento de uma árvore, é possível aplicar as regras de uma árvore AVL. Dessa forma, operações em árvores binárias podem atingir uma performance satisfatória. Observe o seguinte resumo das regras de inserção em uma árvore AVL:

1) Se a inserção for feita na subárvore direita do filho à direita: balanceia-se com rotação simples à esquerda.

2) Se a inserção na subárvore esquerda do filho à esquerda: balanceia-se com rotação simples à direita.

3) Se a inserção na subárvore esquerda do filho à direita: balanceia-se com rotação dupla direita-esquerda.

4) Se a inserção na subárvore direita do filho à esquerda: balanceia-se com rotação dupla esquerda-direita.

A partir das orientações iniciais, você deverá utilizar seu RA como base de dados para montar uma árvore AVL. Para isso, basta que você siga as regras de inserção de dados em árvores AVL, inserindo cada um dos algarismos do seu RA em sua respectiva árvore AVL.


Por exemplo: se meu RA é 87654321, vou inserir cada um dos dígitos da esquerda pra direita, em minha árvore AVL. O resultado seria algo como:

Answer 1

As arvores binarias geralmente seu seu filho a direita e seu filho a esquerda, que são chamados de nós ou raizes.

Regras de inserção em uma árvore AVL: inserção for feita na subárvore direita do filho à direita: balanceia-se com rotação simples à esquerda.

Se a inserção na subárvore esquerda do filho à esquerda: balanceia-se com rotação simples à direita.

Se a inserção na subárvore esquerda do filho à direita: balanceia-se com rotação dupla direita-esquerda

Se a inserção na subárvore direita do filho à esquerda: balanceia-se com rotação dupla esquerda-direita.

Answer 2

Árvores Binárias:

são estruturas do tipo árvore com as seguintes características:

A árvore tem grau 2.

Cada subárvore é identificada como subárvores esquerda e direita.

Pode haver uma ordenação entre as subárvores.

tem-se as arvores com implementação do tipo: Sequencial, Encadeada;

E as arvores binarias balanceadas, são do tipo que A altura de uma árvore binária é o nível máximo de suas folhas (profundidade).

Uma árvore binária balanceada (AVL) é uma árvore binária na qual as alturas das duas subárvores de todo nó nunca difere em mais

de 1.

O balanceamento de um NÓ é definido como a altura de sua subárvore esquerda menos a altura de sua subárvore direita.