Aula 5 - Árvores Red Black e Árvores B

7/24/2019 Aula 5 - rvores Red Black e rvores B

1/60

RVORESrvores Red-Black


2/60

IntroduoSo tambm rvores binrias de busca

Conhecidas tambm como rvores Rubro-Negras

Foram inventadas em 1!" com o nome de

rvores binrias simtricas #ossuem dois novos cam$os%

o &m bit e'tra $ara arma(enar a cor de cada n)

o

&m $onteiro $ara o n) $ai* rvore a$ro'imadamente ba+anceada,

$ois nenhum caminho ser duas ve(es maiordo ue ua+uer caminho $ara uma .o+ha


3/60

Introduo

* a+tura m'ima de uma rvore R/

com n n)s internos %

#or serem ba+anceadas as o$era0es+evam o tem$o%

#ossuem me+hor desem$enho emrvores de a+turas maiores

)1log(2 += nh

)(lognO


4/60

Propriedades

123odo n) vermelhoou preto"2 * rai( da rvore necessariamente

preta

423oda .o+ha Ni+ preta

52 N)s vermelhosue no se6a .o+has$ossuem a$enas 7+hos pretos

823odos os caminhos a $artir da rai( at

suas .o+has $assam $e+a mesmauantidade de n)s pretos

92 No $odem e'istir dois n)s

vermelhosconsecutivos


5/60

Mais Propriedades

3oda ve( ue um n) inserido ou

de+etado todas as $ro$riedadesdevem ser testadas

Caso um ou mais $ro$riedades no

se6am satis.eitas ento rota0es e:oumudan0as de cores devem ser .eitasoRota0es e mudan0as de cores so .eitas

$ara manter o ba+anceamentoO bhou b+ac;-high de cada n) indica

a uantidade de n)s $retos

encontrados entre a rai( e .o+ha


6/60

Exemplo

2720

18

2210

133

51 16

4

3

2 2

3

3

2 22

3

12

1714

2 2

2 2

19 212 24 4011


7/60

Insero

3odo n) ao ser inserido verme+hooOb6etiva no mudar o bh dos n)so Se um n) inserido .or $reto e+e .ere a

$ro$riedade 8

Se um n) .or inserido na rvoreva(ia ento basta mudar a cor do n)de verme+ho $ara $reto

p p

x


8/60

Insero

Caso 1o Se um n) .or verme+ho e no tiver $ai,

ento e+e a rai( e deve sertrans.ormado em $reto

Caso "o&m n) ' esta sendo inserido, e seu tio

verme+ho ento necessrio reco+orir

o $ai, o tio e o av

Caso 5o Su$ondo ue ' esta sendo inserido em

um n) verme+ho e seu tio ni+ =$reto>,ento deve ser .eita uma rota0o


10/60

Caso

Subcaso 1 ? Caso os n)s este6am @

esuerda deve-se .a(er uma rota0o@ direitaoOs n)s devem ser reco+oridos


11/60

Caso

Subcaso " ? Caso os n)s este6am @

direita deve-se .a(er uma rota0o @esuerdaoOs n)s devem ser reco+oridos


12/60

Caso

Subcaso 4 ? caso os n)s este6am @

direita e ' se6a o 7+ho @ esuerda de$, ento deve-se se .a(er umarota0o @ direita com $ e uma

rota0o @ esuerda com a =rota0odu$+a>a

tp

x

x

a p

t

a

tx

p

Rota0o sim$+es @ esuerda

Rota0o sim$+es @direita

Recolorao de x e a


13/60

Caso

Subcaso 5 - caso os n)s este6am @

esuerda e ' se6a o 7+ho @ direita de$, ento deve-se se .a(er umarota0o @ esuerda com $ e uma

rota0o @ direita com aat

x

p

x

p a

t

a

tp

x

Rota0o sim$+es @direita

Rota0o sim$+es @ esuerda Recolorao de x e a


14/60

Rota!es com "ub-#rvores

y

x

* /

C

x

y*

/ C

direita

esquerda


15/60

8

Exemplo

Anserindo o n) ! na rvore abai'o

2

1 4

3 5

6

7

-Propriedade 4 violada-Caso 3

- Subcaso 2 Rotao esquerda no n 5


16/60

Exemplo


2

1 4

3

75

6

-Propriedade 4 violada-Basta re-colorir os ns 5 ! e

"


17/60

