Junior
Mi az a bináris fa?
sobes.tech MI
Válasz az MI-től
Kétágú fa egy olyan adatstruktúra, amelyben minden csomópontnak legfeljebb két leszármazottja van: bal és jobb.
Fő jellemzők:
- Gyökér (Root): A fa legfelső csomópontja.
- Csomópont (Node): A fa eleme, amely adatok és hivatkozások tartalmaz a leszármazottaira.
- Gyermek (Child): Egy másik csomópont közvetlenül alatta (szülő).
- Szülő (Parent): Olyan csomópont, amelynek közvetlenül alatta egy vagy több leszármazott van.
- Levél (Leaf): Olyan csomópont, amelynek nincs leszármazottja.
- Ág (Branch): Út a gyökértől a levélig.
- Alfa (Subtree): Egy csomópontból és összes leszármazottjából álló fa.
Különböző típusú kétágú fák:
- Teljes kétágú fa (Full Binary Tree): Minden csomópontnak 0 vagy 2 leszármazottja van.
- Tökéletes kétágú fa (Perfect Binary Tree): Minden szint, kivéve az utolsót, teljesen kitöltött, és az utolsó szinten minden csomópont a lehető legbalra van rendezve.
- Egyensúlyozott kétágú fa (Balanced Binary Tree): Bármely csomópont bal és jobb alfája magasságban legfeljebb 1 különbség van. Példa: AVL-fa, piros-fekete fa.
- Degenerált (kifejlődött) kétágú fa (Degenerate Binary Tree): Minden csomópontnak legfeljebb egy leszármazottja van. Lényegében ez egy láncolt lista.
Különböző algoritmusokban és adatstruktúrákban alkalmazzák, például keresőfák, halmok, szintaktikus fák.