Ebben az oktatóanyagban megismerheti a fa adatszerkezetét. Ezenkívül megismerheti a fák különböző típusait és a fában használt terminológiákat.
A fa egy nemlineáris hierarchikus adatszerkezet, amely élekkel összekötött csomópontokból áll.
Egy fa
Miért a fa adatszerkezete?
Más adatstruktúrák, például tömbök, összekapcsolt lista, verem és várakozási sor lineáris adatstruktúrák, amelyek egymás után tárolják az adatokat. Bármely művelet végrehajtása lineáris adatstruktúrában, az idő bonyolultsága növekszik az adatméret növekedésével. De ez a mai számítási világban nem elfogadható.
A különböző fa adatszerkezetek gyorsabb és könnyebb hozzáférést tesznek lehetővé az adatokhoz, mivel ez egy nem lineáris adatszerkezet.
Fa terminológiák
Csomópont
A csomópont olyan entitás, amely kulcsot vagy értéket tartalmaz, és a gyermek csomópontjaira mutat.
Az egyes utak utolsó csomópontjait levélcsomópontoknak vagy külső csomópontoknak nevezzük , amelyek nem tartalmaznak linket / mutatót a gyermek csomópontokhoz.
A legalább gyermekcsomópontot tartalmazó csomópontot belső csomópontnak nevezzük .
Él
Ez a kapcsolat bármely két csomópont között.
Egy fa csomópontjai és szélei
Gyökér
Ez egy fa legfelső csomópontja.
Egy csomópont magassága
A csomópont magassága az élek száma a csomóponttól a legmélyebb levélig (azaz a csomóponttól a levélcsomópontig terjedő leghosszabb út).
Egy csomópont mélysége
A csomópont mélysége az élek száma a gyökértől a csomópontig.
Egy fa magassága
A fa magassága a gyökércsomópont magassága vagy a legmélyebb csomópont mélysége.
A fák mindegyik csomópontjának magassága és mélysége
Csomópont mértéke
A csomópont mértéke az adott csomópont összes ágának száma.
Erdő
Az elszakadt fák gyűjteményét erdőnek hívják.
Erdő létrehozása egy fáról
Erdőt úgy hozhat létre, hogy kivágja a fa gyökerét.
Fa típusai
- Bináris fa
- Bináris keresési fa
- AVL fa
- B-fa
Fa bejárása
Bármely művelet végrehajtásához egy fán el kell érnie az adott csomópontot. A fa bejárási algoritmus segít meglátogatni egy szükséges csomópontot a fában.
Ha többet szeretne megtudni, kérjük, látogasson el a fák bejárására.
Fa alkalmazások
- A bináris keresési fákat (BST) arra használják, hogy gyorsan ellenőrizzék, van-e elem egy halmazban.
- A halom egyfajta fa, amelyet halom rendezésére használnak.
- A Tries nevű fa módosított változatát a modern útválasztókban használják az útválasztási információk tárolására.
- A legnépszerűbb adatbázisok a B-Fákat és a T-Fákat használják, amelyek a fent megismert faszerkezet variánsai.
- A fordítók egy szintaxisfát használnak az összes program szintaxisának érvényesítéséhez.
