Fa (Tree): csomópontok (nodes) halmaza, amelyeket élek (edges) kötnek össze, és teljesülnek az alábbi feltételek:

Fák [email protected] PPT 2007/2008 tavasz http://nik.bmf.hu/ppt 1

Témakörök 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

2

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 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

3

Alapfogalmak • Ha (v, w) ∈ E, akkor F=(V,E) u v-t a w szülőjének, w-t pedig a v gyerekének nevezzük v s • 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 w x y z 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

4

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 – a csomópont mélysége

5

Rekurzív típusok • 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 6


7

Bináris fa eleme • 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 8

Példa bináris fára • 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)

9

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 – különálló kulcs mező – a kulcs a tartalom része – a kulcs a tartalomból számítható érték

10

Példa bináris keresőfára • Példa bináris keresőfára: gyökér 30 20

40 ∅

10

25 ∅

5 ∅

50 ∅

15 ∅ ∅

45 ∅

∅

60 ∅

∅

55 ∅

∅

• 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 = ∅ 11

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 (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 12

PreOrder 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

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 13

InOrder 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

rekurzió

• Bejárás indítása InOrder(gyökér)


InOrder(p)

részfa bejárása

• Gyakorlati alkalmazás: elemek elérése rendezés szerinti sorrendben (növekvő vagy csökkenő) 14

PostOrder bejárás • 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)


PostOrder(p)

részfa bejárása

• Gyakorlati alkalmazás: fa felszabadítása 15

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 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

16

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): O(log2n) 17


18

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 – 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 19

Beszúrás algoritmusa • Új elem beszúrása 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 20

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 – két gyerekkel rendelkező elem mindkét gyerekét nem tudjuk az ő szülőjének egy mutatójára rákapcsolni – gyökérelem törlése

• Törlés 1. lépése (beszúrandó kulcs: x) – bázis • ha T üres, akkor nincs ilyen elem • ha T gyökerének kulcsa x, akkor töröljük, majd tovább a 2. lépésre: BST tulajdonság visszaállítása – indukció (legyen T gyökerének kulcsa y) • ha xy, akkor a jobb részfából töröljük 21

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 • Pl. töröljük a 70-et 30

30 50

40 35

60 45

42

50 40 70

35

60 45

42

22

Törlés BST-ből – 2. lépés • B) eset: a törlendő csúcspontnak csak egy bal vagy csak egy jobb oldali gyereke van • Pl. töröljük a 60-at 30

30 50

40 35

60 45

42

50 40 70

35

70 45

42

23

Törlés BST-ből – 2. lépés • C) eset: a törlendő csúcspontnak bal és jobb oldali gyereke is van • Pl. töröljük az 50-et 30

30 50

40 35

45 60

45

40 70

35

60 42

70

42

24

Törlés algoritmus Eljárás Törlés(címszerint p, törlendő) Ha p = ∅ akkor „Nincs 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ésCEset(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 25

Törlés algoritmus – folyt. Eljárás TörlésCEset(p, címszerint r) Ha r.jobb ≠ ∅ akkor TörlésCEEset(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 26

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) – 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 27


28

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 40 35

35 40

60 45 55

45 65

50 55 60 65

• A jobboldali (elfajult) fa keresési szempontból nem ideális, láncolt listához hasonló lépésszámot igényel 29

Kiegyensúlyozottság • 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ó bal oldalihoz hasonló) fák építésére törekedjenek • Ennek egy lehetséges megoldása, ha a beszúrás és törlés után a fa szerkezetét megváltoztatjuk, például forgatásokkal 30

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öztetünk balra- illetve jobbra forgatás műveletet 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 31

Piros-fekete fa • Piros-fekete fa: Olyan bináris keresőfa, amely rendelkezik az alábbi tulajdonságokkal: – – – –

minden csúcs színe piros vagy fekete minden levél színe fekete minden piros csúcsnak mindkét gyereke fekete 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: – a BST struktúrát kiegészítjük egy új attribútummal, ami jelzi a színt (értéke csak piros vagy fekete lehet) – az egyszerűbb algoritmusok miatt tároljuk a csomópontok szüleit is (a gyökérpont esetén ezt ∅-el jelöljük) – az egyszerűbb algoritmusok miatt a tartalommal külön nem foglalkozunk, feltételezzük, hogy amennyiben a kulcsot átmásoljuk, az mindig a kulccsal együtt „mozog” 32

