IF096 - Algoritmos e Estruturas de Dados
 março a junho de 2000

Exercício 2
Data da entrega: 04 de abril de 2000.

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:
A função de inserção deve ser da ordem de (log n) no pior caso!!!

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

2. Escreva um programa para, dada uma árvore binária implementada com apontadores, imprimir as chaves dos nós que constituem o maior caminho nesta árvore, na ordem em que eles aparecem no caminho.

Esse programa deve ter dois módulos:
        - Um para identificar qual o comprimento e onde se localiza o maior caminho, e
        - Outro para fazer a impressão do caminho.

IMPORTANTE:
O seu programa só deve visitar cada nó da árvore a partir do pai no máximo duas vezes, uma 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.

   

Retorna à página Principal do Curso

[Última alteração em 21.março.2000 por katia.]