Fastruktúra

A Programozás Wiki wikiből
(Fa szócikkből átirányítva)

Fastruktúrának (fának) nevezünk egy szerkezetet, ha egy gyökérből, a gyökérhez kötött csúcsokból, és további korábbi csúcsokhoz kötött csúcsokból áll.

Két összekötött csúcs közül a gyökér irányában levőt gyakran szülő-, vagy őscsúcsnak, a másikat gyerek-, vagy leszármazott csúcsnak nevezzük. Fastruktúrában nem megengedett, hogy egy csúcsnak több őse legyen.

Ha minden csúcsnak legfeljebb két leszármazottja van, akkor a fát bináris fának nevezzük.

Sok probléma, és adatszerkezet ábrázolható fával. A hagyományos könyvtárszerkezetek, objektumorientált nyelvekben az osztályok leszármazási kapcsolatai, egy program blokkjainak egymásba ágyazottsága, egy kifejezés részei, a komolyabb adatbáziskezelők indexei általában ábrázolhatók fával.

Kapcsolódó algoritumok[szerkesztés]

Ha felismerjük, hogy egy probléma tere felfogható fastruktúraként, sokat segíthetnek a fastruktúrához kapcsolódó ismert és bevált algoritmusok a probléma kezelésében. Néhány ezek közül: