Beremo linearne podatkovne strukture, kot so polje, povezan seznam, sklad in čakalna vrsta, v kateri so vsi elementi razvrščeni zaporedno. Za različne vrste podatkov se uporabljajo različne podatkovne strukture.

Pri izbiri strukture podatkov se upoštevajo nekateri dejavniki:

Kakšno vrsto podatkov je treba shraniti?: Morda obstaja možnost, da je določena struktura podatkov najbolj primerna za nekatere vrste podatkov.Stroški operacij:Če želimo minimizirati stroške operacij za najpogosteje izvajane posege. Na primer, imamo preprost seznam, na katerem moramo izvesti operacijo iskanja; potem lahko ustvarimo matriko, v kateri so elementi shranjeni v razvrščenem vrstnem redu za izvedbo binarno iskanje . Binarno iskanje deluje zelo hitro za preprost seznam, saj iskalni prostor razdeli na polovico.Poraba pomnilnika:Včasih želimo podatkovno strukturo, ki uporablja manj pomnilnika.

Drevo je tudi ena izmed podatkovnih struktur, ki predstavljajo hierarhične podatke. Recimo, da želimo prikazati zaposlene in njihove položaje v hierarhični obliki, potem jo lahko predstavimo, kot je prikazano spodaj:

Zgornje drevo prikazuje organizacijska hierarhija nekega podjetja. V zgornji strukturi je Janez ali je direktor družbe, John pa ima dva neposredna podrejena, imenovana kot Steve in Rohan . Steve ima imenovane tri neposredne podrejene Lee, Bob, Ella kje Steve je vodja. Bob ima imenovana dva neposredna podrejena naj in Emma . Emma ima dva imenovana neposredna poročila Tom in Raj . Tom ima enega neposrednega poročevalca račun . Ta posebna logična struktura je znana kot a Drevo . Njegova struktura je podobna pravemu drevesu, zato se imenuje a Drevo . V tej strukturi je korenina je na vrhu, njene veje pa se premikajo navzdol. Zato lahko rečemo, da je drevesna podatkovna struktura učinkovit način shranjevanja podatkov na hierarhični način.

Razumejmo nekaj ključnih točk podatkovne strukture drevesa.

• Drevesna podatkovna struktura je definirana kot zbirka predmetov ali entitet, znanih kot vozlišča, ki so med seboj povezani, da predstavljajo ali simulirajo hierarhijo.
• Drevesna podatkovna struktura je nelinearna podatkovna struktura, ker ne shranjuje na zaporedni način. Gre za hierarhično strukturo, saj so elementi v drevesu razporejeni na več ravneh.
• V podatkovni strukturi drevesa je najvišje vozlišče znano kot korensko vozlišče. Vsako vozlišče vsebuje nekaj podatkov, podatki pa so lahko katere koli vrste. V zgornji drevesni strukturi vozlišče vsebuje ime zaposlenega, zato bi bil tip podatkov niz.
• Vsako vozlišče vsebuje nekaj podatkov in povezavo ali referenco drugih vozlišč, ki jih lahko imenujemo podrejeni.

Nekaj ​​osnovnih izrazov, uporabljenih v podatkovni strukturi Tree.

Oglejmo si drevesno strukturo, ki je prikazana spodaj:

V zgornji strukturi je vsako vozlišče označeno z neko številko. Vsaka puščica, prikazana na zgornji sliki, je znana kot a povezava med obema vozliščema.

Koren:Korensko vozlišče je najvišje vozlišče v drevesni hierarhiji. Z drugimi besedami, korensko vozlišče je tisto, ki nima nobenega nadrejenega. V zgornji strukturi je vozlišče s številko 1 korensko vozlišče drevesa. Če je vozlišče neposredno povezano z nekim drugim vozliščem, se to imenuje razmerje starš-otrok.Podrejeno vozlišče:Če je vozlišče potomec katerega koli vozlišča, je vozlišče znano kot podrejeno vozlišče.Starš:Če vozlišče vsebuje katero koli podvozlišče, se za to vozlišče reče, da je nadrejeno temu podvozlišču.sorojenec:Vozlišča, ki imajo istega starša, so znana kot bratje in sestre.Listno vozlišče:-Vozlišče drevesa, ki nima podrejenega vozlišča, se imenuje listno vozlišče. Listno vozlišče je skrajno spodnje vozlišče drevesa. V splošnem drevesu je lahko poljubno število listnih vozlišč. Listna vozlišča lahko imenujemo tudi zunanja vozlišča.Notranja vozlišča:Vozlišče ima vsaj eno podrejeno vozlišče, znano kot notranji Vozlišče prednika:-Prednik vozlišča je katero koli predhodno vozlišče na poti od korena do tega vozlišča. Korensko vozlišče nima prednikov. V drevesu, prikazanem na zgornji sliki, so vozlišča 1, 2 in 5 predniki vozlišča 10.Potomec:Neposredni naslednik danega vozlišča je znan kot potomec vozlišča. Na zgornji sliki je 10 potomec vozlišča 5.

