Hierarchikus adatszerkezetek

Olyan adatszerkezetek, amelyek valamilyen értelemben a lista általánosításainak tekinthetőek. A hierarchikus adatszerkezetben egy elemnek akárhány rákövetkezője lehet, de minden elemnek csak egyetlen megelőzője létezik. Van egy kitüntetett eleme, amelynek nincs megelőzője, és több olyan eleme, amelynek nincs rákövetkezője.

FA (TREE)

Dinamikus, homogén adatszerkezet, amelyben minden elem megmondja a rákövetkezőjét.
A gyökérelem a fa azon eleme, amelynek nincs megelőzője. A legegyszerűbb fa egyetlen gyökérből áll. Mindig csak egy gyökérelem van, üres fában egy sem.
A levélelemek a fa azon elemei, amelyeknek nincs rákövetkezőjük. Bármennyi lehet belőlük. Úgy érhetőek el, hogy a gyökérelemből indulva veszem a gyökérelem rákövetkezőjét, majd annak a rákövetkezőjét stb.
A fa közbenső elemei a fa nem gyökér- ill. levélelemei, hanem az összes többi eleme.
Az út a gyökérelemtől kiinduló, különböző szinteken átmenő, és levélelemben véget érő egymáshoz kapcsolódó élsorozat (lista).
Az út hosszán az adott útban szereplő élek számát értjük. Minden levélelem a gyökértől pontosan egy úton érhető el, út helyett szokás beszélni a fa ágairól is. Egy fában az utak száma megegyezik a levélelemek számával.
A fán belül vannak szintek, egy elem szintje megegyezik az elem gyökérelemtől vett távolságával. A 0. szinten a gyökérelem helyezkedik el, az első szinten a gyökérelem rákövetkezői (a gyökértől egy élnyi távolságra lévő elemek), a második szinten ezeknek a rákövetkezői, és így tovább. A maximális szintszámot a fa magasságának vagy mélységének nevezzük.
Minden közbenső elem egy részfa gyökereként tekinthető, így a fa részfákra bontható. Beszélhetünk üresfáról is, ez a fáknak az a szélsőséges esete, amikor a fának egyetlen eleme sincs.

A fát tekinthetjük rendezett vagy rendezetlen módon. Ha rendezetlen módon vizsgáljuk, akkor az egy elemből kiinduló ágaknak nem tulajdonítunk rendezettséget, felcserélhetőek, azaz a sorrendjük tetszőleges. Ha egy fa rendezett, akkor az egy elemből kiinduló éleknek a sorrendje kötött. Tekintsük ezt a két fát:

Ha rendezetlen módon vizsgáljuk, akkor a két fa megegyezik, ha viszont feltesszük, hogy rendezettek, akkor a két fa nem ekvivalens.

Bináris fa
A számítástechnikában kitüntetett szerepe van a bináris fának. A bináris fa olyan fa, amelyben minden elemnek legfeljebb két rákövetkezője lehet. Szigorú értelemben vett bináris fáról akkor beszélünk, amikor minden elemnek 0 vagy pontosan 2 rákövetkező eleme van. Rendezett bináris fáknál a rendezettség miatt az egyértelműség kedvéért beszélhetünk baloldali és jobboldali részfákról. Tetszőleges nem bináris fa reprezentálható bináris fa segítségével a következő módon:

A binárisan ábrázolandó fa gyökéreleme a bináris fában is gyökérelem lesz. Ezek után a bináris fa baloldali részfájának gyökéreleme legyen a következő szinten lévő legbaloldalibb elem. Ehhez láncoljuk hozzá az azonos szinten lévő, közös gyökerű elemeket egymás jobboldali részfáiként. Ezt a folyamatot ismételni kell az egész fára, minden szinten. A bináris fában az eredeti fa levélelemei nem feltétlenül maradnak levélelemek, viszont felismerhetőek arról, hogy nincs baloldali részfájuk. Bármely fa kezelhető bináris faként.

Műveletek
Létrehozás: Létrehozzuk az üres fát, majd egy elemet viszünk be (a gyökérelemet), ezután a létrehozás nem más, mint a fa bővítése.
Bővítés: Bővíteni általában levélelemmel szoktunk, ritkábban részfával. Általában csak a levélelemmel való bővítést értelmezzük, de tetszőleges helyen való bővítés is értelmezhető, a fa átstrukturálásával jár.
Törlés: Bináris fából bármikor törölhetek egy részfát, közbenső elemet általában nem. Ez fizikai törlés, logikai törlést bármikor végezhetek.
Csere: A megfelelő adatelemet bejárással elérem és az értékét bármikor fölülírhatom.
Rendezés, keresés, elérés: Nincs, legalábbis a korábbi értelemben. Elérés helyett egy speciális faművelet, a bejárás értelmezhető:
Bejárás: A bejárás az a tevékenység, amikor a fát, mint hierarchikus adatszerkezet egy sorra, lineáris adatszerkezetre képezzük le. A fa elemeit a bejárás folyamán egyszer, és pontosan egyszer érintjük, az elemek között valamilyen sorrendet állapítunk meg, attól függően, hogy hogyan járjuk be a fát. Három bejárási mód van, ezek közötti különbség abban rejlik, hogy a bejárás folyamán a gyökérelemet mikor dolgozzuk fel.

• preorder bejárás: Ha a fa üres, akkor vége a bejárásnak, egyébként vegyük a gyökérelemet és dolgozzuk fel (vagy képezzük le a sor első elemére). Ezután járjuk be preorder módon a baloldali, majd a jobboldali részfát. Pl. a lenti fánál: abdecfg.
• inorder bejárás: Ha a fa üres, akkor a bejárás befejeződik. Egyébként járjuk be inorder módon a baloldali részfát, majd dolgozzuk fel a gyökérelemet, és járjuk be ugyanezen módszerrel a jobboldali részfát. Pl. a lenti fánál: dbeafcg.
• postorder bejárás: Üres fánál vége, egyébként járjuk be postorder módon a baloldali, majd a jobboldali részfát, végül dolgozzuk fel a gyökérelemet. Pl. a lenti fánál: debfgca.

A bináris fáknál a leggyakoribb ábrázolás a szétszórt ábrázolás, majdnem kizárólagosan ezt alkalmazzák. Egy fa eleme egy adatrészből és két mutatórészből áll, ezek egyike a bal, a másik a jobb oldali részfát címzi. A gyökérmutató fej jellegű, egy fán kívüli információ. Ha a fej NIL, akkor a fa üres.

Alkalmazható a folytonos tárolás is, leginkább akkor, ha a fa statikus. Ilyenkor a fát egy bejárással leképezzük egy sorra. Három darab egydimenziós tömbre lesz szükség: Adat, B (a bal oldali részfák indexei, hol van a bal oldali részfa gyökere), J (a jobb oldali részfák indexei, hol van a jobb oldali részfa gyökere). Az Adat vektorban valamilyen módon felsorolom a fa elemeit.
Ha valamely i-re B[i] és J[i] is nulla, akkor az Adat[i] levélelem. A bővítést és a törlést nehezebbé teszi, a bejárást könnyebbé.
Bármely kifejezéshez felírható a megfelelő bináris fa, a kifejezésfája. A kifejezés és a bináris fa között kölcsönösen egyértelmű a megfeleltetés: az operandusokat és a műveleti jeleket a fa egy-egy elemének tekintem (a zárójelekkel nem foglalkozom). A kérdés az, hogy az operandusokhoz képest a műveleti jelek hol helyezkednek el.

Pl. ha a kifejezés az a/b+c*(d-e):

Minimális magasságú fa
Legyen adva egy adott elemszám. Ez alapján fel lehet építeni egy olyan fát, amelynek a magassága az adott elemszám mellett a lehető legkisebb. Ezt megtehetjük úgy, hogy a legalsó szint kivételével minden szintre a lehető legtöbb elemet helyezzük el. Jelentősége az, hogy az utak minimálisak, bármely levélelem a legrövidebb úton érhető el.

Tökéletesen kiegyensúlyozott fa
Egy fa akkor tökéletesen kiegyensúlyozott, ha minden elem bal- illetve jobboldali részfájában elhelyezett elemek száma legfeljebb eggyel tér el. Mindig minimális magasságú.
A kérdés az, hogy hogyan lehet létrehozni adott elemszám (n) mellett egy tökéletesen kiegyensúlyozott fát. Ez a következőképpen történik: az elemeket az érkezés sorrendjében vesszük, az első elem a gyökér lesz. A maradék elemből előállítjuk a gyökér n_b = (n % 2) elemszámú bal oldali részfáját, majd ugyígy előállítjuk a gyökér n_j = (n - n_b - 1) elemszámú jobb oldali részfáját.

