Fa (adatszerkezet)

Fa
Típus	Fa

Fa alatt egy olyan rekurzív adatszerkezetet értünk számítástechnikában, amely belső és külső csúcsok hierarchikus (szülő-gyermek) elrendezéséből áll. Formálisan, egy fa az vagy (1) egy külső csúcs, vagy pedig egy belső csúcs (szülő), amelyhez bizonyos számú fa kapcsolódik (gyermekek). Matematikailag, az adatszerkezet megfelel egy irányított (gyökeres) fának, amelyben egy kitüntetett csúcsból (a gyökérből) pontosan egy út vezet minden más csúcshoz.

Gyakran (de nem mindig), minden belső csúcsnak ugyanannyi gyereke van, azaz ugyanaz a fokszáma, és a gyerekek sorrendje számít.

Bináris fa

Bármely típusú fa ábrázolható bináris fa segítségével. A bináris fa legfőbb jellemzője az, hogy bármelyik csomópontnak csak két utóda lehet. A bináris fák utódjait megkülönböztetjük aszerint, hogy bal illetve jobb részfák.

Ábrázolása

Különféle implementációkban általában csak a belső csúcsok hordoznak információt, és a külső csúcsokat csak egy null mutató jelöli. Az alábbi Java program egy bináris fa definícióját tartalmazza: ebben a példában minden csúcsnál eltároljuk a szülőt és a gyerekeket is.

class Csucs // bináris fa egy belső csúcsa
{
    Csucs szülő; // mutató a szülőre, null ha gyökér
    Csucs bal; // mutató a bal gyerekre, null ha külső gyerek
    Csucs jobb; // mutató a jobb gyerekre, null ha külső gyerek
    Object adat; 
}

C++ - ban:

Bináris fa 9 (belső) csúccsal (a külső csúcsok nincsenek feltüntetve). A fa gyökere a 2-es csúcs. (Ábrákon általában felülre kerül a gyökér, és lefele vannak a gyermekek.)

struct fa{
    int info;
    fa *bal, *jobb;
}

Bináris fákat ábrázolhatunk tömbök segítségével is, ebben az esetben meg kell adnunk minden csomópontra, az indexét, az információját és a bal illetve a jobb utódját.

Például a képen látható bináris fa esetében, így néz ki tömbökkel az ábrázolása:

Index	Információ	Bal utód	Jobb utód
1	2	2	3
2	7	4	5
3	5	0	6
4	2	0	0
5	6	7	8
6	9	9	0
7	5	0	0
8	11	0	0
9	4	0	0

Műveletek fákkal

• létrehozás
• bejárás
• adott elem megkeresése
• adott elem beszúrása
• adott elem törlése

Tökéletesen egyensúlyozott bináris fa

Egy tökéletesen egyensúlyozott bináris fa minden levele az utolsó két szinten helyezkedik el a fában úgy, hogy bármely csomópont esetében a bal részfa csomópontjainak száma legfeljebb 1-gyel különbözik a jobb részfa csomópontjainak számától.

Tökéletesen egyensúlyozott bináris fa létrehozó alprogramja C++ -ban:

fa *letrehoz(int n){
    if (n){
        int nb, nj;
        nb = n/2;
        nj = n-nb-1;
        fa *gyoker = new fa;
        cin >> gyoker ->info;
        gyoker -> bal = letrehoz(nb);
        gyoker -> jobb = letrhoz(nj);
        return gyoker;
    }
    else return NULL;
}

Keresőfa

A bináris fák rendkívül előnyösek, ha keresési művelet végrehajtását tervezzük.

Egy bináris keresőfa minden csomópontjára igaz, hogy a bal részfájában csak a saját kulcsánál kisebb, míg a jobb részfájában csak a saját kulcsértékénél nagyobb értékek találhatók.