Lastnosti drevesne podatkovne strukture

Rekurzivna struktura podatkov:Drevo je znano tudi kot a rekurzivna struktura podatkov . Drevo je mogoče definirati kot rekurzivno, ker je razločno vozlišče v drevesni podatkovni strukturi znano kot a korensko vozlišče . Korensko vozlišče drevesa vsebuje povezavo do vseh korenin njegovih poddreves. Levo poddrevo je na spodnji sliki prikazano rumeno, desno poddrevo pa rdeče. Levo poddrevo je mogoče nadalje razdeliti na poddrevesa, prikazana v treh različnih barvah. Rekurzija pomeni zmanjševanje nečesa na sebi podoben način. Torej je ta rekurzivna lastnost strukture drevesnih podatkov implementirana v različnih aplikacijah.
Število robov:Če obstaja n vozlišč, potem bi bilo n-1 robov. Vsaka puščica v strukturi predstavlja povezavo ali pot. Vsako vozlišče, razen korenskega vozlišča, bo imelo vsaj eno vhodno povezavo, znano kot rob. Obstajala bi ena povezava za odnos starš-otrok.Globina vozlišča x:Globino vozlišča x lahko definiramo kot dolžino poti od korena do vozlišča x. En rob prispeva eno enoto dolžine na poti. Tako lahko globino vozlišča x definiramo tudi kot število robov med korenskim vozliščem in vozliščem x. Korensko vozlišče ima globino 0.Višina vozlišča x:Višino vozlišča x lahko definiramo kot najdaljšo pot od vozlišča x do listnega vozlišča.

Na podlagi lastnosti podatkovne strukture drevesa so drevesa razvrščena v različne kategorije.

Izvedba drevesa

Drevesno podatkovno strukturo je mogoče ustvariti z dinamičnim ustvarjanjem vozlišč s pomočjo kazalcev. Drevo v pomnilniku je lahko predstavljeno, kot je prikazano spodaj:

Zgornja slika prikazuje predstavitev drevesne podatkovne strukture v pomnilniku. V zgornji strukturi vozlišče vsebuje tri polja. Drugo polje hrani podatke; prvo polje shranjuje naslov levega otroka, tretje polje pa shranjuje naslov desnega otroka.

V programiranju lahko strukturo vozlišča definiramo kot:

 struct node { int data; struct node *left; struct node *right; } 

Zgornjo strukturo je mogoče definirati samo za binarna drevesa, ker ima lahko binarno drevo največ dva otroka, generična drevesa pa imajo lahko več kot dva otroka. Struktura vozlišča za generična drevesa bi bila drugačna v primerjavi z binarnim drevesom.

Aplikacije dreves

Naslednje so aplikacije dreves:

Shranjevanje naravno hierarhičnih podatkov:Drevesa se uporabljajo za shranjevanje podatkov v hierarhični strukturi. Na primer, datotečni sistem. Datotečni sistem, shranjen na disku, datoteka in mapa sta v obliki naravno hierarhičnih podatkov in shranjena v obliki dreves.Organizirajte podatke:Uporablja se za organiziranje podatkov za učinkovito vstavljanje, brisanje in iskanje. Na primer, binarno drevo ima logN čas za iskanje elementa.Poskusite:Gre za posebno vrsto drevesa, ki se uporablja za shranjevanje slovarja. Je hiter in učinkovit način za dinamično preverjanje črkovanja.Kup:Je tudi drevesna podatkovna struktura, implementirana z uporabo nizov. Uporablja se za izvajanje prednostnih čakalnih vrst.B-Tree in B+Tree:B-Tree in B+Tree sta drevesni podatkovni strukturi, ki se uporabljata za izvajanje indeksiranja v bazah podatkov.Usmerjevalna tabela:Drevesna podatkovna struktura se uporablja tudi za shranjevanje podatkov v usmerjevalnih tabelah v usmerjevalnikih.