A bináris fákat olyan adathalmaz feldolgozására használják gyakran, amikor az adatelemeknek van egy kulcsrészük (táblázatok) vagy maguk az adatelemek különböző értékűek. Ilyenkor a kulcs a feldolgozás alapja, a rendezett kulcs alapján kell keresni.
Ha adott elemszám mellett a fát úgy építem fel, hogy bármely elemére igaz, hogy az elem baloldali részfájában az összes eleme kulcsa kisebb, a jobboldali részfájában az összes eleme kulcsa pedig nagyobb az adott elem kulcsánál, akkor keresőfáról (vagy rendezőfáról) beszélünk.

A keresőfa jelentősége abból áll, hogy ha van egy adott elemünk, amelyet meg akarunk keresni a fában, akkor a gyökértől kiindulva bármelyik kulcsú elem megkereshető úgy, hogy vizsgáljuk, hogy a gyökérelem kulcsa, megegyezik-e a keresett elem kulcsával. Ha igen, megállunk, ha nem megnézzük, hogy attól kisebb vagy nagyobb. Ha nagyobb, akkor a jobboldali részfán (ha van), ha kisebb, akkor a baloldali részfán (ha van) haladok tovább ugyanezzel a módszerrel, mindaddig, míg az elemet meg nem találom, vagy nem jutok el egy olyan elemhez, amelyiknél az adott irányban nincs több elem, ekkor a keresett kulcsú elem nem szerepel a fán. A keresés gyors, mert maximum a fa magassága +1 hasonlítással vagy megtalálom az elemet, vagy az elem nincs a fában. A keresőfában az elemek olyan sorrendben vannak, hogy ha inorder módon járom be a fát, akkor az elemeknek egy rendezet sorozatát kapjuk.
Egy ilyen fa létrehozása: Vegyük az elemeket az adott sorrendben. Az első elem lesz a fa gyökere. A második elemet véve keressük meg, hogy szerepel-e már a fában. Ha igen, akkor hiba történt (kétszer nem lehet benne ugyanaz az elem), ha nem, akkor döntsünk, hogy az hol helyezkedik el az előzőhöz képest (kisebb vagy nagyobb a gyökérelemnél). Ha nagyobb, akkor a jobboldali részfának lesz az eleme, ha pedig kisebb, akkor a baloldalinak. Beillesztjük az új elemet a részfába: addig megyünk, amíg levélelemet nem találunk, mert mindig levélelemmel bővítünk.
A keresőfából fizikailag bármely elem törölhető.
A keresőfák jelentősége, hogy nagyon gyors keresést tesznek lehetővé. Ez igazán nagy adathalmaz esetén lényeges. Ha a keresőfa tökéletesen kiegyensúlyozott lenne (ez lenne az optimális eset, a minimális magasságú fa), akkor lenne a leggyorsabb a keresés (a keresés maximum annyi lépésig tart, amennyi a fa magassága), de a módosítások miatt nehéz lenne kezelni, mert mindig át kellene szervezni, hogy tökéletesen kiegyensúlyozott legyen. Nem éri meg tökéletesen kiegyensúlyozni őket, ezért kiegyensúlyozott fákat alkalmaznak. (AVL-fa). Egy fa kiegyensúlyozott, ha bármely elem esetén a bal és jobb oldali részfák magasságának különbsége legfeljebb eggyel tér el. Kezelése egyszerűbb, mint a tökéletesen kiegyensúlyozott fáké.
A kiegyensúlyozott fa magassága elemszámtól függetlenül legfeljebb 45%-kal nagyobb, mint egy olyan tökéletesen kiegyensúlyozott fa magassága, amelyik ugyanannyi elemből épül fel, ezért a kiegyensúlyozott keresőfák játszanak fontos szerepet a gyakorlatban. A keresés hatékonyságát maximum 50%-kal rontja, de a fa kezelését könnyebbé teszi. Bővítésük és a törlés egyszerűen megoldható.
Tökéletesen kiegyensúlyozott fát csak fix elemszámnál érdemes használni, mert sokszor kell benne keresni. Ha az elemek száma dinamikusan változik, akkor kiegyensúlyozott keresőfa marad.

Műveletek
Bővítés: A Keres eljárást használva megkeressük, hogy hova szúrjam be az új elemet. Levélelemmel bővítünk. Tegyük fel, hogy a beszúrás után a baloldali részfa magassága nőtt meg. Ekkor három lehetőség van:

