Question

MAPA - ADS - ESTRUTURA DE DADOS II - 52/2021
1ª QUESTÃO

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.

OLIVEIRA, P. M. de.; PEREIRA, R. de. L. Estruturas de Dados II. Maringá: Unicesumar, 2019.

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:
O QUE DEVE SER ENVIADO:
1. Para esta atividade, você deverá enviar, como resposta, um arquivo PDF ou .DOC considerando seu RA original (escrito em texto, normalmente), juntamente com uma imagem de sua árvore AVL montada a partir do seu RA (conforme orientações anterior).
2. Utilize o template do Mapa disponível no Material da Disciplina.

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: 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.