Vrste podatkovne strukture drevesa

Drevesne podatkovne strukture so naslednje vrste:

Splošno drevo:Splošno drevo je ena od vrst drevesne podatkovne strukture. V splošnem drevesu ima vozlišče lahko 0 ali največ n število vozlišč. Glede stopnje vozlišča (število vozlišč, ki jih lahko vsebuje vozlišče) ni nobenih omejitev. Najvišje vozlišče v splošnem drevesu je znano kot korensko vozlišče. Otroci nadrejenega vozlišča so znani kot poddrevesa .

Lahko obstaja n število poddreves v splošnem drevesu. V splošnem drevesu so poddrevesa neurejena, saj vozlišč v poddrevesu ni mogoče razporediti.
Vsako neprazno drevo ima rob navzdol, ti robovi pa so povezani z vozlišči, imenovanimi otroška vozlišča . Korensko vozlišče je označeno z nivojem 0. Vozlišča, ki imajo istega starša, so znana kot bratje in sestre . Binarno drevo :Tukaj samo binarno ime predlaga dve števili, tj. 0 in 1. V binarnem drevesu ima lahko vsako vozlišče v drevesu največ dve podrejeni vozlišči. Tu največ pomeni, ali ima vozlišče 0 vozlišč, 1 vozlišče ali 2 vozlišča.

Če želite izvedeti več o binarnem drevesu, kliknite spodnjo povezavo:
https://www.javatpoint.com/binary-tree Binarno iskalno drevo :Binarno iskalno drevo je nelinearna podatkovna struktura, v kateri je povezano eno vozlišče n število vozlišč. Je podatkovna struktura, ki temelji na vozliščih. Vozlišče je lahko predstavljeno v binarnem iskalnem drevesu s tremi polji, tj. podatkovnim delom, levim podrejenim in desnim podrejenim. Vozlišče je lahko povezano z največ dvema podrejenima vozliščema v binarnem iskalnem drevesu, tako da vozlišče vsebuje dva kazalca (levi podrejeni in desni podrejeni kazalec).
Vsako vozlišče v levem poddrevesu mora vsebovati vrednost, manjšo od vrednosti korenskega vozlišča, vrednost vsakega vozlišča v desnem poddrevesu pa mora biti večja od vrednosti korenskega vozlišča.

Vozlišče je mogoče ustvariti s pomočjo uporabniško definiranega podatkovnega tipa, znanega kot struktura, kot je prikazano spodaj:

niz struktur v jeziku c

 struct node { int data; struct node *left; struct node *right; } 

Zgoraj je struktura vozlišča s tremi polji: podatkovno polje, drugo polje je levi kazalec vrste vozlišča, tretje polje pa je desni kazalec vrste vozlišča.

Če želite izvedeti več o binarnem iskalnem drevesu, kliknite spodnjo povezavo:

https://www.javatpoint.com/binary-search-tree

AVL drevo

Je ena od vrst binarnega drevesa ali lahko rečemo, da je različica binarnega iskalnega drevesa. Drevo AVL izpolnjuje lastnost binarno drevo kot tudi od binarno iskalno drevo . To je samouravnotežno binarno iskalno drevo, ki ga je izumil Adelson Velsky Lindas . Tukaj samouravnoteženje pomeni uravnoteženje višin levega poddrevesa in desnega poddrevesa. To uravnoteženje se meri v smislu izravnalni faktor .

Drevo lahko obravnavamo kot drevo AVL, če drevo upošteva binarno iskalno drevo in tudi faktor uravnoteženja. Faktor izravnave je mogoče definirati kot razlika med višino levega poddrevesa in višino desnega poddrevesa . Vrednost faktorja izravnave mora biti 0, -1 ali 1; zato mora imeti vsako vozlišče v drevesu AVL vrednost izravnalnega faktorja 0, -1 ali 1.

Če želite izvedeti več o drevesu AVL, kliknite spodnjo povezavo:

https://www.javatpoint.com/avl-tree

Rdeče-črno drevo

Rdeče-črno drevo je binarno iskalno drevo. Predpogoj za rdeče-črno drevo je, da poznamo binarno iskalno drevo. V binarnem iskalnem drevesu mora biti vrednost levega poddrevesa manjša od vrednosti tega vozlišča, vrednost desnega poddrevesa pa večja od vrednosti tega vozlišča. Kot vemo, je časovna kompleksnost binarnega iskanja v povprečnem primeru log₂n, najboljši primer je O(1), najslabši primer pa O(n).