• Balra bővítünk, amikor a jobboldali részfa magassága eggyel nagyobb volt (m_baljobb a beszúrás előtt). A fa kiegyensúlyozódik.
• Úgy szúrunk be, hogy korábban tökéletesen ki volt egyensúlyozva a fa (mbal=mjobb a beszúrás előtt). A fa még a beszúrás után is kiegyensúlyozott.
• Balra bővítünk, de a baloldali részfa volt a magasabb (m_jobbbal a beszúrás előtt), a kiegyensúlyozottság, így ki kell egyensúlyozni a fát mutatócserével. Egy-egy ilyen kiegyensúlyozási lépés két vagy három elemet érint, ezeket forgatni kell. Át kell szervezni a fát, a túl hosszú ágat helyre kell billenteni. Alesetek:

A bináris fák bejárása alapvetően rekurzív algoritmusokkal oldható meg, de ezek memória- és időigényesek. A bejárás gyorsítása vezetett ahhoz az ötlethez, hogy bináris fákban, szétszórt ábrázolást feltételezve, vannak olyan elemek (a levélelemek), amelyeknek van 2 NIL mutatójuk. Célunk az, hogy használjuk ezeket a mutatókat arra, hogy visszamutassanak a gyökérre. Ezt nevezzük a vissza- ill. felfűzött fák, vagy a kitaposott út módszerének.

Az inorder bejárás szerinti első elem baloldali mutatója mutasson a gyökérelemre. Az inorder bejárás szerinti utolsó elem jobboldali elem mutatója maradjon NIL. Az összes többi esetben állítsuk be a mutatókat úgy, hogy a baloldali mutató mutasson az adott elemet inorder módon megelőző elemre, a jobboldali pedig az adott elemet inorder módon követő elemre. Ezzel felfűztük a fát, így a fában kétfajta mutató lesz: a tényleges (részfára mutató) mutató és visszafűző mutató. Hogy a két mutatót megkülönböztessük, hozzá kell rendelni egy-egy jelzőbitet. Például, ha a bit értéke 1, akkor részfára mutat, ha 0, akkor visszafűző mutató.

A felfűzött fa a preorder és az inorder bejárást segíti, mert ezen mutatók segítségével rekurzió nélkül be tudom járni a fát, viszont a postorder bejárást nem teszi hatékonyabbá. Ez általában statikus fáknál használható jól, mert különben minden változtatásnál a mutatókat is változtatni kellene, és kezelése nehézkessé válna.
Többágú rendezett fák esetén is lehet értelmezni a bejárást. Pl. preorder bejárás: Ha a fa üres, akkor vége. Egyébként feldolgozzuk a gyökeret, majd utána preorder módon a legbaloldalibb részfát járjuk be, majd az összes többi részfát rendezettség szerint. Hasonlóan lehet végrehajtani az inorder és a postorder bejárást is.
A reprezentációjára az egyik megoldás a bináris fa. Másik lehetséges módja az, hogy többágú fákat úgy ábrázolok, hogy annyi mutatója legyen minden egyes elemnek, ahány részfa indul ki az adott elemből. Az elemeknél vagy dinamikus számú mutatót kell alkalmazni, vagy fix mutatótömböt, de ekkor a mutatók száma maximált: annyinak kell lennie, hogy minden elem kezelhető legyen. A karbantartása könnyű, de sok helyet foglal. Nincsenek általános elvek ill. algoritmusok, a megoldása problémafüggő.
Ezek a lemezen megjelenő fáknál játszanak alapvető szerepet, mert az állományok kezelésénél nagy probléma a mozgatás és az átviteli idő. A mutatók lemezcímeket jelentenek, és nem egy tárbeli címet. A cél az, hogy ne egy elemet mozgassunk, hanem adatcsoportokat. A többágú fa a lemezen van. Ha elemenként fogom meg, minden elemet egyenként ki kell vinnem, és ez lassú. A fát osszuk fel lapokra, egy lapon több elem legyen. Lapot mozgassunk a lemez és a gép között, lapot hozzunk be a tárba. A lap elérése periféria sebességű, az elem sebessége pedig társebességű, így lényegesen gyorsabb a művelet.
Tökéletesen kiegyensúlyozott bináris fa lapokra osztása:

B-fák (balanced)
Speciális keresőfák. A kiegyensúlyozott fák, a kereső fák és a lapra történő felosztás elvét viszik tovább. Viszonylag könnyű karbantartani, és gyors a keresés. Jelentőségük az állományoknál vannak.
Mindig adott egy n szám, amely a B-fa rendje. Úgy kell felépíteni a fát, hogy minden lapon legalább n és legfeljebb 2n db elem legyen. Az aktuális elemszám egy olyan m szám, melyre teljesül, hogy n < m < 2n.
Ha összesen k db elemem van, legrosszabb esetben n/logk hivatkozással meg tudom keresni az adott elemet. Általában akkor használjuk, ha van kulcs az adatoknál.
A B-fa definíciója: A B-fa elemi lapok összessége. Minden lap maximum 2n db elemet tartalmaz, és minden lap, kivéve a gyökérlapot, legalább n db elemet tartalmaz, a gyökérlap legalább egyet. A B-fában minden levéllap ugyanazon a szinten van. Egy lap vagy levéllap, vagy m+1 rákövetkezője van (m a lapon elhelyezett adatok száma).

Műveletek
Létrehozás: Üres fa bővítése.
Bővítés: Mindig levéllapon történik. Megkeresem a bővítendő elem helyét.
Egyszerű esete az, amikor olyan lapra akarok bővíteni, ahol az elemek száma kisebb, mint a megengedett maximális érték (m < 2n).
Ha olyan lapra kellene bővíteni, amelyik tele van (2n eleme van), akkor új lapot kell létrehozni. Ha az új elemet is felviszem a lapra, akkor 2n + 1 elemem lesz. Ezen elemek közül a középső elemet fölviszem a részfa gyökérlapjára, majd ott a megfelelő helyre beillesztem. A maradék 2n első felét az első, második felét a második lapra viszem. Ez a vágás. Így részfa gyökérlapon bővítettünk. Ha a felvitt elem befért, akkor nincs probléma, ha nem fért be, akkor ezen a szinten is vágni kell ugyanezzel az algoritmussal. Előfordulhat, hogy a gyökérelemen nem tudunk bővíteni, ezért itt is vágni kell, így a fa magassága eggyel nő, lesz egy új, egyelemű gyökerünk. Ez az egyetlen eset, hogy a fa magassága változhat egy szinttel, egyébként nem változik.
Törlés: Bármely lapról lehet.
Meg kell keresni az adott kulcsú elemet. Ha a törlendő elemet levéllapon találtuk meg, akkor fizikailag törlöm, a mutatókkal nem kell foglalkozni. Ha nem levéllapon találtuk meg, akkor a törlendő elemet felülírom a rendezettségben az őt megelőző vagy a rákövetkező levéllapon lévő elemmel, és azt törlöm.
Ha az adott lapon az elemek száma minimálisan n marad, akkor nincs baj. Elem törlése annyit jelent, hogy a tőle jobbra állókat ráhúzom. Lehet, hogy kevesebb lesz az elemek száma, mint n, ilyenkor a szomszédos lapból kölcsönkérünk elemet. Ez csak akkor lehetséges, amikor a szomszéd lapon több mint n db elem van, és ekkor az eggyel fentebbi lapon keresztül áthúzom az adott elemet. Gyakorlatilag ez az előbbi vágás inverze.
Ha két szomszédos lapon az elemek száma 2n-1, akkor összevonjuk a két szomszédos lap elemeit, megszüntethetjük az egyik (az üres) lapot, és a gyökérből hozzávesszük a "középső" elemet. Ilyenkor az előző szintet is csökkentjük egy elemmel. Lehet, hogy magasabb szinteken is kevés elem van, itt is hasonlóan járunk el. Végiggyűrűzhet a fán, lehet, hogy a gyökérlapot is meg kell szüntetni, ekkor a fa magassága csökken eggyel.
Rendezés: Nincs.
Feldolgozás: Alapja a keresés.

HIERARCHIKUS LISTA

Tekinthetjük ezt a listát a listák általánosításainak. A listák elemei listák is lehetnek, ezért a listaműveletek értelmezhetőek erre a adatszerkezetre.
A hierarchikus lista egy fa szimbolikus kezelésére szolgálhat, az összes, a fáknál ismertetett algoritmus alkalmazható rá. Olyan sztring, amely szimbólumokat tartalmaz.

Egy szintet vissza, vagy vissza a főmenübe.