Piros-fekete fa példa • Piros-fekete fa 25 18

40

10

22 20

30 24

28

50 32

48

60

• 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 33

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í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

A

B C

34

Piros-fekete fába beszúrás – A eset 11 2

14

1

7

y

5

x

15

8

4 11 2

14 x

1

7 5 4

15 8 35

Piros-fekete fába beszúrás – B eset 11 2

y 14

x 1

7 5

15 8

4 11 7

14

x 2 1

8

15

5 4 36

Piros-fekete fába beszúrás – C eset 11

y

7

14

x 2

8

1

15

5 4 7

x 2 1

11 5

4

8

14 15 37

Piros-fekete fa további műveletei • Bejárás – azonos az egyszerű bináris keresőfánál megismerttel – a piros-fekete tulajdonságnak nincs szerepe

• Keresés – azonos az egyszerű bináris keresőfánál megismerttel – a piros-fekete tulajdonságnak nincs szerepe

• Törlés – alapja az egyszerű bináris keresőfánál megismert törlés, – kiegészítve egy piros-fekete tulajdonságot biztosító karbantartó eljárással – a beszúráshoz hasonlóan ezt átszínezésekkel és forgatásokkal oldja meg – nem tárgyaljuk

38


39

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 – 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 40

B-fa egy csúcsának felépítése • 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 41

B-fa további jellemzői • 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) 42

B-fa példa 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 43

B-fa csúcsának szétvágása • B-fa csúcsának szétvágása (t = 4) x

A I U

y

y = x.ci

B C D E F G H T1 T2 T3 T4 T5 T6 T7 T8 x

y = x.ci z = x.ci+1

A E I U z

y

B C D

F G H

T1 T2 T3 T4

T5 T6 T7 T8

44

B-fa csúcsának szétvágása • A szétvágás lépései – Új z csúcs létrehozása – Az y utolsó t-1 db kulcsának (és ha van, gyerek mutatójának) átmásolása z-be – Az y így maradt legnagyobb kulcsának felvitele x-be – 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

45

B-fába új elem beszúrása • •

Feladat: x csúcsba egy új K kulcs beszúrása Megkülönböztetett esetek – 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.kulcsi-k alapján 2. ez mögötti x.kulcsi-k hátra léptetése 3. a K elhelyezése az üres helyre 4. az x.n növelése 46

A) x egy levélelem • 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

...

...

47

B-fába új elem beszúrása 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 x-be 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

48

B) x nem levélelem • 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

...

...

49

B-fába új elem beszúrása 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

50

C) x a gyökér és telített • Példa: X beszúrása (t = 4)

B C D E F G H ..

..

..

..

..

..

..

..

..

..X

E B C D ..

..

..

..

F G H ..

..

51

B-fából elem törlése • Feladat: egy x csúcsból K kulcs törlése • Ha K az x-ben van és x egy levélelem, akkor K kulcs törlése x-ből • Ha K az x-ben van és x belső csúcs – i) eset: 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’ kulcsra – ii) eset: hasonló mint i) csak a K-t közvetlenül követő kulcsot keressük meg – iii) eset: ha az i) és ii)-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

• Minden esetben feltételezzük, hogy x kulcsszáma mindig legalább t! 52

Feltétel biztosítása • Feltételeztük, hogy x kulcsszáma mindig legalább t, a K kulcsot tartalmazó csúcs keresése során ezt mindig garantálnunk kell a rekurzió újabb meghívása előtt • Ennek lehetőségei – 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)

53

B-fa további műveletei • Bejárás – 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

• 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, így csúcsokon belül is egy ciklust kell indítani

• Keresés hatékony, mivel – 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

54

Javasolt/felhasznált irodalom • Cormen, Leiserson, Rivest: Algoritmusok Műszaki Könyvkiadó, 1997 • Pap, Szlávi, Zsakó: µlógia27 – Rekurzív típusok ELTE TTK, 1994

55

Fa (Tree): csomópontok (nodes) halmaza, amelyeket élek (edges) kötnek össze, és teljesülnek az alábbi feltételek:

Recommend Documents