Čitamo linearne podatkovne strukture poput niza, povezanog popisa, hrpe i reda čekanja u kojem su svi elementi raspoređeni na sekvencijalan način. Različite strukture podataka koriste se za različite vrste podataka.

Za odabir strukture podataka uzimaju se u obzir neki čimbenici:

Koju vrstu podataka treba pohraniti?: Postoji mogućnost da određena struktura podataka najbolje odgovara nekoj vrsti podataka.Troškovi operacija:Ako želimo minimizirati troškove operacija za najčešće izvođene operacije. Na primjer, imamo jednostavan popis na kojem moramo izvesti operaciju pretraživanja; tada možemo stvoriti niz u kojem su elementi pohranjeni poredanim redoslijedom za izvođenje binarno pretraživanje . Binarno pretraživanje radi vrlo brzo za jednostavan popis budući da dijeli prostor pretraživanja na pola.Upotreba memorije:Ponekad želimo strukturu podataka koja koristi manje memorije.

Stablo je također jedna od struktura podataka koje predstavljaju hijerarhijske podatke. Pretpostavimo da želimo prikazati zaposlenike i njihove položaje u hijerarhijskom obliku, a onda se to može predstaviti kao što je prikazano u nastavku:

Gornje stablo prikazuje organizacijska hijerarhija neke tvrtke. U gornjoj strukturi, Ivan je direktor tvrtke tvrtke, a John ima dva izravna izvještaja imenovana kao Steve i Rohan . Steve ima imenovana tri izravna odgovorna Lee, Bob, Ella gdje Steve je menadžer. Bob ima imenovana dva izravna odgovorna treba i Emma . Emma ima dva izravna izvještaja imenovana Tom i Raj . Tom ima jednog izravnog izvještaja imenovanog Račun . Ova određena logička struktura poznata je kao a Drvo . Građa mu je slična pravom drvetu, pa je i nazvana a Drvo . U ovoj strukturi, korijen je na vrhu, a grane se kreću prema dolje. Stoga možemo reći da je struktura podataka Tree učinkovit način pohranjivanja podataka na hijerarhijski način.

Razmotrimo neke ključne točke podatkovne strukture stabla.

• Podatkovna struktura stabla definirana je kao zbirka objekata ili entiteta poznatih kao čvorovi koji su međusobno povezani kako bi predstavljali ili simulirali hijerarhiju.
• Podatkovna struktura stabla je nelinearna podatkovna struktura jer se ne pohranjuje na sekvencijalan način. To je hijerarhijska struktura jer su elementi u stablu raspoređeni na više razina.
• U podatkovnoj strukturi stabla, najviši čvor je poznat kao korijenski čvor. Svaki čvor sadrži neke podatke, a podaci mogu biti bilo koje vrste. U gornjoj strukturi stabla, čvor sadrži ime zaposlenika, tako da bi vrsta podataka bila niz.
• Svaki čvor sadrži neke podatke i vezu ili referencu drugih čvorova koji se mogu nazvati podređeni.

Neki osnovni pojmovi koji se koriste u podatkovnoj strukturi stabla.

Razmotrimo strukturu stabla koja je prikazana u nastavku:

U gornjoj strukturi, svaki čvor je označen nekim brojem. Svaka strelica prikazana na gornjoj slici poznata je kao a veza između dva čvora.

