Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|AlgElKeresofaOsszefoglalo}} vissza: AlgElDefiniciok ---- ==Bináris fák== * '''Tárolási szerkezet, tulajdonságok:''' ** Bináris f…”

2012-10-21T19:52:11Z

Új oldal, tartalma: „{{GlobalTemplate|Infoalap|AlgElKeresofaOsszefoglalo}} vissza: AlgElDefiniciok ---- ==Bináris fák== * '''Tárolási szerkezet, tulajdonságok:''' ** Bináris f…”

Új lap

{{GlobalTemplate|Infoalap|AlgElKeresofaOsszefoglalo}}

vissza: [[AlgElDefiniciok]]

----

==Bináris fák==
* '''Tárolási szerkezet, tulajdonságok:'''
** Bináris fa
*** Egy csúcs jellemzői:
**** elem(x): a csúcsban tárolt informásió
**** bal(x), jobb(x): mutató az x csúcs bal/jobb fiára
**** (_apa(x)_: _mutató az x csúcs apjára_)
**** (_s(X)_: _x gyökerű részfa csúcsainak száma_)
*** A bejárások (preorder, inorder, postorder) O(n) azaz lineáris időben megvalósíthatók
** Keresőfa-tulajdonság: Tetszőleges x csúcsra igaz, hogy: (y az x csúcs bal, z a jobb részfájának tetszőleges csúcsa)
*** elem(y) ≤ elem(x)
*** elem(x) ≤ elem(z)
** Feltételezzük, hogy nincsenek ismétlődő elemek (belátható, hogy ez nem jelent lényegi változást, kisebb módosításokkal működnének az eljárások ismétlődő elemekkel is)

* '''Műveletek megvalósítása és költsége:''' (__S__ ''az x gyökerű fa,'' '''''s__ ''a keresett/törlendő/beszúrandó elem,'' __l''''' ''a fa szintjeinek száma,'' __n__ _a fában tárolt elemek száma_)
$ *KERES(s, S)*: Első lépésben összehasonlítjuk a gyökérrel a keresett elemet, ha nem egyezik akkor tovább keresünk az összehasonlítás eredményének függvényében a bal (s < x) vagy jobb (s > x) részfában, amennyiben nincs ilyen fia x-nek megállapíthatjuk, hogy s nincs a fában; költség: O(l)
$ *BESZÚR(s, S)*: Egy KERES(s, S) hívással kezdünk, ha találunk s elemet akkor nincs dolgunk, ellenkező esetben azért állunk meg mert nincs az aktuális csúcsnak olyan fia amerre tovább szeretnénk lépni, tehát annyi a dolgunk, hogy létrehozzuk ezt a megfelelő fiút és s értéket adunk neki; költség: O(l)
$ *TÖRÖL(s, S)*: Egy KERES(s, S) hívással kezdünk, ha s nincs a fában akkor nincs tennivalónk, egyébként pedig két lehetőségünk van (__x__ ''itt az a csúcs amiben'' __s__ _található_):
### s-nek legfeljebb egy fia van: (könnyű törlés) ekkor x-et helyettesítjük a fiával
### s-nek két fia van: megkeressük y=MAX(bal(x))-et majd az ebben lévő s' elemet tesszük X-be és végül töröljük y csúcsot ami már egy könnyű törlés; költség: O(l)
$ *MIN(S), MAX(S)*: Az elsőnél balra megyünk amíg lehetséges, utóbbinál jobbra; költség: O(l)
$ *TÓLIG(a, b, S)*: S fa a és b közé eső elemeit adja vissza. Első lépésben végrehajtunk egy KERES(a, S)-t majd inorder bejárás szerint lépkedünk amíg az első b-nél nagyobb elemig el nem jutunk; költség: O(n) vagy inorder mutatókkal O(l+k) (__k__ ''az'' '''''a__ ''és'' __b''''' _közti elemek száma_)

==2-3 fák==
* '''Tárolási szerkezet, tulajdonságok:'''
** 2-3 fa
### A tárolni kívánt rekordok a levelekben helyezkednek el (egy levél egy rekord) a kulcs szerint rendezve balról jobbra növekvő sorrendben
### A belső (nem levél) csúcsoknak 2 vagy 3 fia van, ennek megfelelően 1 vagy 2 kulcsot tartalmaznak tehát kétféle lehet egy belső csúcs:
|<math>m_{1}</math>||<math>s_{1}</math>||<math>m_{2}</math>||<math>s_{2}</math>||<math>m_{3}</math>
|}
vagy
|<math>m_{1}</math>||<math>s_{1}</math>||<math>m_{2}</math>
|}
**** <math>s_{1}, s_{2}</math> a csúcsban lévő kulcsok, melyekre teljesül hogy <math>s_{1} < s_{2}</math>
**** <math>m_{1}, m_{2}, m_{3}</math> pedig mutatók a csúcs részfáira, amikre igaz, hogy:
##### <math> MAX(m_{1}) < s_{1}</math>
##### <math> MIN(m_{2}) = s_{1}</math> és <math>MAX(m_{2}) < s_{2}</math>
##### <math> MIN(m_{3}) = s_{2}</math>
### A fa levelei a gyökértől egyforma távolságra vannak
** l szintű 2-3 fa esetén a levelek száma legalább <math>2^{l-1}</math> vagyis l ≤ <math>\log_{2}n + 1</math>

