Fa (adatszerkezet)

Ebben a cikkben a Fa (adatszerkezet) témakörben fogunk foglalkozni, amely ma nagyon fontos téma. A Fa (adatszerkezet) egy olyan érdekesség, amely a mindennapi élet különböző területeire gyakorolt ​​hatása miatt felkeltette a szakértők, a tudósok és a nagyközönség figyelmét. Különböző aspektusainak részletes elemzésével és kimerítő feltárásával igyekszünk jobban megérteni a Fa (adatszerkezet) hatásait a mai világban. Továbbá megvizsgáljuk annak időbeli alakulását és a különböző területekre gyakorolt ​​hatását annak érdekében, hogy átfogó jövőképet kínáljunk, amely gazdagítja a témával kapcsolatos vitát. A Fa (adatszerkezet) kétségtelenül nagy érdeklődést és vitát kiváltó téma, ezért elengedhetetlen, hogy a megérdemelt komolysággal és mélységgel foglalkozzunk vele.

 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
TípusFa

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.