Korijen:Korijenski čvor je najviši čvor u hijerarhiji stabla. Drugim riječima, korijenski čvor je onaj koji nema roditelja. U gornjoj strukturi, čvor pod brojem 1 je korijenski čvor stabla. Ako je čvor izravno povezan s nekim drugim čvorom, to bi se nazvalo odnos roditelj-dijete.Podređeni čvor:Ako je čvor potomak bilo kojeg čvora, tada je čvor poznat kao podređeni čvor.Roditelj:Ako čvor sadrži bilo koji podčvor, tada se za taj čvor kaže da je roditelj tog podčvora.Brat ili sestra:Čvorovi koji imaju istog roditelja poznati su kao braća i sestre.Listni čvor:-Čvor stabla koji nema nijedan čvor dijete naziva se čvor lista. Listni čvor je najdonji čvor stabla. U općem stablu može postojati bilo koji broj lisnih čvorova. Listni čvorovi također se mogu nazvati vanjskim čvorovima.Unutarnji čvorovi:Čvor ima barem jedan podređeni čvor poznat kao an unutarnje Čvor pretka:-Predak čvora je bilo koji čvor prethodnik na putu od korijena do tog čvora. Korijenski čvor nema nikakvih predaka. U stablu prikazanom na gornjoj slici, čvorovi 1, 2 i 5 su preci čvora 10.Potomak:Neposredni nasljednik danog čvora poznat je kao potomak čvora. Na gornjoj slici, 10 je potomak čvora 5.

Svojstva strukture podataka stabla

Rekurzivna struktura podataka:Drvo je također poznato kao a rekurzivna struktura podataka . Stablo se može definirati kao rekurzivno jer je istaknuti čvor u strukturi podataka stabla poznat kao a korijenski čvor . Korijenski čvor stabla sadrži vezu sa svim korijenima njegovih podstabala. Lijevo podstablo prikazano je žutom bojom na donjoj slici, a desno podstablo crvenom bojom. Lijevo podstablo može se dalje podijeliti u podstablo prikazano u tri različite boje. Rekurzija znači smanjivanje nečega na sebi sličan način. Dakle, ovo rekurzivno svojstvo strukture podataka stabla implementirano je u raznim aplikacijama.
Broj rubova:Ako postoji n čvorova, tada bi bilo n-1 rubova. Svaka strelica u strukturi predstavlja vezu ili put. Svaki čvor, osim korijenskog čvora, imat će najmanje jednu dolaznu vezu poznatu kao rub. Postojala bi jedna poveznica za odnos roditelj-dijete.Dubina čvora x:Dubina čvora x može se definirati kao duljina puta od korijena do čvora x. Jedan brid doprinosi jednoj jedinici duljine na putu. Dakle, dubina čvora x također se može definirati kao broj bridova između korijenskog čvora i čvora x. Korijenski čvor ima dubinu 0.Visina čvora x:Visina čvora x može se definirati kao najduži put od čvora x do čvora lista.

Na temelju svojstava podatkovne strukture stabla, stabla se klasificiraju u različite kategorije.

Implementacija stabla

Struktura podataka stabla može se stvoriti dinamičkim stvaranjem čvorova uz pomoć pokazivača. Stablo u memoriji može se prikazati kao što je prikazano u nastavku:

Gornja slika prikazuje prikaz strukture podataka stabla u memoriji. U gornjoj strukturi, čvor sadrži tri polja. Drugo polje pohranjuje podatke; prvo polje pohranjuje adresu lijevog djeteta, a treće polje pohranjuje adresu desnog djeteta.

U programiranju se struktura čvora može definirati kao:

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

Gornja struktura može se definirati samo za binarna stabla jer binarno stablo može imati najviše dvoje djece, a generička stabla mogu imati više od dvoje djece. Struktura čvora za generička stabla bila bi drugačija u usporedbi s binarnim stablom.

Primjene drveća

Sljedeće su primjene drveća:

Pohranjivanje prirodno hijerarhijskih podataka:Stabla se koriste za pohranjivanje podataka u hijerarhijskoj strukturi. Na primjer, datotečni sustav. Datotečni sustav pohranjen na disku, datoteka i mapa su u obliku prirodno hijerarhijskih podataka i pohranjeni su u obliku stabala.Organizirajte podatke:Koristi se za organiziranje podataka za učinkovito umetanje, brisanje i pretraživanje. Na primjer, binarno stablo ima logN vremena za pretraživanje elementa.Pokušajte:To je posebna vrsta stabla koja se koristi za pohranjivanje rječnika. To je brz i učinkovit način za dinamičku provjeru pravopisa.Hrpa:To je također stablo podatkovne strukture implementirano korištenjem polja. Koristi se za implementaciju prioritetnih redova.B-stablo i B+stablo:B-Tree i B+Tree su strukture podataka stabla koje se koriste za implementaciju indeksiranja u bazama podataka.Tablica usmjeravanja:Struktura podataka stabla također se koristi za pohranu podataka u tablice usmjeravanja u usmjerivačima.