Ko se na drevesu izvaja katera koli operacija, želimo, da je naše drevo uravnoteženo, tako da vse operacije, kot so iskanje, vstavljanje, brisanje itd., trajajo manj časa, vse te operacije pa bodo imele časovno zapletenost dnevnik₂n.

Rdeče-črno drevo je samouravnoteženo binarno iskalno drevo. Drevo AVL je torej tudi binarno iskalno drevo za uravnoteženje višine zakaj potrebujemo rdeče-črno drevo . Pri drevesu AVL ne vemo, koliko rotacij bi bilo potrebnih za uravnoteženje drevesa, pri rdeče-črnem drevesu pa sta za uravnoteženje drevesa potrebni največ 2 rotaciji. Vsebuje en dodaten bit, ki predstavlja rdečo ali črno barvo vozlišča, da se zagotovi uravnoteženje drevesa.

Raztegnjeno drevo

Podatkovna struktura razpršenega drevesa je tudi binarno iskalno drevo, v katerem je nedavno dostopan element postavljen na korenski položaj drevesa z izvajanjem nekaterih operacij vrtenja. tukaj, raztezanje pomeni nedavno dostopno vozlišče. Je samouravnoteženje binarno iskalno drevo, ki nima eksplicitnega pogoja ravnotežja, kot je AVL drevo.

Morda obstaja možnost, da višina raztegnjenega drevesa ni uravnotežena, tj. višina levega in desnega poddrevesa se lahko razlikujeta, vendar se operacije v raztegnjenem drevesu izvajajo v vrstnem redu miren čas kje n je število vozlišč.

Splay drevo je uravnoteženo drevo, vendar ga ni mogoče obravnavati kot višinsko uravnoteženo drevo, ker se po vsaki operaciji izvede rotacija, ki vodi do uravnoteženega drevesa.

Treap

Podatkovna struktura Treap je nastala iz podatkovne strukture Tree in Heap. Torej obsega lastnosti podatkovnih struktur Tree in Heap. V binarnem iskalnem drevesu mora biti vsako vozlišče na levem poddrevesu enako ali manjše od vrednosti korenskega vozlišča in vsako vozlišče na desnem poddrevesu mora biti enako ali večje od vrednosti korenskega vozlišča. V podatkovni strukturi kopice tako desno kot levo poddrevo vsebujeta večje ključe kot koren; zato lahko rečemo, da korensko vozlišče vsebuje najnižjo vrednost.

V podatkovni strukturi treap ima vsako vozlišče oboje ključ in prioriteta kjer ključ izhaja iz binarnega iskalnega drevesa, prioriteta pa iz podatkovne strukture kopice.

The Treap struktura podatkov sledi dvema lastnostima, ki sta navedeni spodaj:

• Desni podrejeni vozlišča>=trenutno vozlišče in levi podrejeni del vozlišča<=current node (binary tree)< li>
• Otroci katerega koli poddrevesa morajo biti večji od vozlišča (kupa)

B-drevo

B-drevo je uravnoteženo m-način drevo kje m določa vrstni red drevesa. Do zdaj smo prebrali, da vozlišče vsebuje samo en ključ, vendar ima lahko b-drevo več kot en ključ in več kot 2 otroka. Vedno vzdržuje razvrščene podatke. V binarnem drevesu je možno, da so listna vozlišča na različnih ravneh, v b-drevesu pa morajo biti vsa listna vozlišča na isti ravni.

Če je vrstni red m, ima vozlišče naslednje lastnosti:

• Vsako vozlišče v b-drevesu ima lahko največ m otroci
• Za minimalne otroke ima listno vozlišče 0 otrok, korensko vozlišče ima najmanj 2 otroka in notranje vozlišče ima najmanjšo zgornjo mejo m/2 otrok. Na primer, vrednost m je 5, kar pomeni, da ima lahko vozlišče 5 otrok, notranja vozlišča pa lahko vsebujejo največ 3 otroke.
• Vsako vozlišče ima največ (m-1) ključev.

Korensko vozlišče mora vsebovati vsaj 1 ključ, vsa druga vozlišča pa morajo vsebovati vsaj strop m/2 minus 1 ključi.