A kurzus teljesítésének feltételei Évközi teljesítés • Két gyakorlaton megírt ZH, az elérhet˝o 100 pontból 50 pontot kell elérni. • Aki nem teljesíti a feltételt a vizsgaid˝oszak els˝o hetében a vizsgára engedésért írhat dolgozatot. • Az I404 kódú kurzus teljesítéséhez meg kell oldani egy otthoni feladatot, határid˝o április 30. Vizsga • Kiskérdések, amelyekb˝ol 63 pontot lehet szerezni, a minimumkövetelmény 35. • Egy tétel 37 pont, minimumkövetelmény nincs. Érdemjegy • 175-200 jeles • 150-174 jó • 125-149 közepes • 100-124 elégséges • 0-99 elégtelen Oktatási segédanyag • El˝oadás anyag www.inf.u-szeged.hu/∼cimreh/algo2.htm • Régebbi el˝oadások anyaga: /pub/alg/II • T. H. Cormen, C. E. Leiserson, R.L. Rivest: Algoritmusok, M˝uszaki Könyvkiadó, 2003. • T. H. Cormen, C. E. Leiserson, R.L. Rivest, C. Stein: Új algoritmusok, Scolar Informatika Könyvkiadó, 2003 Bináris keres˝ofák Az F = (M,R,Adat) absztrakt adatszerkezetet bináris keres˝ofának nevezzük, ha • F bináris fa, R = {bal, jobb, apa}, bal, jobb, apa : M → M, • Adat : M → Elemtip és Elemtip-on értelmezett egy ≤ lineáris rendezési reláció, • (∀x ∈ M)(∀p ∈ Fbal(x) )(∀q ∈ Fjobb(x) )(kulcs(p) ≤ kulcs(x) ≤ kulcs(q)) KERES2(F,k) while(F!=Nil or k!=kulcs(F)) if k
Futási id˝o: A fa magasságával arányos. Piros fekete fák A piros-fekete fa olyan bináris keres˝ofa, amelynek minden pont egy extra bit információt tartalmaz, ez a pont színe, amelynek értékei: PIROS vagy FEKETE. Tehát a fa minden pontja tartalmazza a szín, kulcs, bal, jobb és apa mez˝oket. Ha egy ponthoz tartozó fiú vagy apa nem létezik, akkor a megfelel˝o mez˝o a NIL értéket tartalmazza. Úgy tekintjük, hogy az ilyen NIL mutató értékek a bináris keres˝ofa küls˝o (levél) pontjaira mutatnak, míg a fa kulcsot tartalmazó pontjai a bels˝o pontok. Megvalósítás során ezeket a küls˝o pontokat egyetlen o˝ rszem ponttal ábrázoljuk, amelyet NIL[F] jelöl. A piros-fekete fák azok, amelyekre teljesülnek a következ˝o tulajdonságok: 1. Minden pont színe vagy PIROS vagy FEKETE. 2. A gyökérpont színe FEKETE. 3. Minden levél (a NIL pontokat tekintjük levélnek) színe FEKETE. 4. Minden piros pontnak mindkét fia fekete. 5. Bármely pontból bármely levélig vezet˝o úton ugyanannyi fekete pont van. Piros fekete fák magassága Egy x pont fekete-magasságának nevezzük az x pontból induló, levélig vezet˝o úton található, x-en kívüli fekete pontok számát, és fm(x)-szel jelöljük ezt az értéket. Az 5. tulajdonság miatt a fekete-magasság jól definiált, mivel minden ilyen út azonos számú fekete pontot tartalmaz. Egy piros-fekete fa fekete-magasságát a fa gyökérpontjának fekete-magasságaként definiáljuk. A piros fekete fákra teljesül a következ˝o állítás. Tétel Bármely n bels˝o pontot tartalmazó piros-fekete fa magassága legfeljebb 2 log(n + 1). Biz Teljes indukcióval igazolható, hogy a fa minden x gyöker˝u részfája legalább 2 f m(x) − 1 bels˝o pontot tartalmaz. Ha x magassága 0, akkor x levél (nil), tehát az x gyöker˝u részfának valóban 0 bels˝o pontja van. Tegyük fel, hogy x magassága pozitív, és két fia van. Mindkét fiú fekete-magassága vagy fm(x), vagy fm(x)-1 attól függ˝oen, hogy a színe piros vagy fekete. Mivel x fiainak magassága kisebb, mint x magassága, így az indukciós feltevés alapján mindkét részfa legalább 2 f m(x)−1 − 1 bels˝o pontot tartalmaz. Tehát az x gyöker˝u részfa bels˝o pontjainak száma legalább (2 f m(x)−1 − 1) + (2 f m(x)−1 − 1) + 1 = 2 f m(x) − 1. Legyen x magassága h. A 4. tulajdonság szerint minden a gyökért˝ol levélig haladó út, legalább feleannyi fekete pontot tartalmaz, mint ezen út pontjainak száma, nem számítva a gyökeret. Tehát a gyökér feketemagassága legalább h/2, így n ≥ 2h/2 − 1. Tehát azt kapjuk, hogy log(n + 1) ≥ h/2, azaz h ≤ 2 log(n + 1). Következésképpen a keres˝ofa m˝uveletek id˝oigénye O(log n), ahol n a pontok száma. Azt kell megvizsgálni a piros fekete fa tulajdonságainak karbantartásának mekkora az id˝oigénye. Beszúrás piros fekete fába A fába a keres˝ofa BESZUR m˝uveletének megfelel˝oen beszúrjuk az új pontot, a színét pirosra állítjuk, a gyermekeit Nil-re és feketére. Amennyiben az új pont apja is piros, akkor a beszúrást követ˝oen sérül a 4-es tulajdonság és ezt helyre kell állítanunk. PF-Beszur(F,z) y:=Nil[F] x:=F while(x!=Nil[F]) y:=x 2
if kulcs(z)
Y X c
a
b
X
Y
a
b
c
Balra, jobbra forgatás
1. ábra.
JobbraForgat(F,apa(apa(z))) else ugyanaz, mint a then ág, csak bal és jobb felcserélve szin(F):=FEKETE Törlés piros fekete fából A fából a keres˝ofa Töröl m˝uveletének megfelel˝oen töröljük az adott pontot. Ha a pont piros akkor nincs más teend˝o, egyébként sérül az 5. tulajdonság és ezt helyre kell állítani. Ezt úgy oldjuk meg, hogy a ténylegesen törölt pont fia, kap egy extra fekete értéket, és duplán fekete lesz, majd forgatásokkal és átzsínezéssel ezt megszüntetjük. PFFabolTorol(F,z) If bal(z)=Nil(F) or jobb(z)=Nil(F) then y:=z else y:=FabanKovetkezo(z) If bal(y)!=Nil(F) then x:=bal(y) else x:=jobb(y) apa(x):=apa(y) If apa(y)=Nil(F) then F:=x else if y=bal(apa(y)) then bal(apa(y)):=x else jobb(apa(y)):=x If y!=z 4
CF BP
DP
AP
a
b
d
e
c
CP BF
DF
AP
a
b
d
e
c
B1eset, nagybácsi piros
2. ábra.
then kulcs(z):=kulcs(y) If szín(y)=FEKETE then PFTorolJavit(F,x) PFTorolJavit(F,x) while x!=F and szín(x)=FEKETE if x=bal(apa(x)) then w:=jobb(apa(x)) if szín(w)=PIROS /1. eset then szín(w):=FEKETE szín(apa(x)):=PIROS BalraForgat(F,apa(x)) w:=jobb(apa(x)) if szín(bal(w))=FEKETE and szín(jobb(w))=FEKETE /2. eset then szín(w)=PIROS x:=apa(x) else if szín(jobb(w))=FEKETE /3. eset then szín(bal(w))=FEKETE szín(w):=PIROS JobbraForgat(F,w) w:=jobb(apa(x)) szín(w):=szín(apa(x)) /4. eset szín(apa(x)):=FEKETE 5
CF BP d
AP
a
b
c
CF AP d
B
P
c
a
b
B2. eset
3. ábra.
szín(jobb(x)):=FEKETE BalraForgat(F,apa(x)) x:=F else ugyanaz, mint a then ág, csak bal és jobb felcserélve szín(x):=FEKETE Helyreállítások id˝oigénye Beszúrásnál a while ciklusmag csak az 1. esetben ismétel, így az id˝oigény O(log n). A törlésnél is csak a 2. esetben kerül feljebb a dupla fekete értéket tartalmazó csúcs, a többi eset legfeljebb három forgatás után helyreállítja a tulajdonságot, így a m˝uveletigény O(log n). Bemutató mintaprogramok http://people.ksp.sk/~kuko/bak/index.html http://gauss.ececs.uc.edu/RedBlack/redblack.html http://www.ece.uc.edu/~franco/C321/html/RedBlack/rb.orig.html Alapvet˝o részek • Piros fekete fa definíciója • Beszúrás PF fába 6
CF BP d
AP
a
c
b
BF AP
a
CP
b
c
d
B3. eset
4. ábra.
• PFBeszurJavit • Törlés PF fából • PFTorolJavit
7
BF x
w
AF
DP
CF
b
a
c
EF
d
e
f
DF BP
EF
x
w
AF
a
b
CF
c
e
f
d
T1.eset
5. ábra.
8
B? x
w
AF
DF
CF
b
a
c
B?
EF
d
f
x
AF
a
e
DP
EF
CF
b
c
d
f
e
T2. eset
6. ábra.
9
B? x
w
AF
DF
CP
b
a
c
EF
d
e
f
B? x
w
AF
a
CF
b
DP
c
EF
d
e
T3. eset
7. ábra.
10
f
B? x
w
AF
DF
C?
b
a
c
EP
d
e
f
D? BF
EF
C?
AF
a
b
c
e
f
d
T4. eset
8. ábra.
11
