INF 1010 Estruturas de Dados Avançadasnoemi/eda-16.2/comentarios.pdf · 2016. 9. 28. · remoção • voltamosa ... 2 197. remoçãoárvore AVL 100 140 183 50 17 121 2 197. remoçãoárvore

INF 1010Estruturas de Dados Avançadas

26/09/16 © 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1 1

voltando ao tempo de CPU

26/09/16 2© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1

P1 P2 P3 P1 P3 P1 P2 P3 P1

tempo

medidas de tempo

c1 = clock();

...

c1 = clock() = c1;

não precisamos dividir por ”número de ticks porsegundo”, pois só estamos interessados emcomparar coisas, não em obter tempos absolutos!


questões comuns

• medidas com TAM muito pequeno

• computador é muito rápido (ainda bemJ)

questões comuns – árvore binária

• problemas na remove (1)

remove (m, chave):if (chave < m->chave)desce subárvore à esquerda

else if (chace > m->chave)desce subárvore à direita

else/* encontrou *//* tratar casos distintos *//* folha, filho único, dois filhos */



remove (m, chave):…/* dois filhos */ procura filho mais à esquerda em sa à direita”troca” com nó correntelibera filho



remove (m, chave):…/* dois filhos */sucessor = m->dir;while (sucessor->esq != NULL) {sucessor = sucessor->esq;

}aux = m;m = sucessor;sucessor = aux;free(aux);m->dir = remove(m->dir, chave);

100

140

183

50

12117 61

270170



remove (m, chave):…/* dois filhos */while (sucessor->esq != NULL)

sucessor = sucessor->esq;

m->chave = sucessor->chave; /* troca as chaves */sucessor->chave = chave;

m->dado = sucessor->dado;

free(sucessor);0

100

140

183

50

12117 61

270170



remove (m, chave):…/* dois filhos */aux = m->esq;while(aux->dir != NULL)

aux = aux->dir;m->dado = aux->dado;m->chave – aux->chave;m->esq = removeNo(m->esq, aux->chave);

100

140

183

50

12117 61

270170



remove (m, chave):…/* dois filhos */Mapa *temp = m->dir; Mapa *tempAnterior = NULL;while(temp->esq != NULL) { //Caminha mais à esquerda possível com

tempAnterior = temp;temp = temp->esq;

}... acerta a árvore diretamente pois tem ponteiro p/ anterior

100

140

183

50

12117 61

270170

outro comentário

• fazer uma debug_mostra_mapa que

mostre de fato!100

140

183

50

12117 61

270

100, 50, 17, 61, 140, 121, 183, 270

100

140

183

50

12117 61

270100

140

183

50

12117

61

270

(100 (50 (17 () ()) (61()()))(140 (121()())(183 ()(270()()))))

100

140

183

50

12117 61

270

100

140

183

50

12117

61

270

(100 (50 (17 (61()()) ()) ())(140 (121(183()())())(270()()))))

árvores AVL

100

140

183

50

12117 61

270

remoção

• voltamos a precisar de ajustes

• só que podemos precisar de váriosajustes

remoção árvore AVL

100

140

183

50

12117 61

2 197


100

140

183

50

12117 61

2 197


100

140

183

50

12117

2 197

remoção árvore AVL: um ajuste

100

140

183

17

1212

197

50

remoção árvore AVL – outro exemplo

100

140

183

50

12161

197

300

h=4h=4

h=3


100

140

183

50

12161

197

300

h=4h=4

h=3


100

140

183

50

61

197

300

h=4h=4

h=3


100

183

140

50

61 197

300

h=4h=4

h=2

Exemplo: Remove 8

26/09/16 24

5

3

82

1 7 10

9 116

5

3

72

1 6 10

9 11

© 2012 DI, PUC-Rio • Estruturas de Dados Avançadas • 2012.1

Exemplo: Remove 6

26/09/16 25

5

3

72

1 6 10

9 11

5

3

72

1 10

9 11


Exemplo: Remove 6

26/09/16 26

5

3

72

1 6 10

9 11

5

3

72

1 10

9 11

rotação à esquerda

5

3 7

2

1

10

9

11


Problemas com as Árvores AVL

•Problema:• Nem sempre uma ÚNICA rotação

(simples ou dupla) resolve o problema de desbalanceamento dos nós

• Há casos em que O(log n) rotações são necessárias para tornar a árvore balanceada

•Exemplo (a seguir):• exclusão do nó provoca diversas rotações


remove 3

Múltiplas Rotações na Árvore AVL

26/09/16 28

5

4

93

1 8 11

10 1272

6

5

93

1 8 11

10 1272

6


rotação dupla

Múltiplas Rotações na Árvore AVL

26/09/16 29

5

4

93

1 8 11

10 1272

6

5

93

1 8 11

10 1272

6

5

9

31 8 11

10 127

2

6


rotação duplaMúltiplas Rotações na Árvore AVL

26/09/16 30

5

4

93

1 8 11

10 1272

6

5

93

1 8 11

10 1272

6

5

9

31 8 11

10 127

2

6

5

9

31 8 11

10 127

2

6

rotação dupla 5 9

31

8

11

10 12

72

6


Esboço do algoritmo de remoção

•Pesquise o nó que contém a chave procurada,

aplicando recursivamente o algoritmo de remoção

•Quando achar o nó

• faça a remoção

(semelhante à remoção em árvore de busca binária)

• analise o balanceamento

• Se o nó estiver desbalanceado ( |fb| >1 ),

faça as devidas rotações

•Recursivamente, reporte uma mudança na altura de um nó

ao seu pai para que ele faça as devidas correções


Esboço do algoritmo de remoção

•Pontos adicionais da remoção

(que não ocorrem na inserção)

• tratar todos os casos possíveis de altura nas

rotações

• analisar quando uma sub-árvore muda de altura

para reportar esta informação ao pai


Casos de rotação à esquerda (a s.a.e. perdeu altura)

26/09/16 33

2r

t

T4

1

T1

m


0r

t

T4

0

T1 m

2r

t

T4

0

T1

m


1r

t

T4

-1

T1 m

2r

t

T4

-1

T1

s

T2 T3

rotação dupla


Rotação dupla direita-esquerda (fb=2)

26/09/16 34

2r

t

T4

-1

T1

s

T2 T3

0

2r

t

T4

-1

T1

s

T2 T3

-1

2r

t

T4

-1

T1

s

T2 T3

1

r t

T4T1

s

T2 T3

0

10r t

T4T1

s

T2 T3

0

0-1r t

T4T1

s

T2 T3

0

00


Documents

INF 1010 Estruturas de Dados Avançadasnoemi/eda-16.2/comentarios.pdf · 2016. 9. 28. · remoção • voltamosa ... 2 197. remoçãoárvore AVL 100 140 183 50 17 121 2 197. remoçãoárvore