IF672 - Algoritmos e Estruturas de Dados
novembro 2002 a março 2003

Lista 2

Essa lista naturalmente NÃO é opcional

Antes de fazer estes exercícios, leia com atenção textos sobre
Recursão e Árvores (Binárias, AVL, etc...)

Implemente as árvores da questão utilizando ponteiros

*Balance de A*	*Lado Inserção*	*Sub_árvore do Filho*	*Tipo Rotação*
-1	*esquerda de A*	*esquerda de B*	*SIMPLES*
+1	*direita de A*	*direita de C*	*SIMPLES*
-1	*esquerda de A*	*direita de B*	*DUPLA*
+1	*direita de A*	*esquerda de C*	*DUPLA*

1. Escrever um procedimento para inserção em árvore AVL (naturalmente isso inclui a rotação simples e a dupla), e outro para impressão dos filhos à esquerda e à direita de um dado nó.

IMPORTANTE:
Leia (e entenda) o texto nas páginas 71 a 77 do livro de Udi Manber antes de começar a sua implementação.
Observe que há diversos casos de inserção que não requerem rotação.
No caso de ser necessário fazer rotação, há quatro situações diferentes para considerar:
Se A é o nó crítico, B é o seu filho à esquerda e C seu filho à direita, então:

Balance de A Lado Inserção Sub_árvore do Filho Tipo Rotação

-1 esquerda de A esquerda de B SIMPLES

+1 direita de A direita de C SIMPLES

-1 esquerda de A direita de B DUPLA

+1 direita de A esquerda de C DUPLA

IMPORTANTE:

A função de inserção deve ser da ordem de O(log n) (ou seja, ser feita do jeito que foi mostrado em sala de aula) no pior caso!!!

O seu programa só deve visitar cada nó da árvore a partir do pai no máximo uma vez para cada um dos módulos acima. Assim, as informações devem ser "carregadas" enquanto estão disponíveis, obedecendo ao fluxo da informação.

[Última alteração em 26/11/2002 por katia.]