Keresőfák

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

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ó_):

1. 1. 1. s-nek legfeljebb egy fia van: (könnyű törlés) ekkor x-et helyettesítjük a fiával
      2. 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

1. 1. 1. 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
      2. 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:

|$m_{1}$||$s_{1}$||$m_{2}$||$s_{2}$||$m_{3}$ |} vagy |$m_{1}$||$s_{1}$||$m_{2}$ |}

• • • • $s_{1},s_{2}$ a csúcsban lévő kulcsok, melyekre teljesül hogy $s_{1}<s_{2}$
      • $m_{1},m_{2},m_{3}$ pedig mutatók a csúcs részfáira, amikre igaz, hogy:

1. 1. 1. 1. 1. $MAX(m_{1})<s_{1}$
            2. $MIN(m_{2})=s_{1}$ és $MAX(m_{2})<s_{2}$
            3. $MIN(m_{3})=s_{2}$
      2. 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 $2^{l-1}$ vagyis l ≤ $\log _{2}n+1$

• 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 $s_{1}$ és esetleg $s_{2}$ kulcsokkal a keresett elemet, ez alapján el tudjuk dönteni, hogy melyik részfában kerressük tovább az s-t:

1. 1. 1. $s<s_{1}$ akkor az $m_{1}$ által mutatott részfában keresünk tovább
      2. $s_{1}\leq s<s_{2}$ akkor az $m_{2}$-t követjük
      3. $s_{2}\leq s$ akkor az $m_{3}$ 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:

1. 1. 1. 2 fia van: ebben az esetben a beszúrás viszonylag egyszerű csak x-et kell ügyesen modosítani (TK: 66. old.)
      2. 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:

1. 1. 1. 3 fia van: ebben az esetben a törlés viszonylag egyszerű csak x-et kell ügyesen modosítani (TK: 67. old.)
      2. 2 fia van: ekkor még két lehetőségünk van
         1. 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)
         2. 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 $m_{1}$, $m_{2}$) mutató van, ilyenkor az egyik mutató (mondjuk $m_{2}$) törlendő és csak $m_{1}$ mutat egy valódi részfa gyökerére, tehát mostantól vehetjuk az $m_{1}$ á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 $B_{m}$-fa) tulajdonságai:

1. 1. 1. A gyökér foka legalább 2, kivéve ha csak max 2 szintes a fa
      2. Minden más belső csúcsnak min $\lceil {\frac {m}{2}}\rceil$ fia van
      3. A levelek a gyökértől egyforma távolságra vannak
      4. Egy csúcsnak legfeljebb m mutatója lehet
         

Tehát egy csúcs így néz ki: ($\lceil {\frac {m}{2}}\rceil -1\leq i\leq m-1$) |$m_{0}$||$s_{1}$||$m_{1}$||$s_{2}$||$m_{2}$||...||$s_{i}$||$m_{i}$ |}

• • l szintű, n levelű $B_{m}$-fa fa esetén: $l\leq {\frac {\log _{2}{n}-1}{\log _{2}{\lceil {\frac {m}{2}}\rceil }}}+2$
• 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

Szófák

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