Fák Fa definíciója Fa(Tree): csomópontok(nodes) halmaza, amelyeket élek(edges) kötnek össze, és teljesülnek az alábbi feltételek: - létezik egy kitűntetett csomópont: a gyökér (root) - a gyökértől különböző minden más C csomópont egy éllel van összekötve szülőjéhez - a fa összefüggő: bármely nem-gyökér csomóponttól kiindulva a szülőkön keresztül a gyökérhez eljutunk A gráfelmélet alapján fa definíciója: olyan gráf, amelyik - összefüggő - nem tartalmaz kört
Alapfogalmak -
Ha (v,w) ε E, akkor v-t a w szülőjének nevezzük Ha u-ból vezető út w-be, akkor u a w őse, w az u leszármazottja Ha u ≠ w, akkor valódi ős illetve leszármazott Valódi leszármazottal nem rendelkező csomó-pont a fa levele Egy s csomópont az összes leszármazottjával együtt F részfáját alkotja. Ennek gyökere s Erdő: fák együtteséből álló irányított gráf
F=(V,E) U V
W
S
X
Y
Z
Fa jellemzői -
Csomópont mélysége: a gyökértől a hozzá elvezető út hossza Csomópont magassága: annak az innen kiinduló útnak a hossza, amelyik a leghosszabb a levelekig vezető utak közül Fa magassága: a gyökér magassága Csomópont szintje: a fa magassága – csomópont mélysége
Rekurzív adattípusok -
Az adatszerkezet egy része jól leírható egy rekurzív szerkezettel is, ami fizikailag hasonló tárolást, de egészen más algoritmusokat eredményezhet TLista = Struktúra (tartalom, következő) A lista rekurzív értelmezése szerint minden eleme felfogható egy tartalom résszel, és egy másik ( a következő mutató által mutatott elemmel kezdődő) listával rendelkező szerkezetként TFa = Struktúra ( tartalom, fák ) Egy fa egy eleme elképzelhető egy tartalom résszel, és további részfákkal rendelkező struktúrával TBinárisFa = Struktúra (tartalom, balfa, jobbfa) Bináris a hasonló mint egy fa, csak definíció szerint legfeljebb két másik fát tartalmazhat
Bináris Fa eleme -
Bináris fa egy elemének a definíciója: TBinFaElem = Struktúra (tartalom, balgyerek, jobbgyerek) Tartalom (példában: tart): tárolandó adat o Egyszer vagy összetett típus, objektum-referencia Balgyerek, jobbgyerek: a csomópont baloldali illetve jobboldali részfáinak a gyökerére hivatkozik (bal, jobb) A listához hasonlóan a gyerek mezőkben egy kitűntetett érték jelzi, ha hiányzik (példában: ø) Általában egy külső változó tartalmaz egy hivatkozást a fa gyökérelemére (gyökér) A csomóponton belül egyéb mezők is lehetnek, pl. gyakran tároljuk a szülő címét is
Példa bináris fára gyökér
Aritmetikai kifejezés fa: -
*
+
Fenti kifejezés: (x+ (y – 10)) * (6 / z)
/
X
-
6
Y
Levelek: operandusok Csomópontok: operátorok
Z
10
Bináris Keresőfa (BST) -
Rendezett Fa, emiatt pontosítjuk a struktúrát TBSTElem = Struktúra (kulcs, tartalom, balgyerek, jobbgyerek) Kulcs alapján rendezett: a fa minden r csomópontjára igaz, hogy r baloldali részfája legfeljebb r.kulcs nagyságú, r jobboldali részfája pedig legalább r.kulcs nagyságú kulcsokat tartalmaz A rendezés természetesen lehet fordított is A kulcs lehetséges megvalósításai o Különálló kulcs mező o A kulcs a tartalom része o A kulcs a tartalomból számítható érték Megjegyzések: - a későbbiekben a záró ø –eket nem jelöljük, az algoritmusokban azonban számítunk ezekre - Üres fa esetén: gyökér = ø
Példa bináris keresőfára gyökér
30
20
40
10
ø 5
ø
ø
25
ø
15
ø
ø
50
45
ø
ø
60
55
ø ø
ø ø
Bejárás -
Bejárás: az adatszerkezet valamennyi elemének egyszeri elérése (feldolgozása) A láncolt listához hasonlóan a bejárás algoritmusa független a végrehajtandó tevékenységtől, ezért az algoritmuson belül csak utalást teszünk erre Mivel a láncolt listával ellentétben egy elemből több irányban is tovább lehet lépni, többféle bejárás is elképzelhető A csomópontokban található adatok (tartaom, bal, jobb) feldolgozásának sorrendje alapján három fő változat különböztethető meg (ezen belül bal és jobb megcserélhető): o PreOrder bejárás: tartalom, bal, jobb o InOrder bejárás: bal, tartalom, jobb o PostOrder: bal, jobb, tartalom
PreOrder bejárás
PostOrder bejárás
Rekurzió Eljárás PreOrder(p) Ha p≠ø akkor Feldolgozás(p) PreOrder(p.bal) PreOrder(p.jobb) Elágazás Vége Eljárás Vége
Rekurzió Eljárás PostOrder(p) Ha p= ø akkor PostOrder(p.bal) PostOrder(p.jobb) Feldolgozás(p) Elágazás Vége Eljárás Vége
Bejárás indítása PreOrder(gyökér) # teljes fa bejárása
Bejárás indítása PostOrder(gyökér) # teljes fa bejárása
PreOrder(p) # részfa bejárása
PostOrder(p) # részfa bejárása
(Gyakorlati alkalmazás: fa elmentése)
(Gyakorlati alkalmazás: fa felszabadítása)
InOrder bejárás Rekurzió Eljárás InOrder(p) Ha p= ø akkor InOrder(p.bal) Feldolgozás(p) InOrder(p.jobb) Elágazás Vége Eljárás Vége Bejárás indítása InOrder(gyökér) # teljes fa bejárása InOrder(p) # részfa bejárása (Gyakorlati alkalmazás: elemek elérése rendezés szerinti sorrendben, növekvő vagy csökkenő)
Keresés BST-ben -
Alapelv: a fa gyökérelemének kulcsa vagy egyenlő a keresett kulccsal, vagy egyértelműen meghatározza, hogy melyik részfában kell keresést folytatni Ez ugyanúgy igaz a teljes bináris fa gyökérelemére, illetve bármelyik (a keresés során elért) részfájának gyökerére A keresés menete (keresendő kulcs: x) o Bázis § Ha T üres, akkor nincs x benne § Ha T gyökerének cimkéje x, akkor talált o Indukció (legyen T gyökerének kulcsa y) § Ha x < y akkor x-et a bal részfában § Ha x > y akkor a jobb részfában keressük
Keresés algoritmusa Kulcs alapján keresés Függvény Keresés(p, mitkeres) Ha p≠ø akkor Ha p.kulcs = mitkeres akkor Keresés ! p Különben Ha p.kulcs > mitkeres akkor Keresés ! Keresés (p.bal, mitkeres) Különben Keresés ! Keresés(p.jobb, mitkeres) Elágazás Vége Különben Keresés ! ø Elágazás Vége Függvény Vége * átlagos lépésszám (kiegyensúlyozott fában): Ordo(log2n)
Beszúrás BST-be -
-
A beszúrás során az elem beláncolásán kívül ügyelnünk kell a keresőfa tulajdonság fenntartására is Ugyanazok az elemek többféleképpen is elhelyezkedhetnek egy bináris keresőfában, beszúráskor ez alapján több stratégiánk is lehet o Minél kisebb erőforrásigény legyen a beszúrás o Minél kiegyensúlyozottabb legyen a fa a beszúrások után A beszúrás menete (beszúrandó kulcs: x) o Bázis § Ha T üres, akkor új csomópontot készítünk x kulccsal és visszatérünk a csomópont címével § Ha T gyökerének kulcsa x, akkor visszatérünk a csomópont címével o Indukció (legyen T gyökerének kulcsa y) § Ha x < y, akkor x-t bal részfában § Ha x > y, akkor a jobb részfába szúrjuk be
Beszúrás algoritmusa Új elem beszúrása Függvény Beszúrás(címszerin p, újkulcs) Ha p= ø akkor ElemLétrehozás(p) p.kulcs! újkulcs; p.bal ! ø; p.jobb! ø Beszúrás!p Különben Ha p.kulcs > újkulcs akkor Beszúrás!Beszúrás(p.bal, újkulcs) Különben Ha p.kulcs < újkulcs akkor Beszúrás ! Beszúrás(p.jobb, újkulcs) Különben Beszúrás!p Elágazás Vége Elágazás Vége Elágazás Vége Függvény Vége
Törlés BST-ből – 1. lépés -
-
A törlés során az elem kiláncolásán kívül ügyelnünk kell a keresőfa tulajdonság fenntartására is Törlés során az alábbi problémák merülhetnek fel: o Két gyerekkel rendelkező elem mindkét gyerekét nem tudjuk az ő szülőjének egy mutatójára rákapcsolni o Gyökérelem törlése Törlés 1. lépése (beszúrandó kulcs: x) o Bázis § Ha T üres, akkor nincs ilyen elem § Ha T gyökerének kulcsa x, akkor töröljük, majd tovább 2. lépésre: BST tulajdonság visszaállítása § Indukció · Ha x < y akkor x-t a bal részfából · Ha x > y akkor a jobb részfából töröljük
Törlés BST-ből – 2. lépés A) eset: a törlendő csúcspont egy levél, tehét nincsenek gyerek elemei a. Pl töröljük a 70-et 30
30
50
40
35
60
45 42
50
40
70
35
60
45 42
Törlés BST-ből – 2. lépés B) eset: törlendő csúcspontnak csak egy bal vagy csak egy jobb oldali gyereke van a. Pl töröljük a 60-et 30
30
50
40
35
50
60
45
40
70
35
70
45
42
42
Törlés BST-ből – 2. lépés C) eset: a törlendő csúcspontnak bal és jobb oldali gyereke is van a. Pl töröljük a 50-et 30
30
50
40
35
60
45 42
45
40
70
35
60
42
70
Törlés algoritmusa
Eljárás Törlése(címszerint p, törlendő) Ha p=ø akkor “Nincse ilyen elem” Külünben Ha p.kulcs > törlendő akkor Törlés(p.bal, törlendő) Különben Ha p.kulcs < törlendő akkor Törlés(p.jobb, törlendő) Különben Ha p.bal = ø akkor q=p; p!p.jobb; ElemFelszabadítás(q) Különben Ha p.jobb = ø akkor q=p; p!p.bal; ElemFelszabadítás(q) Különben TörlésEset(p, p.bal) Elágazás Vége Elágazás Vége Elágazás Vége Elágazás Vége Elágazás Vége Eljárás Vége Eljárás TörlésEset(p, címszerint r) Ha r.jobb≠ø TörlésEset(p, r.jobb) Különben p.kulcs ! r.kulcs p.tart ! r.tart q!r r ! r.bal ElemFelszabadítás(q) Elágazás Vége ELjárás Vége -
Baloldali részfa legjobboldalibb elemének megkeresése, és ennek tartalmával felülírjuk a törlendő elemet Ezt megtehetjük, hiszen ez Biztosan nagyobb, mint a baloldali elemek és Biztosan kisebb, mint a jobboldali elemek
Miért használjuk A bináris fa előnyei - Rendezett - Ebből adódóan gyors keresés - Relatív gyors elem felvétel - Relatív gyors elem törlés, legrosszabb esetben sincs szükség a fa nagy részének átalakítására - A csomópontok tartalma gyakran egy más adatszerkezet elemére mutat: ideális indexelésre kiegészítő adatszerkezetként A bináris fa hátrányai - bonyolult, lásd bejárások - rekurzióval a műveletek költségesek, illetve maga a rekurzió az OOP nyelvekben gyakran életidegen módon jelenik meg - elemek nem érhetőek el közvetlenül (sőt, maga az indexelés sem egyértelmű, csak a bejárás módjával együtt) - gyors keresés nem garantált, csak kiegyensúlyozott fákban valósul meg - két gyerek címe miatt még nagyobb egy elem helyfoglalása
Probléma felvetése - Vizsgáljuk meg az alábbi kettő, adattartalom szempontjából azonos, de szerkezetileg más fákat keresés szempontjából 50
50 50
40
60 50
35
45
55
65
50 50 50 50
- A jobboldali (elfajult) fa keresési szempontból nem ideális, láncolt listához hasonló lépésszámot igényel
Kiegyensúlyozott fa -
Kiegyensúlyozott fa: legfeljebb egy szintnyi (mélység) eltérés van az egyes (azonos szinten található részfái között) Teljesen kiegyensúlyozott fa: minden csúcsából leágazó bal- és jobboldali részfa csúcsainak száma legfeljebb egyel különbözik egymáshoz képest Teljes fa: Minden csúcsból leágazó bal-és jobboldali részfa csúcsainak száma azonos Célunk: a módosító algoritmusok kiegészítése, hogy minél inkább kiegyensúlyozott (az előző oldalon látható baloldalihoz hasonló) fák építésére törekedjenek Ennek lehetséges megoldásai: beszúrás s törlés után a fa szerkezetét megváltoztatjuk, például forgatással
Forgatás -
Forgatás: olyan lokális művelet, amely megváltoztatja a fa szerkezetét, de megőrzi a rendezettséget Megkülönböztetjük balra- illetve jobbra forgatás műveletét
Eljárás Balra-Forgat(x) y ! x.jobb x.jobb ! y.bal Ha y.bal ≠ ø akkor y.bal.szülő ! x y.szülő ! x.szülő Ha x.szülő = ø akkor gyökér ! y Különben Ha x.szülő.bal = x akkor x.szülő.bal = y Különben x.szülő.jobb = y Elágazás Vége y.bal ! x x.szülő ! y Eljárás Vége
Piros-Fekete Fa -
-
Piros-Fekete fa: Olyan bináris keresőfa, amely rendelkezik az alábbi tulajdonságokkal o Minden csúcs színe piros vagy fekete o Minden levél színe fekete o Minden piros csúcsnak mindkét gyereke fekete o Bármely két, azonos csúcsból kiinduló és levélig vezető úton ugyanannyi fekete csúcs van (fekete magasság) Megvalósítással kapcsolatos megjegyzések: o A BST struktúrát kiegészítjük egy új attribútummal, ami jelzi a színt (értéke vagy piros vagy fekete lehet) o Az egyszerűbb algoritmusok miatt tároljuk a csomópontok szüleit is (a gyökérpontok esetén ezt ø-el jelöljük) o Az egyszerűbb algoritmusok miatt tartalommal külön nem foglalkozunk, feltételezzük, hogy amennyiben a kulcsot átmásoljuk, az mindig a kulccsal együtt “mozog” Megjegyzés: - levélnek a nem ábrázolt ø értékeket tekintjük (ezek kötelezően feketék) - megközelítőleg kiegyensúlyozott: biztosítható, hogy bármely, a gyökértől levélig vezető út hossza nem nagyobb, mint a legrövidebb ilyen út hosszának a kétszerese
25
18
10
40
22
20
24
30
28
32
50
48
60
Piros-Fekete fába beszúrás Eljárás PF-Fába-Beszúrás(x) BinárisFábaBeszúrás(gyökér, x); x.szín ! PIROS Ciklus amíg x ≠ gyökér és x.szülőszülő.szín = PIROS Ha x.szülő = x.szülő.szülő.bal akkor y ! x.szülő.szülő.jobb Ha y≠ø és y.szín = PIROS akkor x.szülő.szín ! FEKETE; y.szín ! FEKETE x.szülő.szülő.szín ! PIROS; x!x.szülő.szülő Különben Ha x=x.szülő.jobb akkor x!x.szülő; Balra-Forgat(x) Elágazás Vége x.szülő.szín ! FEKETE; x.szülő.szülő.szín ! PIROS Jobbra-Forgat(x.szülő.szülő) Elágazás Vége Különben… Ciklus Vége Gyökér.szín ! FEKETE Eljárás Vége
Piros-Fekete fába beszúrás – A eset 11
11
2
14
1
7
15
5
X
2
8
14
1
7
Y
X
15
5
4
8
4
Piros-Fekete fába beszúrás – B eset 11
11
2
14
1
7
5
X
Y
7
15
8
2
14
8
X
1
15
5
4
4
Piros-Fekete fába beszúrás – C eset 11
2
7
14
X
1
7
5
Y
15
8
X
2
1
11
5 8
14
4 14
4
Piros-Fekete Fa további műveletei - Bejárás o Azonos az egyszerű bináris keresőfánál megismerttel o Piros-fekete tulajdonságoknak nincs szerepe - Keresés o Azonos az egyszerű bináris keresőfánál megismerttel o A piros-fekete tulajdonságnak nincs szerepe - Törlés o Alapja az egyszerű bináris keresőfánál megismert törlés o Kiegészítve egy piros-fekete tulajdonságot biztosító karbantartó eljárással o A beszúráshoz hasonlóan ezt átszínezésekkel és forgatásokkal oldja meg o Nem tárgyaljuk B-Fa -
B-Fa: Olyan kiegyensúlyozott keresőfa, amelyet úgy terveztek, hogy hatákonyan lehessen alkalmazni háttértárolón tárolt adatok esetén is Gyakorlati szempontból a futási időt két összetevőre bontjuk fel o Lemezhozzáférések száma o Központi egység műveleteinek száma Napjainkban alkalmazott háttértárolók általában nagyságrendekkel nagyobb sebességet tudnak elérni blokkok írása/olvasása során, mintha ugyanezt az adatmennyiséget elemi adatokként írnánk/olvasnánk A keresés során tehát egy optimalizálási lehetőség, ha a lemezhozzáférések számát blokkonkénti kezeléssel próbáljuk csökkenteni
B-Fa további jellemzői: - Ha ki egy kulcs ci gyökerű részfában, akkor: k1 ≤ kulcs1 ≤ k2 ≤ kulcs2 ≤ … kn ≤ kulcsn ≤ kn+1 - Minden levél mélysége azonos: h (fa magassága) - A csúcsokban található kulcsok darabszáma alulról és felülről is korlátos, ezt egy rögzített t számmal lehet kifejezni (B-fa minimális fokszáma): o Minden nemgyökér csúcsnak legalább t-1 kulcsa van, tehát minden belső csúcsnak legalább t gyereke o Minden csúcsnak legfeljebb 2t-1 kulcsa lehet, tehát minden belső csúcsnak legfeljebb 2t gyereke - A kulcsok darabszámára más módon is adhatunk korlátot, mi mindig ezt a definíciót használjuk (egyes szakirodalmak azonban ettől eltérhetnek)
B-Fa példa N
CFI
AB
DE
DE
QT
GH
JK
OP
RS
WX
B-Fa csúcsának szétvágása (t=4) A szétvágás lépései: 1. Új z csúcs létrehozása 2. Az y utolsó t-1 db kulcsának (és ha van, gyerek mutatójának) átmásolása z-be 3. Az y így maradt legnagyobb kulcsának felvitele x-be 4. A z csúcs legyen x gyereke a 3. pontban felvitt kulcs után Megjegyzés: y telített, x nem telített Speciális eset: gyökér szétvágása X
X A E I U
AIU Y
Y
B C D E F G H
T1
T2
T3
T4
T5
T6
Z B C D
T7
T8
T1
T2
T3
F G H
T4
T5
T6
T7
T8
B-Fába új elem beszúrása -
-
Feladat: x csúcsba egy új K kulcs beszúrása Megkülönböztetett esetek: o x egy levélelem o x egy nem-levélelem o x a gyökérelem és teltett Minden esetben feltételezzük, hogy az x elem nem telített
A) Ha x egy levélelem a. a K kulcs helyének megkeresése az x.kulcsi –k alapján b. ez mögötti x.kulcsi –k hátra léptetése c. a K elhelyezése az üres helyre d. az x.n növelése B) Ha x nem levél a. a K kulcsnak megfelelő gyerek meghatározása az x.kulcsi –k alapján b. az így meghatározott gyerek betöltése x-be c. ha ez a gyerek telített, szétvágás; vágás esetén ha szükséges (a keresést a létrejött új elemben kell folytatni), x aktualizálása d. a beszúrást végző rekurzió folytatása az új csúcson C) Ha x a gyökér és telített a. az x szétvágása egy új gyökérelem létrehozásával b. a beszúrás rekurzió indítása a megfelelő gyerek csúcsban i. A gyökércsúcs kettévágása az egyetlen művelet, amely a B-fa magasságát növeli ii. A bináris keresőfával ellentétben tehát a B-fa a gyökerénél nő, és nem a fa alján iii. Ennek köszönhetően a B-fa mindig kiegyensúlyozott
B-Fába új elem beszúrása 1. AOU
...
BCDEHI
AOU
...
...
.. .
.. .
BCDEFHI
.. .
B-Fába új elem beszúrása 2. AOU
.. .
BCDEFHI
AFOU
.. .
.. .
.
BCDE
.
GHI
.
B-Fába új elem beszúrása 3. E BCD
BCDEFGH
.. .
..
..
..
.. .
.. .
.. .
.. .
FGH
.. .
.. .
.. .
.X
B-Fából elem törlése Egy x kulcsból K kulcs törlése: A) Ha K az x-ben van és x levél, akkor K kulcs törlése x-ből B) Ha K az x-ben van, és x belső csúcs a. Ha van x-nek olyan y gyereke, amelyik tartalmaz egy K-t megelőző kulcsot és legalább t kulcsa van: a K-t közvetlenül megelőző K’ kulcs felhozatala x-be, majd a törlés folytatása K’-re b. Hasonló, mint az a, csak K-t közvetlenül követő kulcsot keressük meg c. Ha a, b, -ben vizsgált mindkét szomszédos gyereknek csak t-1 kulcsa van, akkor egyesítjük a két gyereket és a törlendő K-t egy közös csúcsban, majd rekurzívan folytatjuk a törlést innen (feltételezzük, hogy x kulcsszáma mindig legalább t!) Feltételezzük, hogy x kulcsszáma mindig legalább t, a k-t tartalmazó csúcs keresése során ezt mindig garantálnunk kell a rekurzió újabb meghívása előtt. Lehetőségek: - Ha a következő vizsgálandó y csúcsnak csak t-1 kulcsa van, de valamelyik testvérének t, akkor a testvérből vigyünk fel egy kulcsot a szülőbe, onnan pedig egyet le az y-ba - Ha a következő csúcsnak és testvéreinek is t-1 kulcsuk van, akkor egyesítsük valamelyik testvérével és vigyünk le az így feleslegessé vált kulcsot a szülőből (ha ez a gyökér és az utolsó kulcs, akkor csökken a fa magassága egyel). -
További műveletek: Bejárás, keresés (alapelve hasonló a bináris fáknál megismerttel, kibővítve azzal, hogy egy csúcsnak több tartalma és gyereke lehet ( A fa minden szempontból kiegyensúlyozott, tehét keresés szempontjából hatékony)
Mivel egy csúcs több kulcsot tartalmaz, így kevesebb csúcsbetöltést igényel
