Estrutura de dados algoritmos, análise da complexidade e implementações em Java e CC++

7/23/2019 Estrutura de dados algoritmos, anlise da complexidade e implementaes em Java e CC++

1/34

RVORES AVL

Lvia N. Andrade


2/34

rvores AVL

Recebem esse nome em homenagem aos seus criadores,os matemticos russos AdelsonVelskii e Landis, 1962.

ma rvore AVL ! uma rvore binria de "es#uisa onde adi$eren%a em altura entre as subrvore es#uerda e direita !no m&imo 1 '"ositivo ou negativo(.

)uando a di$eren%a chega a 2 ou *2, deve ser re$eito obalanceamento atrav!s de rota%+es.

hamamos essa di$eren%a de -$ator de balanceamento.


3/34

/escri%0o das rota%+es

Diferena dealtura de um

n

Diferena de altura don lho do n

desbalanceado

Tipo de rotao

2

1 Simples esquerda

0 Simples esquerda

-1Dupla !m "l#! paraa direi$a e pai para aesquerda

-2 1 Dupla !m "l#! paraa esquerda e pai paraa direi$a

0 Simples direi$a

-1 Simples direi$a


4/34

&em"los de alanceamentoR!$a%&! simples esquerda

6

30

1

rvore Balanceada rvoreDesbalanceada

6

31

2

12

0

+ 12

30

0

6 120

rvoreBalanceada R!$a%&! simple

para a esquerd


5/34

'(di)! em '

** n( des+alanead! , 2

v!id re+alaneamen$!Esq Ap!n$ad!r p/ in$ #

Ap!n$ad!r pu , p-Dir3 **passand! para "l#! d! n( des+alanead!

i4 pu-+alaneamen$! ,, 1 **n( "l#! , 1/ mesm! sinal r!$a%&!

simples a esquerdaprin$45r!$aa! a esquerda !m 6ld7n5/ pu-Re).'#ave3

p-Dir , pu-Esq3 **direi$a de p ap!n$a para null

pu-Esq , p3

p-+alaneamen$! , 03p , pu3

8

p-+alaneamen$! , 03

# , 03

}

6

31

2

120

pu

p


6/34

'(di)! em '







pu-Esq , p3 **p passa a ser "l#! a esquerda de pu


8

p-+alaneamen$! , 03

# , 03

} 6

31

2 120

pu

p


7/34

'(di)! em '








p-+alaneamen$! , 03 **a$uali9a :; de pp , pu3

8

p-+alaneamen$! , 03

# , 03

} 6

31

0 120

pu

p


8/34

'(di)! em '








p-+alaneamen$! , 03 **a$uali9a :; de pp , pu3 **pu a)!ra < p

8

p-+alaneamen$! , 03 **a$uali9a :; de p

# , 03

} 6

30

0 120

p


9/34



n


desbalanceado

Tipo de rotao

2

1 Simples esquerda

0 Simples esquerda



0 Simples direi$a

-1 Simples direi$a


10/34

6

3

0

1


6

3

-1

2

40

+

R!$a%&! dupla !m "l#! para a direi$a epai para a esquerda

6

40

0 30

rvore Balanceada 6

41

2

30rvore

R!$a%&! para adirei$a n! "l#! d!n(des+alanead!

R!$a%&! paraa esquerda n!

