Fa (adatszerkezet)

Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye.

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.

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.

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:

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:

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

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

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.