Universidade Federal de Pernambuco
Centro de Informática
IF672 - Algoritmos e Estruturas de Dados
junho a setembro de 2002
IMPORTANTE:
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 |
Veja os detalhes das rotações em : http://www.cin.ufpe.br/~if672/2002.1/ppt/ArvoresAVL.pps
IMPORTANTE:
A função de inserção deve ser eficiente!!!
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.