Exemplo


2

1 4

3

7

6

5


18/60

Casos para Correo de Cores

E'istem 4 casos $ara corre0o das cores%

oCaso 1 ? o tio do e+emento inserido verme+ho

Budar cores

oCaso " ? O tio do e+emento inserido $reto e o e+emento inserido @ direita

oCaso 4 ? O tio do e+emento inserido

$reto e o e+emento inserido @esuerda

Nos casos " e 4 - Buda-se as cores e.a(em-se uma ou duas rota0es


19/60

Exemplo$ inserindo o n% &

Caso 1% o tio do n) inserido

verme+ho


20/60

Exemplo$ Inserindo o n% &

Caso "% ! verme+ho e 15 =tio>

$retoRota0o nos e+ementos " e !

#iolao

Rotao esquerda$ % 2& % "


21/60


Caso 4 o tio do e+emento inserido @

esuerda $reto n)s ! e "continuam vio+ando a $ro$riedade 5

Rotacionar ! e 11 $ara a direita


22/60


#e+a $ro$riedade 1 o n) ! $assa a

ser $retoO n)s D e 15 so $retos, +ogo o n) 11

$assa a ser verme+ho


23/60

'l(oritmo de RotaoLeft_rotate(Tree T, obj x)

y right[x] right[x] left[y] if left[y] nil[T] then

pai[left[y]] x end if

pai[y] pai[x]

if pai[x] = nil[T] then T y

else

if x = left[pai[x]] then

left[pai[x]] y

else right[pai[x]] y end if

end if

left[y] x

pai[x]y

' al(orit)o derotao direita *

an+lo(o


24/60

'l(oritmo de Insero

RB-insert(Tree T, obj z)

ynil[T] x T

while x nil[T] do

y x if key[z] < key[x] then

x left[x] else

x right[x] end if

end while

pai[z] y

if y = nil[T] then T z else

if key[z] < key[y] then

left[y] z

else right[y] z end if

end if

left[z] nil[T]right[z] nil[T]cor[z] er!elhoRB-insert-fix"p(T, z)


25/60

'l(oritmo de Re-EstruturaoRB-insert-fix"p(Tree T, obj z)

#$while cor[pai[z]] = vermelho do%$

if pai[z] = left[pai[pai[z]]] then&$ y right[pai[pai[z]]]'$ if cor[y] = vermelho then$ caso#* cor[pai[z]] preto+$ cor[y] preto$ cor[pai[pai[z]]] er!elho$ z pai[pai[z]]

.$ else#/$ if z = right[pai[z]] then##$ caso% $*z pai[z]#%$ left-rotate(T, z)

#&$ end if#'$ caso& $*cor[pai[z]] preto#$ cor[pai[pai[z]]] er!elho#+$ right-rotate(T, pai[pai[z]])

#$ end if#$ else#.$ o !es!o 0o caso then (linhas 3 a 1!

trocando entre si right com left"%/$ end if

%#$ end while%%$ cor[T] preto


26/60

Exerc)cios

Ansira os va+ores os va+ores , " e

19 na rvore do e'em$+o anterior#esuise como .a(er a remo0o de

n)s

Am$+emente os a+goritmosdemonstrados $ara inser0o de n)sem uma rvore R/


27/60

RVORES /


28/60

Introduo

#ro$osto em 1!" $or /aGer e

BcCreight, desenvo+vido noHaborat)rio de #esuisas CientI7cas/oeing

oNo se sabe se o / de /aGer ou /oing&sado no arma(enamento em

mem)ria secundria

J uma rvore n-ria


29/60

Introduo

Botiva0o

oKuando no conseguimos traba+har namem)ria $rinci$a+ =ou $rimria>, temos ueusar a mem)ria secundria2

o Sabemos ue o acesso aos dados emmem)ria secundria muito +ento2

o #recisamos de meios e7cientes de acessoaos dados =$rovave+mente na .orma de

LMIndices>o E'em$+o% &m disco com 49 r$m na mdia

+eva Dms $ara cada acesso 1s $ara 1"acessos


30/60

Caracter)sticas

O ue a.eta o desem$enho de uma

rvore a a+tura* a+tura diminui a medida ue a aridade

aumenta

&ma rvore de ordem m tem umaaridade m, onde cada n) $ode ter m7+hos

3odas as .o+has esto no mesmo nIve+3odas as no-.o+has, com e'ce0o da

raI(, tm no mInimo m : "7+hos


31/60

Caracter)sticas

O n) raI( ou uma .o+ha ou tem de "

a m 7+hos&m n) .o+ha no contm mais ue m

? 1 chaves =e+ementos>

O nPmero m deve ser sem$re Im$ar

N de uma rvore B de ordem = 5

class #$%&Tree

' Tipo chave[])

#$%&Tree p[*])

"


32/60

Caracter)sticas

Ca$acidade m'ima de uma rvore-

/Qe$ende da a+tura e do grau

o h ordem 1 e+ementos

o h 1 T 1 e+ementos

o h " T 1 1 T 1 T

e+ementos1_ 1 = +hmelementosqtd


33/60

Insero de Elementos

*s chaves:e+ementos so inseridas

em ordem crescenteKuando o nPmero de e+ementos

u+tra$assado a uantidade de

e+ementos deve ser dividida entre onovo n) e o n) antigo


34/60

Insero de Elementos

3ente inserir a nova chave em um n) .o+ha

=na $osi0o adeuada>Se isso 7(er com ue o n) 7ue cheio,

divida a .o+ha em duas $artes e suba oe+emento centra+ $ara o n) $ai

Se isso 7(er com ue o $ai 7ue cheiore$ita o $rocesso* estratgia $oder ser re$etida at o n)

rai(

Se necessrio o n) rai( dever sertambm divido e o e+emento centra+ sertrans.ormado em nova rai( =.a(endo comue a rvore 7ue mais a+ta>


35/60

U Su$onha ue iniciemos com uma rvore / va(ia e aschaves devem ser inseridas na seguinte ordem%

1 1" D " "8 9 15 "D 1! ! 8" 19 5D 9D 4 "9 "84 88 58

U Kueremos construir uma rvore / de ordem 8U Os 5 $rimeiros e+ementos vo $ara a raI(%

U O uinto e+emento e'tra$o+a o tamanho do n)U *ssim, uando inserimos o "8 devemos dividir o n)em duas $artes e co+ocar o e+emento do meio comonova rai(

RVORE

/

1 2 8 12

,$e)plo


36/60

RVORE

/

1 2 12 25

8

25 6 14 28 17 7 52 16 48 68 3 26 29 53 55 45

1 2 12 258

I!er"do o 25 ocorre #ue$rada re%ra de &ama'o mx"mo

( )rec"!o *a+er o!)l"&


37/60

RVORE

/

6 14 28 17 7 52 16 48 68 3 26 29 53 55 45

Em seguida colocamos 6, 14 e 28 :

1 2

8

12 146 25 28

1 2 12 25

8


38/60

RVORE

/

17 7 52 16 48 68 3 26 29 53 55 45

Adicionando 17 !"o!e #e!emos ou#!o s$li#%

1 2

8

12 146 25 28

17


39/60

RVORE

/

17 7 52 16 48 68 3 26 29 53 55 45

8 17

12 14 25 281 2 6


40/60

RVORE

/

7 52 16 48 68 3 26 29 53 55 45

Continuando com 7, 52, 16 e 48

8 17

12 14 25 281 2 6 16 48 527


41/60

RVORE

/

68 3 26 29 53 55 45

E agora, inserindo o 68

8 17

12 14 25 281 2 6 16 48 527 68


42/60

RVORE

/

68 3 26 29 53 55 45

Adicionando 68 rvore causa um split na folha mais direita,fazendo com que o 48 suba raiz. Quando inserimos o 3 o split

na folha mais esquerda (o 3 sobe); 26, 29, 53, 55 vo para as

folhas:

3 8 17 48

52 53 55 6825 26 28 291 2 6 7 12 14 16


43/60

RVORE

/

45

Por fim o 45:

3 8 17 48

52 53 55 6825 26 28 291 2 6 7 12 14 16


44/60

RVORE

/Por fim, quando inserimos o 45, isso forar com que o 28 subapara a raiz Mas a raiz tambm estcheia ,

3 8 17 48

52 53 55 6825 26 29 451 2 6 7 12 14 16

28


45/60

RVORE

/Por fim, quando inserimos o 45, isso forar com que o 28 subapara a raiz Mas a raiz tambm estcheia ,

3 8 17 48

52 53 55 6825 26 29 451 2 6 7 12 14 16

28


46/60

RVORE

/O 17 tem que subir para se tornar a nova raiz lembrem-se que araiz pode ter um nico elemento.

3 8

17

48

52 53 55 6825 26 29 451 2 6 7 12 14 16

28


47/60

RVORE

/

17

3 8 28 48

2 6 7 12 14 16 52 53 55 6825 26 29 45


48/60

RVORE

/=REBOWO>

Remoo

Qurante a inser0o, a chave sem$re vai

$ara a .o+ha2 Na remo0o dese6amosremover da .o+ha2 *ssim, temos 4$ossibi+idades%

1 ? Se a chave 6 est em um n) .o+ha esua remo0o no .a( com ue o n) 7uecom $oucos e+ementos =menos ue m : "7+hos>, ento a$enas e+imine-a2

" ? Se a chave no .o+ha, ento garantido ue seu $redecessor ou

sucessor este6a em um n) .o+ha ? e nestecaso $odemos e+iminar a chave e subir o$redecessor ou sucessor $ara a $osi0oocu$ada $e+a chave e+iminada2


49/60

Remoo 4 - Se =1> ou ="> ocasionam uma .o+ha a ter um

nPmero menor ue o mInimo ento temos ueobservar os irmos ad6acentes ao n) emuesto %

A% Se um de+es tem nPmero de chaves maiorue o mInimo ento $ode-se subir uma chave

deste n) $ara o n) $ai e $egar a chave do n)$ai $ara a $osi0o da chave e+iminada

