Abd ttrabalho

Algoritmos e Estruturas de Dados 2007 / 2008 Departamento de Ciências e Tecnologias
Data: 26/06/2008 (19:00) – Duração: 2H

Frequência Teórica

Nome: Curso:

Número: Turma: D: N:

NOTAS:
1. O teste é realizado sem consulta. 2. Não serão aceites respostas a lápis e não serão corrigidas as respostas de letra elegível. 3. Responda a cada uma das questões de forma objectiva.

GRUPO A 1. Considere a árvore seguinte árvore:

PORTO

GOUVEIA

VISEU

FARO

HORTA

SETUBAL

1.1. Supondo que se trata de uma árvore AVL mostre o estado de evolução da árvore após cada operação de inserção e remoção. A remoção de elementos é feita com base na árvore obtida após todas as inserções. Justifique convenientemente a sua resposta. Inserir: CALDAS da RAINHA, COIMBRA, SEIA Remover: CALDAS da RAINHA, GOUVEIA RESPOSTA: Inserir CALDAS da RAINHA não provoca qualquer alteração de equilíbrio na árvore, mas a inserção de COIMBRA logo em seguida vai provocar um desequilíbrio no nó FARO e em consequência um desequilíbrio no nó GOUVEIA e também no nó PORTO.

+2

PORTO

+2 GOUVEIA +2 FARO -1 CALDAS da RAINHA 0 COIMBRA HORTA 0 SETÚBAL

+1 VISEU 0

A sub-árvore esquerda neta interior do nó FARO (nó em desequilíbrio mais próximo do nó COIMBRA) foi a árvore afectada com a inserção do nó COIMBRA, assim sendo o reequilíbrio faz-se ao executar uma dupla rotação à direita do nó FARO, a qual é

Frequência Teórica – 26 Jun 2008 - CORRECÇÃO

2

constituída por uma rotação simples à esquerda do nó CALDAS da RAINHA, seguida de uma rotação simples à direita do nó FARO. Após rotação simples à esquerda de CALDAS da RAINHA..

+2

PORTO

+2 GOUVEIA +2 FARO +1 COIMBRA 0 HORTA 0 SETÚBAL

+1 VISEU 0

CALDAS da RAINHA

Após rotação simples à direita de FARO..

+1

PORTO

+1 GOUVEIA 0 COIMBRA 0 CALDAS da RAINHA FARO HORTA 0 0 SETÚBAL

+1 VISEU 0

De seguida inserir SEIA vai provocar um desequilíbrio no nó VISEU.

Frequência Teórica – 26 Jun 2008 -