MAPA ESTRUTURA DE DADOS 2 - 2021
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 estudante dedicado, 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.
meu RA é 87654321, vou inserir cada um dos dígitos da esquerda pra direita, em minha árvore AVL. O resultado seria algo como:
Soluções para a tarefa
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: nserçã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.
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.