A gráfelméletben a gyökerezett fa vagy arboreszcencia olyan irányított aciklusos gráf , amelynek egyetlen gyökere van, és olyannak, hogy a gyökér kivételével az összes csomópontnak egyetlen szülője van.
A számítástechnikában ez is egy rekurzív adatszerkezet, amelyet az ilyen típusú grafikonok ábrázolására használnak.
Egy fán két kategóriájú elem van:
A fa gyökere az egyetlen csomópont, amelynek nincs szülője. A csomópontokat (apák és fiaik) egy gerinc köti össze egymással . A kontextustól függően egy csomópont utalhat a fa belső vagy külső csomópontjára (levelére).
A csomópont mélysége a távolság, azaz az élek száma a gyökértől a csomópontig. A fa magassága a levél legnagyobb mélysége a fán. A fa mérete a csomópontok száma (a leveleket számítva vagy sem), az út hossza az egyes levelek mélységének összege.
A fák címkézhetők. Ebben az esetben minden csomópontnak van egy címkéje , amely a csomópont „tartalmának” felel meg. A címke nagyon egyszerű lehet: például egész szám. Lehet olyan bonyolult is, amennyit csak akar: objektum, adatstruktúra példánya, mutató stb. Szinte mindig kötelező a címkék összehasonlítása a teljes sorrend függvényében, az algoritmusok fákon történő megvalósítása érdekében.
A fájlrendszer fájljai és mappái általában fa struktúrába vannak rendezve. Lásd például az FHS-t .
A fákat önmagában ritkán használják, de sok korlátozottabb szerkezetű fa létezik, és általában algoritmusokban használják őket , különösen az adatbázisok kezeléséhez vagy a fájlok indexeléséhez. Ezután gyors és hatékony keresést tesznek lehetővé. Itt adjuk meg a főbb példákat:
Ha csak információkat tartalmazó mezőkből szeretne fát építeni, a következő három módszer egyikét teheti:
Megjegyezzük, hogy vannak más típusú ábrázolások is, amelyek a fák egyedi eseteire jellemzőek. Például a kupacot címkék tömbje képviseli.
A fa séták vannak csúcsai látogatók feldolgozni egy fa, például találni egy értéket.
A szélesség elérési útja megegyezik a fa csomópontjainak szintje szerinti elérési úttal . A szint az azonos mélységben elhelyezkedő belső csomópontok vagy levelek összessége - beszélünk egy ugyanolyan magasságú csomópontról vagy levélről is a figyelembe vett fán. Egy adott szint böngészési sorrendjét általában rekurzív módon a szülőcsomópontok - a következő magasabb szintű csomópontok - böngészési sorrendje adja.
Így, ha az előző fát használjuk, az útvonal A , B , C , D , E , F és G lesz .
A mélyreható útvonal egy fán rekurzív útvonal . Általános esetben két megrendelés lehetséges:
A bináris fák esetében elvégezhetünk egy infix utat is, vagyis kezelhetjük a bal és a jobb csomópont közötti aktuális csomópontot. Így, ha az előző fát használjuk, az útvonal D , B , E , A , F , C és G lesz .