Vrste strukture podataka stabla

Sljedeće su vrste strukture podataka stabla:

Opće stablo:Opće stablo jedna je od vrsta strukture podataka stabla. U općem stablu, čvor može imati ili 0 ili najviše n broj čvorova. Ne postoji ograničenje nametnuto stupnju čvora (broj čvorova koje čvor može sadržavati). Najviši čvor u općem stablu poznat je kao korijenski čvor. Djeca nadređenog čvora poznata su kao podstabla .

Tamo može biti n broj podstabala u općem stablu. U općem stablu, podstabla su neuređena jer se čvorovi u podstablu ne mogu poredati.
Svako neprazno stablo ima silazni rub, a ti su rubovi povezani s čvorovima poznatim kao dječji čvorovi . Korijenski čvor označen je razinom 0. Čvorovi koji imaju istog roditelja poznati su kao braća i sestre . Binarno stablo :Ovdje samo binarno ime sugerira dva broja, tj. 0 i 1. U binarnom stablu svaki čvor u stablu može imati najviše dva podređena čvora. Ovdje krajnje znači da li čvor ima 0 čvorova, 1 čvor ili 2 čvora.

Da biste saznali više o binarnom stablu, kliknite na donju poveznicu:
https://www.javatpoint.com/binary-tree Stablo binarnog pretraživanja :Binarno stablo pretraživanja je nelinearna struktura podataka u kojoj je jedan čvor povezan n broj čvorova. To je podatkovna struktura temeljena na čvoru. Čvor se može predstaviti u binarnom stablu pretraživanja s tri polja, tj. podatkovni dio, lijevo dijete i desno dijete. Čvor se može povezati s najviše dva podređena čvora u stablu binarnog pretraživanja, tako da čvor sadrži dva pokazivača (lijevo podređeno i desno podređeno).
Svaki čvor u lijevom podstablu mora sadržavati vrijednost manju od vrijednosti korijenskog čvora, a vrijednost svakog čvora u desnom podstablu mora biti veća od vrijednosti korijenskog čvora.

Čvor se može stvoriti uz pomoć korisnički definiranog tipa podataka poznatog kao struktura, kako je prikazano dolje:

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

Gore je struktura čvora s tri polja: podatkovno polje, drugo polje je lijevi pokazivač tipa čvora, a treće polje je desni pokazivač tipa čvora.

Da biste saznali više o stablu binarnog pretraživanja, kliknite na donju vezu:

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

AVL stablo

To je jedan od tipova binarnog stabla, ili možemo reći da je to varijanta binarnog stabla pretraživanja. AVL stablo zadovoljava svojstvo binarno stablo kao i od binarno stablo pretraživanja . To je samobalansirajuće binarno stablo pretraživanja koje je izumio Adelson Velsky Lindas . Ovdje samobalansiranje znači balansiranje visina lijevog podstabla i desnog podstabla. Ovo balansiranje se mjeri u smislu faktor ravnoteže .

Stablo možemo smatrati AVL stablom ako stablo poštuje binarno stablo pretraživanja kao i faktor ravnoteže. Faktor ravnoteže može se definirati kao razlika između visine lijevog podstabla i visine desnog podstabla . Vrijednost faktora ravnoteže mora biti 0, -1 ili 1; stoga bi svaki čvor u AVL stablu trebao imati vrijednost faktora ravnoteže kao 0, -1 ili 1.

Da biste saznali više o AVL stablu, kliknite donju poveznicu:

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

Crveno-crno drvo

Crveno-crno drvo je stablo binarnog pretraživanja. Preduvjet crveno-crnog stabla je da znamo za binarno stablo pretraživanja. U stablu binarnog pretraživanja, vrijednost lijevog podstabla trebala bi biti manja od vrijednosti tog čvora, a vrijednost desnog podstabla trebala bi biti veća od vrijednosti tog čvora. Kao što znamo da je vremenska složenost binarnog pretraživanja u prosječnom slučaju log₂n, najbolji slučaj je O(1), a najgori slučaj je O(n).

