tyttyu

Análise de Algoritmos

www.nakamura.eti.br/eduardo

Análise de Algoritmos

• O que é
▫ Árvore de pesquisa binária
▫ Um bit a mais por nó: VERMELHO ou PRETO

• Esquema bem definido para coloração
 Nenhum caminho será 2x maior que o comprimento de qualquer outro
 Árvore balanceada (aproximadamente)
 A altura será no máximo 2 log(n+1)

2

www.nakamura.eti.br/eduardo

Análise de Algoritmos

• Regras para balanceamento
▫ O nó raiz é sempre preto
▫ Nós vermelhos possuem apenas filhos pretos
▫ Para cada nó, todos os caminhos do nodo até qualquer folha passa pelo mesmo número de nós pretos

3

www.nakamura.eti.br/eduardo

Análise de Algoritmos

15

23

6

3

2

1

12

5

7

17

13

16

27

20

25

4

www.nakamura.eti.br/eduardo

Análise de Algoritmos

LEFT-ROTATE (T,x) x 

y



x

y

RIGHT-ROTATE (T,x)








5

www.nakamura.eti.br/eduardo

LEFT-ROTATE(T,x)
1: y  x.dir;
2: x.dir  y.esq;
3: (y.esq).pai  x;
4: if x.pai = NIL then
5:
T.raiz  y;
6: else
7:
if x = (x.pai).esq then
8:
(x.pai).esq  y;
9:
else
10:
(x.pai).dir  y;
11:
end if
12: end if
13: y.esq  x;
14: x.pai  y;

Análise de Algoritmos

6

7

x

11

9

18

14

19

www.nakamura.eti.br/eduardo

LEFT-ROTATE(T,x)
1: y  x.dir;
2: x.dir  y.esq;
3: (y.esq).pai  x;
4: if x.pai = NIL then
5:
T.raiz  y;
6: else
7:
if x = (x.pai).esq then
8:
(x.pai).esq  y;
9:
else
10:
(x.pai).dir  y;
11:
end if
12: end if
13: y.esq  x;
14: x.pai  y;

Análise de Algoritmos

7

7

x

11

9

y

18

14

19

www.nakamura.eti.br/eduardo

LEFT-ROTATE(T,x)
1: y  x.dir;
2: x.dir  y.esq;
3: (y.esq).pai  x;
4: if x.pai = NIL then
5:
T.raiz  y;
6: else
7:
if x = (x.pai).esq then
8:
(x.pai).esq  y;
9:
else
10:
(x.pai).dir  y;
11:
end if
12: end if
13: y.esq  x;
14: x.pai  y;

Análise de Algoritmos

8

7