2009.04.06.
Fák
[email protected] PPT 2007/2008 tavasz http://nik.bmf.hu/ppt
1
Rekurzív típusok, fa adatszerkezet Bináris keresőfa, bejárások Bináris keresőfa, módosítás B-fa
Témakörök 2
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 a 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
Gráfelmélet alapján fa definíciója: olyan gráf, amelyik ◦ összefüggő, ◦ nem tartalmaz kört
Fa definíciója 3
1
2009.04.06.
Ha (v, w) E, akkor v-t a w szülőjének, w-t pedig a v gyerekének nevezzük v 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 w 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
u
F=(V,E) s
x
y
z
Alapfogalmak
4
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 – a csomópont mélysége
Fa jellemzői
5
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
Kiegyensúlyozottság
6
2
2009.04.06.
Az adatszerkezetek 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 fa hasonló mint egy fa, csak definíció szerint legfeljebb két másik fát tartalmazhat
Rekurzív típusok
7
Rekurzív típusok, fa adatszerkezet Bináris keresőfa, bejárások Bináris keresőfa, módosítás B-fa
Témakörök 8
Bináris fa egy elemének a definíciója: TBinFaElem = Struktúra(tartalom, balgyerek, jobbgyerek) Tartalom (példákban tart): a tárolandó adat ◦ egyszerű típus ◦ ö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ákban ) Á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
Bináris fa eleme
9
3
2009.04.06.
Példa bináris fára: gyökér * /
+ x
y
6
z
10
Aritmetikai kifejezés fa: ◦ Levelek: operandusok ◦ Csomópontok: operátorok ◦ Fenti kifejezés: (x + (y – 10)) * (6 / z)
Példa bináris fára
10
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 ◦ különálló kulcs mező ◦ a kulcs a tartalom része ◦ a kulcs a tartalomból számítható érték
Bináris keresőfa (BST) 11
Példa bináris keresőfára: gyökér 30 20 10 5
40 25
15
Megjegyzések:
50 45
60 55
◦ 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
12
4
2009.04.06.
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 (tartalom, bal, jobb) feldolgozásának sorrendje alapján három fő változat különböztethető meg (ezen belül a bal és jobb megcserélhető): ◦ PreOrder: tartalom, bal, jobb ◦ InOrder bejárás: bal, tartalom, jobb ◦ PostOrder: bal, jobb, tartalom
Bejárás
PreOrder bejárás algoritmusa 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
13
rekurzió
Bejárás indítása PreOrder(gyökér)
teljes fa bejárása
PreOrder(p)
részfa bejárása
Gyakorlati alkalmazás: fa elmentése
PreOrder bejárás
InOrder bejárás algoritmusa 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
14
Bejárás indítása
rekurzió
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ő)
InOrder bejárás
15
5
2009.04.06.
PostOrder bejárás algoritmusa 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
rekurzió
Bejárás indítása PostOrder(gyökér)
teljes fa bejárása
PostOrder(p)
részfa bejárása
Gyakorlati alkalmazás: fa felszabadítása
PostOrder bejárás
16
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 a 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) ◦ bázis ha T üres, akkor x nincs benne ha T gyökerének címkéje x, akkor talált
◦ 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 BST-ben
17
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
Keresés algoritmusa
18
6
2009.04.06.
Rekurzív típusok, fa adatszerkezet Bináris keresőfa, bejárások Bináris keresőfa, módosítás B-fa
Témakörök 19
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 ◦ minél kisebb erőforrásigényű legyen a beszúrás ◦ minél kiegyensúlyozottabb legyen a fa a beszúrás(ok) után
A beszúrás menete (beszúrandó kulcs: x) ◦ 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
◦ indukció (legyen T gyökerének kulcsa y)
ha x < y, akkor x-t a bal részfába, ha x > y, akkor a jobb részfába szúrjuk be
Beszúrás BST-be
20
Függvény Beszúrás(címszerint 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
Beszúrás algoritmusa
21
7
2009.04.06.
A bináris fa előnyei
A bináris fa hátrányai
◦ ◦ ◦ ◦
rendezett ebből adódóan gyors keresés relatíve gyors elem felvétel relatíve 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 ◦ 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) ◦ a gyors keresés nem garantált, csak kiegyensúlyozott fákban valósul meg ◦ a két gyerek címe miatt még nagyobb egy elem helyfoglalása
Miért használjuk?
22
Rekurzív típusok, fa adatszerkezet Bináris keresőfa, bejárások Bináris keresőfa, módosítás Piros-fekete fa B-fa
Témakörök 23
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 ◦ lemezhozzáférések száma ◦ 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ák/olvasnák 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
24
8
2009.04.06.
n a csúcsban tárolt kulcsok darabszáma (rá vonatkozó korlátokat lásd következő oldalon) levél logikai érték, ami mutatja, hogy levélről vagy belső csúcsról van szó kulcs1 kulcs2 ... kulcsn a csúcsban tárolt kulcsok c1 c2 ... cn+1 a csúcs gyerekeinek (részfáinak) címei tartalom tetszőleges típusú tartalom, a példákban mindig feltételezzük, hogy a kulcsokkal együtt mozog
B-fa egy csúcsának felépítése
25
Ha ki egy kulcs a 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): ◦ minden nemgyökér csúcsnak legalább t-1 kulcsa van, tehát minden belső csúcsnak legalább t gyereke ◦ 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 további jellemzői
26
gyökér
N C F I
A B
D E
G H
Q T
J K
O P
R S
W X
A példában t = 3, tehát a gyökércsúcs kivételével a csúcsokban található kulcsok száma ◦ minimum 2 ◦ maximum 5
B-fa példa
27
9
2009.04.06.
x y
y = x.ci
t=4
A I U
B C D E F G H T1 T2 T3 T4 T5 T6 T7 T8 x
y = x.ci z = x.ci+1
y
A E I U
B C D
F G H
T1 T2 T3 T4
T5 T6 T7 T8
z
B-fa csúcsának szétvágása
28
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 A vágáshoz szükség van egy hivatkozásra az elem szülőjére. Ezt vagy minden elemben eltároljuk, vagy az algoritmusnak kell nyilvántartania Speciális eset: gyökér szétvágása
◦ lépések hasonlóak a fentihez ◦ ezt követően a gyökér elem az újonnan létrehozott elem lesz
B-fa csúcsának szétvágása
Feladat: x csúcsba egy új K kulcs beszúrása Megkülönböztetett esetek ◦ ◦ ◦
29
x egy levélelem x nem levélelem x a gyökérelem és telített
Első két esetben feltételezzük, hogy az x elem nem telített!
A) Ha x egy levélelem 1. a K kulcs helyének megkeresése az x.kulcsik alapján 2. e mögötti x.kulcsi-k hátraléptetése 3. a K elhelyezése az üres helyre 4. az x.n növelése
B-fába új elem beszúrása
30
10
2009.04.06.
Példa: F beszúrása (t = 4) A O U ...
B C D E H I
...
...
A O U
...
B C D E F H I
...
...
A) x egy levélelem
31
B) Ha x nem levélelem 1. a K kulcsnak megfelelő gyerek meghatározása az x.kulcsi-k alapján 2. az így meghatározott gyerek betöltése xbe 3. 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 4. a beszúrást végző rekurzió folytatása az új csúcson
B-fába új elem beszúrása
32
Példa: G beszúrása (t = 4) A O U ...
B C D E F H I
...
...
A F O U ...
B C D E
G H I
B) x nem levélelem
...
... 33
11
2009.04.06.
C) Ha x a gyökér és telített: 1. az x szétvágása egy új gyökérelem létrehozásával 2. a beszúrás rekurzió indítása a megfelelő gyerek csúcsban A gyökércsúcs kettévágása az egyetlen művelet, amely a B-fa magasságát növeli 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 Ennek köszönhetően a B-fa mindig kiegyensúlyozott
B-fába új elem beszúrása
34
Példa: X beszúrása (t = 4) B C D E F G H ..
..
..
..
..
..
..
..
..
..X
E B C D ..
..
..
..
F G H ..
..
C) x a gyökér és telített
Törlés Bejárás
Keresés
Keresés hatékony, mivel
35
◦ alapelve hasonló a bináris fáknál megismerttel, ◦ kibővítve azzal, hogy egy csúcsnak több tartalma és gyereke lehet, így csúcsokon belül is egy ciklust kell indítani ◦ alapelve hasonló a bináris fáknál megismerttel, ◦ kibővítve azzal, hogy egy csúcsnak több tartalma és gyereke lehet, így csúcsokon belül is egy ciklust kell indítani ◦ a fa mindig kiegyensúlyozott, így biztosítható az ideális keresési lépésszám ◦ mivel egy csúcs több kulcsot tartalmaz, így kevesebb csúcsbetöltést igényel, ezzel kevesebb háttértár műveletet
B-fa további műveletei
36
12
2009.04.06.
Cormen, Leiserson, Rivest: Algoritmusok Műszaki Könyvkiadó, 1997
Pap, Szlávi, Zsakó: μlógia27 – Rekurzív típusok ELTE TTK, 1994
Javasolt/felhasznált irodalom 37
13
