Bevezetés a fákhoz az adatszerkezetben
Mielőtt megértjük az adatszerkezetben a fák típusait, először megvizsgáljuk az adatszerkezetben található fákat. A számítógépes mezőben lévő fára valódi faként is hivatkoznak, azonban a valós világ és a számítási mező fa közötti különbség az, hogy fejjel lefelé mutatva jelenik meg, és tetején gyökér, és gyökérről fára elágazik. A különféle valós alkalmazások között a fa-adatstruktúrát használják, mivel ez bizonyítja a különféle csomópontok közötti kapcsolatot a szülő-gyermek hierarchiával. Ezért hierarchikus adatszerkezetnek is hívják. A legnépszerűbb a keresés és a válogatás egyszerűsítéséhez és felgyorsításához. Az egyik legerősebb és legfejlettebb adatszerkezetnek tekintik. A fa a nemlineáris adatszerkezet ábrázolása. Egy fa különféle felhasználó által meghatározott vagy primitív típusú adatokkal jeleníthető meg. Használhat tömböket, osztályokhoz kapcsolódó listákat vagy más típusú adatszerkezeteket a fa megvalósításához. Ez egy csomópontcsoport, amelyek egymással kapcsolatban vannak. Csomópontok vannak csatolva az élekhez, hogy igazolják a kapcsolatot.
Kapcsolatok egy fában: A fenti diagramban P a fa gyökere, valamint P a Q szülője, R és S. Q a P. gyermeke. Ezért Q, R és S testvérek. Mivel P az A, B, C, D és E nagyszülője
Mik a fák?
A fa egy hierarchikus adatstruktúra, amely természetesen az információkat hierarchikus módon tárolja. A fa adatszerkezete az egyik leghatékonyabb és legfejlettebb. Az élekkel összekötött csomópontok vannak ábrázolva.
A fa tulajdonságai: Minden fának van saját gyökér csomópontja. Minden fa csomópontot egy gyökér csomópont keresztezhet. Gyökérnek hívják, mivel a fa volt az egyetlen gyökér. Minden gyermeknek csak egy szülője van, de a szülőnek sok gyermeke is lehet.
A fák típusai az adatszerkezetben
Az alábbiakban bemutatjuk az adatszerkezetben található fák típusait:
1. Általános fa
Ha a fa hierarchiájára nem vonatkozik korlátozás, akkor egy fát általános fának hívnak. Minden csomópontban végtelen számú gyermek lehet az Általános Fa-ban. A fa az összes többi szuperhalmaz.
2. Bináris fa
A bináris fa az a fa, amelyben a szülők számára a legtöbb két gyermek megtalálható. A gyerekeket bal és jobb gyereknek nevezik. Ez népszerűbb, mint a legtöbb többi fa. Bizonyos korlátozások és jellemzők alkalmazásakor a bináris fán számos más, például AVL-fa, BST (bináris keresési fa), RBT-fa stb. Is felhasználásra kerül. Ha továbblépünk, ezeket a stílusokat részletesen elmagyarázjuk.
3. Bináris keresési fa
A bináris keresési fa (BST) egy bináris fa kiterjesztés, több választható korlátozással. A csomópont bal oldali gyermekértékének a BST-ben alacsonyabbnak kell lennie vagy egyenlőnek kell lennie a szülő értékkel, és a jobb oldali gyermek értéknek mindig nagyobbnak kell lennie, vagy egyenlőnek kell lennie a szülő értékével. Ez a bináris keresési fa tulajdonság ideálisvá teszi a keresési műveleteket, mivel minden csomópontnál pontosan meghatározhatjuk, hogy az érték a bal vagy a jobb alfaban van-e. Ez az oka annak, hogy a Keresőfa nevet kapja.
4. AVL fa
Az AVL fa egy bináris keresési fa önkiegyensúlyozó. A feltalálók, Adelson-Velshi és Landis nevében az AVL nevet kapják. Ez volt az első fa, amely dinamikusan kiegyensúlyozott volt. Az AVL-fa minden csomópontjára kiegyenlítő tényezőt osztanak ki annak alapján, hogy a fa kiegyensúlyozott-e vagy sem. A csomópontok magassága legfeljebb 1. AVL szőlő. Az AVL fában a helyes egyensúlytényező 1, 0 és -1. Ha a fának van új csomópontja, akkor azt elforgatják annak biztosítása érdekében, hogy a fa kiegyensúlyozott legyen. Ezután elforgatható. Az olyan általános műveletek, mint a megtekintés, beillesztés és eltávolítás, O (log n) időt vesznek igénybe az AVL fában. Leginkább akkor alkalmazzák, ha a Keresési műveletekkel dolgozik.
5. Vörös-fekete fa
Egy másik fajta automatikus kiegyensúlyozó fa a vörös-fekete. A vörös-fekete név azért van megadva, mert a Vörös-fekete fa mindegyik csomóponton vörös vagy fekete színű van, a vörös-fekete fa tulajdonságai szerint. Fenntartja az erdő egyensúlyát. Annak ellenére, hogy ez a fa nem teljesen kiegyensúlyozott fa, a keresési művelet csak O (log n) időt vesz igénybe. Amikor az új csomópontokat hozzáadják a Vörös-Fekete Fa-hoz, akkor a csomópontok újra forognak, hogy megőrizzék a Vörös-Fekete fa tulajdonságait.
6. N-ary fa
Az ilyen típusú fákban a csúcsok lehet legfeljebb N. A bináris fa kétéves fa, mivel minden bináris fa csomópontban legfeljebb 2 gyermek. A teljes N-ary fa egy olyan fa, ahol egy csomópont gyerekje 0 vagy N.
A fa előnyei
Most megértjük a fa előnyeit:
- A fa az adatok szerkezeti kapcsolataiban tükröződik.
- A fát a hierarchiához használják.
- Hatékony keresési és beillesztési eljárást kínál.
- A fák rugalmasak. Ez lehetővé teszi az alfák áthelyezését minimális erőfeszítéssel.
Következtetés - A fák típusai az adatszerkezetben
Tehát ebben a cikkben láttuk, hogy mi a fa szerkezete, mi az egyes fafajták az adatszerkezetben és annak előnyei. Remélem, van valamilyen elképzelésed az adatok szerkezetében található néhány általános fáról.
Ajánlott cikkek
Ez egy útmutató a fák típusaihoz az adatszerkezetben. Itt megvitatjuk, mi a fák, az adatszerkezetben a 6 fa fája, előnyeivel. Megnézheti más kapcsolódó cikkeket is, ha többet szeretne megtudni -
- AWS Data Pipeline
- Oracle adattárolás
- Többdimenziós adatbázis
- Adatszerkezet Java interjúkérdések