n(des+alanead


11/34


v!id re+alaneamen$!DirEsq Ap!n$ad!r p/ in$ #


i4 pu-+alaneamen$! ,, -1 **n( "l#! , -1/ sinal di4eren$e r!$a%&!

dupla !m pai para esquerda e "l#! para direi$aAp!n$ad!r pv , pu-Esq3

prin$45r!$aa! dupla direi$a-esquerda !m 6ld7n5/ pv-Re).'#ave3

pu-Esq , pv-Dir3 pv-Dir , pu3

p-Dir , pv-Esq3 pv-Esq , p3

i4 pv-+alaneamen$! ,, 1 p-+alaneamen$! , -13

else p-+alaneamen$! , 03

i4 pv-+alaneamen$! ,, -1 pu-+alaneamen$! , 13

else pu-+alaneamen$! , 03p , pv3

8

p-+alaneamen$! , 03

# , 03

6

3-1

2

40

pu

pv

p


12/34




i4 pu-+alaneamen$! ,, -1 **n( "l#! , -1/ sinal di4eren$e r!$a%&!

dupla !m pai para esquerda e "l#! para direi$aAp!n$ad!r pv , pu-Esq3


pu-Esq , pv-Dir3 pv-Dir , pu3 **esq de pu ap!n$a para null e pu se

$!rna "l#! direi$! de pvp-Dir , pv-Esq3 pv-Esq , p3




else pu-+alaneamen$! , 03

p , pv3

8

p-+alaneamen$! , 03

# , 03

6

40

2

3-1

pv

pu

p

** ( d + l d


13/34




i4 pu-+alaneamen$! ,, -1 **n( "l#! , -1/ sinal di4eren$e r!$a%&! dupla!m pai para esquerda e "l#! para direi$a

Ap!n$ad!r pv , pu-Esq3


pu-Esq , pv-Dir3 pv-Dir , pu3 **esq de pu ap!n$a para null e pu se$!rna "l#! direi$! de pv

p-Dir , pv-Esq3 pv-Esq , p3 **dir de p ap!n$a para null e p se$!rna "l#! esquerd! de pv





8

p-+alaneamen$! , 03

# , 03

} 6

40

2

3-1

pv

pup

** ( d + l d 2


14/34










else p-+alaneamen$! , 03 **a$uali9a :; de p



8

p-+alaneamen$! , 03

# , 03

} 6

40

0

3-1

pv

pup

** ( d + l d 2


15/34












else pu-+alaneamen$! , 03 **a$uali9a :; de pup , pv3

8

p-+alaneamen$! , 03

# , 03} 6

40

0

30

pv

pup

** ( d + l d 2


16/34












else pu-+alaneamen$! , 03 **a$uali9a :; de pup , pv3 **pv a)!ra < p

8


# , 03} 6

40

0

30

p


17/34



n


desbalanceado

Tipo de rotao

2

1 Simples esquerda

0 Simples esquerda



0 Simples direi$a

-1 Simples direi$a


18/34

R!$a%&! dupla !m "l#! para a esquerdae pai para a direi$a

6

5

0

1


+ ! 6

51

-2

0

rvore

6

-1

-2

50

rvore Balanceada

6

0

0

5

0

R!$a%&! para a

esquerda n! "l#!d! n(des+alanead!

R!$a%&! para adirei$a n! n(des+alanead!

** n( des+alanead! 2


19/34

** n( des+alanead! , -2

v!id re+alaneamen$!EsqDir Ap!n$ad!r p/ in$ #

Ap!n$ad!r pu , p-Esq3 **passand! para "l#! d! n( des+alanead!

i4 pu-+alaneamen$! ,, 1 **n( "l#! , 1/ sinal di4eren$e r!$a%&!

dupla !m pai para esquerda e "l#! para direi$aAp!n$ad!r pv , pu-Dir3

prin$45r!$aa! dupla esquerda-direi$a !m 6ld7n5/ pv-Re).'#ave3

pu-Dir , pv-Esq3 pv-Esq , pu3

p-Esq , pv-Dir3 pv-Dir , p3

i4 pv-+alaneamen$! ,, -1 p-+alaneamen$! , 13


i4 pv-+alaneamen$! ,, 1 pu-+alaneamen$! , -13


8

p-+alaneamen$! , 03

# , 03

pu

pv

p 6

51

-2

0

** n( des+alanead! 2


20/34




i4 pu-+alaneamen$! ,, 1 **n( "l#! , 1/ sinal di4eren$e r!$a%&!

dupla !m pai para esquerda e "l#! para direi$aAp!n$ad!r pv , pu-Dir3


pu-Dir , pv-Esq3 pv-Esq , pu3 **direi$a de pu ap!n$a para null e pu

se $!rna "l#! esquerd! de pvp-Esq , pv-Dir3 pv-Dir , p3




else pu-+alaneamen$! , 03

p , pv3

8

p-+alaneamen$! , 03

# , 03

pv

pu

p 6

0

-2

51



21/34




i4 pu-+alaneamen$! ,, 1 **n( "l#! , 1/ sinal di4eren$e r!$a%&! dupla!m pai para esquerda e "l#! para direi$a

Ap!n$ad!r pv , pu-Dir3


pu-Dir , pv-Esq3 pv-Esq , pu3 **direi$a de pu ap!n$a para null e pu se$!rna "l#! esquerd! de pv

p-Esq , pv-Dir3 pv-Dir , p3 **esquerda de p ap!n$a para null e p se$!rna "l#! direi$! de pv





8

p-+alaneamen$! , 03

# , 03

}

pv

pu p 6

0

-2

51



22/34













8

p-+alaneamen$! , 03

# , 03

}

pv

pu p 6

0

0

51



23/34












else pu-+alaneamen$! , 03 **a$uali9a :; de pp , pv3

8

p-+alaneamen$! , 03

# , 03

}

pv

pu p 6

0

0

50



24/34












else pu-+alaneamen$! , 03 **a$uali9a :; de pp , pv3 **pv a)!ra < p

8


# , 03

}

p

6

0

0

50


25/34



n


desbalanceado

Tipo de rotao

2

1 Simples esquerda

0 Simples esquerda


-2 1Dupla !m "l#! paraa esquerda e pai paraa direi$a

0 Simples direi$a

-1 Simples direi$a


26/34

&em"los de alanceamentoR!$a%&! simples direi$a

3

6

0

-1


+ 2 3

6

-1

-2

20

rvoreBalanceada

0

3

60

2

0

R!$a%&! simplespara a direi$a


27/34

'(di)! em '


v!id re+alaneamen$!Dir Ap!n$ad!r p/ in$ #


i4 pu-+alaneamen$! ,, -1 **n( "l#! , -1/ mesm! sinal r!$a%&!

simples a direi$aprin$45r!$aa! a direi$a !m 6ld7n5/ pu-Re).'#ave3

p-Esq , pu-Dir3

pu-Dir , p3


8

p-+alaneamen$! , 03

# , 03

}

pu

p 3

6-1

-2

20


28/34

'(di)! em '






p-Esq , pu-Dir3 **esquerda de p ap!n$a para null

pu-Dir , p3 **p passa a ser "l#! direi$! de pu


8

p-+alaneamen$! , 03

# , 03

}

pu

p 3

6-1

-2

2

0


29/34

'(di)! em '








p-+alaneamen$! , 03 **a$uali9a :; de pp , pu3

8

p-+alaneamen$! , 03

# , 03

}

pu

p 3

6-1

0

2

0


30/34

'(di)! em '








p-+alaneamen$! , 03**a$uali9a :; de p

p , pu3 **pu a)!ra < p

8


# , 03

}

p

3

60

0

2

0


31/34

E=eri! 1

'!nsidere a inser%&! d!s se)uin$es val!resnes$a !rdem em uma >rv!re AVL?@//B/2/C//10/1//F/11. Gara essas inser%Hes

nen#uma r!$a%&! < neess>ria. Desen#e a>rv!re AVL resul$an$e e de$ermine ! 4a$!r de+alaneamen$! de ada n(.


32/34

E=eri! 2

De$erminad! sis$ema arma9ena re)is$r!s p!r#aves numrv!re AVL.Nessa >rv!re s&! inserid!s !s se)uin$es

val!res? 20/10/@/0/2@/2 e 2B nessa!rdem.

Apresen$e pass! a pass! !m! a >rv!re vaisend! !ns$ruda. Reali9e as r!$a%Hesneess>rias e indique qual r!$a%&! 4!ireali9ada em ada as!.


33/34

Res!lvend! ! E=eri! 2

1 Inser%&! das #aves 20 e 10/ nessa !rdem A >rv!re "!u pendend! para a esquerda O 4a$!r de +alaneamen$! d! n( uJa #ave

Documents

Estrutura de dados algoritmos, análise da complexidade e implementações em Java e CC++