* '''Műveletek megvalósítása és költsége:''' (__S__ ''az x gyökerű fa,'' '''''s__ ''a keresett/törlendő/beszúrandó elem,'' __l''''' ''a fa szintjeinek száma,'' __n__ _a fában tárolt rekordok száma_)
$ *KERES(s, S)*: A bináris keresőfához hasonlóan keresünk itt is. Első lépésben összehasonlítjuk a gyökérben tárolt <math>s_{1}</math> és esetleg <math>s_{2}</math> kulcsokkal a keresett elemet, ez alapján el tudjuk dönteni, hogy melyik részfában kerressük tovább az s-t:
### <math>s < s_{1}</math> akkor az <math>m_{1}</math> által mutatott részfában keresünk tovább
### <math>s_{1} \leq s < s_{2}</math> akkor az <math>m_{2}</math>-t követjük
### <math>s_{2} \leq s</math> akkor az <math>m_{3}</math> részfában lesz a keresett elem
ezután egy szintel lentebb folytatjuk ugyanígy a keresést; költség: O(log n)
$ *BESZÚR(s, S)*: x most jelölje a legalsó nem levél csúcsot a keresőút mentén. x kétféle lehet:
### 2 fia van: ebben az esetben a beszúrás viszonylag egyszerű csak x-et kell ügyesen modosítani (TK: 66. old.)
### 3 fia van: ekkor egy csúcsvágás nevű műveletet hajtunk végre ami abból áll, hogy az x csúcsot 2 részre szedjük beillesztve s-t és az újonnan keletkező y csúcsot beszúrjuk x apjába (a beszúrandó kulcs a két régi és az új s kulcs közül a nagyság szerinti középső) ugyanezzel a módszerrel, emiatt a csúcsvágások sora eltarthat egészen a gyökérig, ha a gyökérnek is 3 fia van akkor a gyökeret is 2 csúcsra bontjuk és ezek fölé egy új gyökeret hozunk létre ezáltal a fa szintjeinek száma eggyel nő tehát nem sérül a 3. követelmény sem; költség: O(log n)
$ *TÖRÖL(s, S)*: x most is a legalsó nem levél csúcsot jelképezi a keresőút mentén. x kétféle lehet:
### 3 fia van: ebben az esetben a törlés viszonylag egyszerű csak x-et kell ügyesen modosítani (TK: 67. old.)
### 2 fia van: ekkor még két lehetőségünk van
#### x egyik szomszédjának 3 fia van: ekkor átrakhatunk onnan x-be egyet és máris az első esetnek megfelelő helyzet áll elő (de módosítani kell x szomszédját és x apját is)
#### x egyik szomszédjának sincs 3 fia: ilyen esetben kell alkalmazni a csúcsösszevonást ami a csúcsvágás fordítottja azaz x csúcsot és szomszédját egyetlen csúcsban egyesítjük és töröljük x apjából az egyik feleslegessé vált mutatót a most használt módszerrel,tehát újra eljuthatunk a gyökérig csúcsösszevonásokkal. Akkor van gond, ha gyökérben is csak két (pl <math>m_{1}</math>, <math>m_{2}</math>) mutató van, ilyenkor az egyik mutató (mondjuk <math>m_{2}</math>) törlendő és csak <math>m_{1}</math> mutat egy valódi részfa gyökerére, tehát mostantól vehetjuk az <math>m_{1}</math> által mutatott részfa gyökerét a S fa gyökerének. Most is a gyökérben ment végbe a változás, tehát nem sérült mostsem egyik kikötés sem; költség: O(log n)
$ *MIN(S), MAX(S)*: megegyezik a bináris keresőfánál ismertetettel; költség: O(log n)
$ *TÓLIG(a, b, S)*: szintén megegyezik a bináris keresőfánál ismertetettel; költség: O(logn + k) ha a leveleket láncoljuk növekvő sorrendben

==B-fák==
* '''Tárolási szerkezet, tulajdonságok:'''
** 2-3 fa természetes általánosítása
** m-edrendű B-fa (röviden <math>B_{m}</math>-fa) tulajdonságai:
### A gyökér foka legalább 2, kivéve ha csak max 2 szintes a fa
### Minden más belső csúcsnak min <math>\lceil\frac{m}{2}\rceil</math> fia van
### A levelek a gyökértől egyforma távolságra vannak
### Egy csúcsnak legfeljebb m mutatója lehet<br>
Tehát egy csúcs így néz ki: (<math>\lceil\frac{m}{2}\rceil - 1 \leq i \leq m - 1</math>)
|<math>m_{0}</math>||<math>s_{1}</math>||<math>m_{1}</math>||<math>s_{2}</math>||<math>m_{2}</math>||...||<math>s_{i}</math>||<math>m_{i}</math>
|}
** l szintű, n levelű <math>B_{m}</math>-fa fa esetén: <math>l\leq\frac{\log_{2}{n}-1}{\log_{2}{\lceil\frac{m}{2}\rceil}}+2</math>
* '''Műveletek megvalósítása és költsége:'''
A 2-3-fa műveleteinek általánosításaiból nyerhető. költségük a TÓLIG kivételével arányos a szintek számával
==AVL fák==
===Megjegyzések kiegyensúlyozott fákhoz===
==S-fák==
==Szófák==

ui. folyt köv valamikor.. de akár csinálhatja más is.. :)
-- [[OrcA|Orca]] - 2006.01.24.

[[Category:Infoalap]]

Keresőfák - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|AlgElKeresofaOsszefoglalo}} vissza: AlgElDefiniciok ---- ==Bináris fák== * '''Tárolási szerkezet, tulajdonságok:''' ** Bináris f…”