Kada se bilo koja operacija izvodi na stablu, želimo da naše stablo bude uravnoteženo tako da sve operacije poput pretraživanja, umetanja, brisanja, itd., traju manje vremena, a sve te operacije će imati vremensku složenost log₂n.

Crveno-crno drvo je samobalansirajuće binarno stablo pretraživanja. AVL stablo je također stablo binarnog pretraživanja za balansiranje visine zašto nam je potrebno crveno-crno stablo . U AVL stablu ne znamo koliko bi rotacija bilo potrebno za balansiranje stabla, ali u crveno-crnom stablu potrebne su najviše 2 rotacije za balansiranje stabla. Sadrži jedan dodatni bit koji predstavlja crvenu ili crnu boju čvora kako bi se osiguralo balansiranje stabla.

10 od 10

Raskošeno drvo

Struktura podataka splay stabla također je binarno stablo pretraživanja u kojem se nedavno pristupani element postavlja na korijensku poziciju stabla izvođenjem nekih operacija rotacije. Ovdje, razbacivanje znači nedavno pristupani čvor. To je samouravnoteženje binarno stablo pretraživanja koje nema eksplicitni uvjet ravnoteže poput AVL drvo.

Moguće je da visina stabla iskrivljenja nije uravnotežena, tj. visina lijevog i desnog podstabla može se razlikovati, ali operacije u stablu iskrivljenja slijede redoslijed smiriti vrijeme gdje n je broj čvorova.

Splay stablo je uravnoteženo stablo, ali se ne može smatrati visinski uravnoteženim stablom jer se nakon svake operacije izvodi rotacija koja dovodi do uravnoteženog stabla.

Treap

Struktura podataka Treap proizašla je iz strukture podataka Tree i Heap. Dakle, sadrži svojstva i strukture podataka Tree i Heap. U stablu binarnog pretraživanja svaki čvor na lijevom podstablu mora biti jednak ili manji od vrijednosti korijenskog čvora, a svaki čvor na desnom podstablu mora biti jednak ili veći od vrijednosti korijenskog čvora. U strukturi podataka gomile, i desno i lijevo podstablo sadrže veće ključeve od korijena; stoga možemo reći da korijenski čvor sadrži najnižu vrijednost.

U strukturi podataka treap, svaki čvor ima oboje ključ i prioritet gdje se ključ izvodi iz binarnog stabla pretraživanja, a prioritet se izvodi iz strukture podataka gomile.

The Treap struktura podataka slijedi dva svojstva koja su navedena u nastavku:

• Desno dijete čvora>=trenutni čvor i lijevo dijete čvora<=current node (binary tree)< li>
• Djeca bilo kojeg podstabla moraju biti veća od čvora (hrpe)

B-stablo

B-stablo je uravnoteženo m-put drvo gdje m definira redoslijed stabla. Do sada smo čitali da čvor sadrži samo jedan ključ, ali b-stablo može imati više od jednog ključa i više od 2 djece. Uvijek održava sortirane podatke. U binarnom stablu, moguće je da lisni čvorovi mogu biti na različitim razinama, ali u b-stablu, svi lisni čvorovi moraju biti na istoj razini.

Ako je poredak m tada čvor ima sljedeća svojstva:

• Svaki čvor u b-stablu može imati maksimum m djece
• Za najmanje djece, listni čvor ima 0 djece, korijenski čvor ima najmanje 2 djece, a unutarnji čvor ima minimalnu gornju granicu od m/2 djece. Na primjer, vrijednost m je 5 što znači da čvor može imati 5 djece, a unutarnji čvorovi mogu sadržavati najviše 3 djece.
• Svaki čvor ima najviše (m-1) ključeva.

Korijenski čvor mora sadržavati najmanje 1 ključ, a svi ostali čvorovi moraju sadržavati najmanje strop od m/2 minus 1 ključevi.