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.
| Fa | |
| Típus | Fa |
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
szerkesztésBá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
szerkesztésKü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:
| 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
szerkesztés- 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
szerkesztésEgy 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
szerkesztésA 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.