Nelinearna struktura podataka sastoji se od skupa elemenata koji su raspoređeni na ravnini što znači da ne postoji takav slijed između elemenata koji postoje u linearnoj podatkovnoj strukturi.
Tablica usporedbe
| Osnova za usporedbu | drvo | Grafikon |
|---|---|---|
| Staza | Samo jedan između dva vrha. | Dopušteno je više od jednog puta. |
| Root čvor | Ima točno jedan korijenski čvor. | Graf nema korijenski čvor. |
| petlje | Nikakve petlje nisu dopuštene. | Graf može imati petlje. |
| Složenost | Manje složeno | Kompleksnija usporedba |
| Tehnike proboja | Predbilježbe, narudžbe i narudžbe. | Pretraživanje po dubini i pretraživanje dubine. |
| Broj rubova | n-1 (gdje je n broj čvorova) | Nije definirano |
| Vrsta modela | hijerarhijski | Mreža |
Definicija stabla
Stablo je konačna zbirka podataka koje se obično nazivaju čvorovima. Kao što je gore spomenuto, stablo je nelinearna podatkovna struktura koja raspoređuje stavke podataka u sortiranom redoslijedu. Koristi se za prikaz hijerarhijske strukture između različitih elemenata podataka i organizira podatke u grane koje se odnose na informacije. Dodavanje novog ruba u stablo rezultira formiranjem petlje ili kruga.
Postoji nekoliko vrsta stabala kao što su binarno stablo, binarno stablo pretraživanja, AVL stablo, binarno stablo s navojem, B-stablo, itd. Kompresija podataka, pohrana datoteka, manipulacija aritmetičkim izrazom i stabla igre su neke od primjena stabla struktura podataka.
Svojstva stabla:
- Na vrhu stabla nalazi se određeni čvor poznat kao korijen stabla.
- Preostale stavke podataka podijeljene su na disjunktne podskupine koje se nazivaju podstablo.
- Stablo je prošireno u visinu prema dnu.
- Stablo mora biti povezano što znači da mora postojati put od jednog korijena do svih drugih čvorova.
- Ne sadrži nikakve petlje.
- Stablo ima n-1 rubova.
Postoje različiti pojmovi povezani s drvećem kao što su terminalni čvor, rub, razina, stupanj, dubina, šuma, itd. Među tim pojmovima, neki od njih su opisani u nastavku.
- Edge - Linija koja povezuje dva čvora.
- Razina - Stablo je podijeljeno na razine tako da je korijenski čvor na razini 0. Zatim, njegova neposredna djeca su na razini 1, a njezina neposredna djeca su na razini 2 i tako dalje do terminala ili čvorišta lista.
- Stupanj - To je broj podstabala čvora u danom stablu.
- Dubina - To je maksimalna razina bilo kojeg čvora u danom stablu i također poznata kao visina .
- Terminalni čvor - čvor na najvišoj razini je terminalni čvor, dok su drugi čvorovi osim terminalnog i korijenskog čvora poznati kao ne-terminalni čvorovi.
Definicija grafikona
Graf je također matematička nelinearna struktura podataka koja može predstavljati različite vrste fizičke strukture. Sastoji se od skupine vrhova (ili čvorova) i skupa rubova koji povezuju dva vrha. Vertice na grafikonu prikazane su kao točke ili krugovi, a rubovi su prikazani kao lukovi ili segmenti. Rub je predstavljen s E (v, w) gdje su v i w parovi vrhova. Uklanjanje ruba iz kruga ili povezanog grafikona stvara podgraf koji je stablo.
Grafovi su razvrstani u različite kategorije kao što su usmjereni, ne-usmjereni, povezani, nepovezani, jednostavni i višestruki. Računalna mreža, transportni sustav, grafikon društvenih mreža, električni krugovi i projektno planiranje neke su od primjena strukture podataka grafova. Također se koristi u tehnici upravljanja koja se naziva PERT (procjena i pregled programa) i CPM (metoda kritičnog puta) u kojoj se analizira struktura grafa.
Svojstva grafikona:
- Vrh u grafu može se povezati s bilo kojim brojem drugih vrhova koristeći rubove.
- Rub može biti dvosmjerno ili usmjereno.
- Rub može biti ponderiran.
U grafu također koristimo različite izraze kao što su susjedni vrhovi, put, ciklus, stupanj, povezan graf, potpuni graf, ponderirani graf, itd. Razumimo neke od ovih pojmova.
- Susjedni vrhovi - vrh a je susjedan uz vrh b ako postoji rub (a, b) ili (b, a).
- Put - Put od slučajnog vrha w je susjedni slijed vrhova.
- Ciklus - To je staza na kojoj su prvi i zadnji vrh jednaki.
- Stupanj - To je broj rubova koji se pojavljuju na vrhu.
- Povezani grafikon - Ako postoji put od slučajnog vrha do bilo kojeg drugog vrha, tada je taj graf poznat kao povezan graf.
Ključne razlike između stabla i grafikona
- U stablu postoji samo jedan put između bilo koje dvije točke, dok graf može imati jednosmjerne i dvosmjerne staze između čvorova.
- U stablu postoji točno jedan korijenski čvor, a svako dijete može imati samo jednog roditelja. Nasuprot tome, u grafu nema koncepta korijenskog čvora.
- Stablo ne može imati petlje i samo-petlje, dok grafikon može imati petlje i samo-petlje.
- Grafovi su složeniji jer mogu imati petlje i samo-petlje. Nasuprot tome, stabla su jednostavna u odnosu na grafikon.
- Stablo se prelazi pomoću tehnika prije narudžbe, naručenih i naknadnih narudžbi. S druge strane, za zaobilaženje grafikona koristimo BFS (Breadth First Search) i DFS (dubinsko prvo traženje).
- Stablo može imati n-1 rubova. Naprotiv, u grafu nema unaprijed određenog broja rubova i to ovisi o grafu.
- Stablo ima hijerarhijsku strukturu, dok graf ima mrežni model.
Zaključak
Graf i stablo su nelinearna struktura podataka koja se koristi za rješavanje raznih složenih problema. Graf je skupina vrhova i rubova gdje rub povezuje par vrhova, dok se drvo smatra minimalno povezanim grafom koji mora biti povezan i slobodan od petlji.
