Uvod v drevesa v strukturi podatkov
Preden bomo razumeli vrste dreves v strukturi podatkov, bomo najprej preučili drevesa v strukturi podatkov. Drevo v računalniškem polju se imenuje tudi drevo resničnega sveta, vendar je razlika med resničnim svetom in drevesnim računalniškim poljem v tem, da je prikazano kot na glavo in korenina na vrhu ter se veje od korena do listja drevesa. Med različnimi aplikacijami v resničnem svetu se uporablja drevesna podatkovna struktura, saj lahko prikaže razmerja med različnimi vozlišči do hierarhije starš-otrok. Zaradi tega se imenuje tudi hierarhična podatkovna struktura. Najbolj priljubljen je za poenostavitev in pospešitev iskanja in razvrščanja. Velja za eno najmočnejših in najnaprednejših podatkovnih struktur. Drevo je prikaz nelinearne strukture podatkov. Drevo je mogoče prikazati z uporabo različnih uporabniško določenih ali primitivnih vrst podatkov. Za izvajanje drevesa lahko uporabimo matrike, sezname, povezane z razredi ali druge vrste podatkovnih struktur. Gre za skupino vozlišč, ki so med seboj povezana. Na robovih so pritrjena vozlišča, da se prikaže odnos.
Odnosi na drevesu: V zgornjem diagramu je P koren drevesa, P je tudi staršev Q, R in S. Q je otrok P. Torej, Q, R in S so sorodniki. Ker je P vnuk A, B, C, D in E.
Kaj so drevesa?
Drevo je hierarhična podatkovna struktura, ki naravno shranjuje informacije na hierarhični način. Podatkovna struktura Drevesa je ena najbolj učinkovitih in zrelih. Predstavljena so vozlišča, povezana z robovi.
Lastnosti drevesa: Vsako drevo ima določeno korensko vozlišče. Vsako drevesno vozlišče lahko prečka korensko vozlišče. Imenuje se koren, saj je bilo drevo edino korenino. Vsak otrok ima samo enega starša, starš pa ima lahko veliko otrok.
Vrste dreves v strukturi podatkov
Spodaj so vrste dreves v podatkovni strukturi:
1. Splošno drevo
Če na hierarhiji drevesa ni omejitev, se drevo imenuje splošno drevo. Vsako vozlišče ima lahko neskončno število otrok v Splošnem drevesu. Drevo je super skup vseh drugih dreves.
2. Binarno drevo
Binarno drevo je tisto drevo, v katerem je mogoče najti večino dveh otrok za vsakega starša. Otroci so znani kot levi otrok in desni otrok. To je bolj priljubljeno kot večina drugih dreves. Kadar se v binarnem drevesu uporabljajo določene omejitve in lastnosti, se uporabljajo tudi številne druge, kot so drevo AVL, BST (Binary Search Tree), RBT tree itd. Ko bomo šli naprej, bomo podrobno razložili vse te sloge.
3. Binarno iskanje drevo
Binarno drevo iskanja (BST) je binarna drevesna razširitev z več izbirnimi omejitvami. Leva nadrejena vrednost vozlišča mora biti v BST manjša ali enaka nadrejeni vrednosti, desna nadrejena vrednost pa mora biti vedno večja ali enaka vrednosti starša. Ta lastnost binarnega iskalnega drevesa je idealna za iskalne operacije, saj lahko na vsakem vozlišču natančno določimo, ali je vrednost v levem ali desnem podrevju. Zato je poimenovano iskalno drevo.
4. AVL drevo
AVL drevo je binarno iskalno drevo, ki se sam uravnoteži. V imenu izumiteljev Adelson-Velshi in Landis je ime AVL. To je bilo prvo drevo, ki se je dinamično uravnotežilo. Za vsako vozlišče v drevesu AVL se dodeli izravnalni faktor glede na to, ali je drevo uravnoteženo ali ne. Višina otroških vozlišč je največ 1. AVL trta. V drevesu AVL je pravilen faktor ravnotežja 1, 0 in -1. Če ima drevo novo vozlišče, ga bomo zasukali, da bo drevo uravnoteženo. Nato se bo zasukal. Običajne operacije, kot so ogled, vstavljanje in odstranjevanje, v drevesu AVL trajajo O (log n). Večinoma se uporablja pri delu z operacijami Lookups.
5. Rdeče-črno drevo
Druga vrsta drevesa za samodejno uravnoteženje je rdeče-črna. Ime rdeče-črno je podano, ker je rdeče-črno drevo na vsakem vozlišču naslikano rdeče ali črno glede na lastnosti rdeče-črnega drevesa. Ohranja ravnotežje gozda. Čeprav to drevo ni popolnoma uravnoteženo drevo, traja samo O (log n) čas. Ko so nova vozlišča dodana v rdeče-črno drevo, se bodo vozlišča znova zasukala, da bi ohranila lastnosti rdeče-črnega drevesa.
6. N-ari drevo
Največje število otrok v tej vrsti drevesa, ki lahko imajo vozlišče, je N. Binarno drevo je dvoletno drevo, saj je v vsakem vozlišču binarnega drevesa največ 2 otroka. Popolno N-ary drevo je drevo, kjer imajo otroci vozlišča bodisi 0 ali N.
Prednosti Drevesa
Zdaj bomo razumeli Prednosti drevesa:
- Drevo se odraža v strukturnih povezavah podatkov.
- Drevo se uporablja za hierarhijo.
- Ponuja učinkovit postopek iskanja in vstavljanja.
- Drevesa so prožna. To omogoča premestitev poddebel z minimalnim naporom.
Zaključek - Vrste dreves v strukturi podatkov
Tako smo v tem članku videli, kaj je zgradba dreves, kakšne so različne vrste dreves v strukturi podatkov in njegove koristi. Upam, da ste dobili predstavo o nekaterih običajnih drevesih v strukturi podatkov.
Priporočeni članki
To je vodnik za Vrste dreves v strukturi podatkov. Tukaj razpravljamo o tem, kaj so drevesa, 6 vrst dreves v strukturi podatkov, s prednostmi. Obiščite lahko tudi druge naše sorodne članke, če želite izvedeti več -
- AWS Data Pipeline
- Oracle skladiščenje podatkov
- Večdimenzionalna baza podatkov
- Struktura podatkov Vprašanja glede intervjuja s Java