IF096 - Algoritmos e Estruturas de Dados
 agosto a dezembro de 1999

Exercício 2
Atenção: A data da entrega foi adiada para o dia 30/setembro.

1. Escrever um procedimento para, dada uma árvore binária (implementada com apontadores), identificar o fator de equilíbrio de cada nó.
O fator de equilíbrio é um inteiro (positivo ou negativo) que indica a diferença entre as alturas das sub-árvores à esquerda e à direita do vértice.
Note que este deve ser um procedimento recursivo, onde a informação é passada bottom-up, ou seja, de baixo para cima. A base da recursão está nas folhas, onde as soluções são triviais.

Esclarecimento!!! Sua solucao deve ser na ordem de n no pior caso!!!

2. Escrever um procedimento para inserção em árvore AVL (Naturalmente isso inclui a rotação simples e a dupla).

Esclarecimento!!! A funcao de insercao deve ser da ordem de (log n) no pior caso!!!

Observe que você precisará cuidar de quatro situações diferentes quanto a rotação. 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

3. Resolver o problema 3.5 na pág. 56 do livro de Udi Manber.

Retorna à página Principal do Curso

[Última alteração em 24.setembro.99 por katia.]