AA% Se ambos irmos no tm nPmero de chavesmaior ue o mInimo, ento suas chaves devem

ser combinadas com a chave do n) $ai2 Se este$asso 7(er com ue o n) $ai 7ue com menoschaves ue o $ermitido o $rocesso deve serre$etido at o n) rai( =se necessrio>2


50/60

RVORE

/?=REBO

WO?C*SO

1>

1212 2929 5252

22 77 99 1515 2222 5656 6969 72723131 4343

l"m"ar o 2. / c'ave! !u*"c"e&e!

0!!um"do uma rvore deordem 5


51/60

RVORE

/=REBOWO?C*SO1>

1212 2929 5252

22 77 99 1515 2222 5656 6969 72723131 4343

l"m"ar o 52

rvore B.re)oo de n no /ol0a1


52/60

1212 2929 5252

77 99 1515 2222 5656 6969 72723131 4343

l"m"a 525656

rvore B.re)oo de n no /ol0a1


53/60

RVO

RE/

1212 2929 5252

77 99 1515 2222 6969 7272 72723131 4343

l"m"a 525656

Re)oo de n no /ol0a


54/60

RVORE

/

1212 2929 5656

77 99 1515 2222 6969 72723131 4343

l"m"ar o 72ouca!c'ave!,

om$"a

Re)oo de n co) poucas c0aves


55/60

1212 2929

77 99 1515 2222 696956563131 4343

RVORE

/

l"m"ar o 22

Re)oo - Poucas c0aves nos ns ir)os


56/60

RVORE/

=REB

OWO-ARBWOOX>

1212 2929

77 99 1515 2222 696956563131 4343

l"m"ar o 22

e!cer c'ave do )a" e

!u$"r c'ave a *ol'a



57/60

1212

292977 99 1515

3131

696956564343


*

' i


58/60

*NAB*

WO

'nimao

http://slady.net/java/bt/view.php?w=600&h=450http://slady.net/java/bt/view.php?w=600&h=450

:

E ) i


59/60

:

Exerc)cios

Ansira os seguintes nPmeros em uma

rvore / de ordem 8%4, !, , "4, 58, 1, 8, 15, "8, "5, 14,

11, D, 1, 5, 41, 48, 89

Fa0a a inser0o dos e+ementos agoraem uma rvore / de ordem !2

Forma+i(e o a+goritmo de inser0o eremo0o em rvores /

* b lh


60/60

*rabalho

Am$+ementar uma rvore *VH, uma rvore

R-/ e uma rvore-/ =ordem 1 e ordem8>2

Ansira 12, 12 e 122 dee+ementos nas rvores

Veri7ue a a+tura das rvoresVeri7ue o desem$enho $ara%

o Anser0o

o /usca de metade dos e+ementoso Fa0a conc+uses com bases estatIsticas

*$resenta0o% Am$reterive+mente :11

Documents

Aula 5 - Árvores Red Black e Árvores B