Nelinearna podatkovna struktura je sestavljena iz zbirke elementov, ki so porazdeljeni na ravnino, kar pomeni, da med elementi ni takšnega zaporedja, kot obstaja v linearni podatkovni strukturi.
Primerjalna tabela
| Podlaga za primerjavo | Drevo | Graf |
|---|---|---|
| Pot | Samo ena med dvema točkama. | Dovoljena je več kot ena pot. |
| Korensko vozlišče | Ima natančno eno korensko vozlišče. | Graf nima korenskega vozlišča. |
| Zanke | Nobene zanke niso dovoljene. | Graf ima lahko zanke. |
| Zapletenost | Manj zapleteno | Kompleksnejša primerjava |
| Tehnike prečkanja | Prednaročilo, naročilo in naročilo. | Iskanje po širini in iskanje po globini. |
| Število robov | n-1 (kjer je n število vozlišč) | Ni določeno |
| Vrsta modela | Hierarhično | Omrežje |
Opredelitev drevesa
Drevo je končna zbirka podatkovnih elementov, ki se običajno imenujejo vozlišča. Kot je navedeno zgoraj, je drevo nelinearna podatkovna struktura, ki ureja postavke podatkov v razvrščenem vrstnem redu. Uporablja se za prikaz hierarhične strukture med različnimi podatkovnimi elementi in organizira podatke v veje, ki povezujejo informacije. Dodajanje novega roba v drevo povzroči nastanek zanke ali vezja.
Obstaja več vrst dreves, kot so binarno drevo, binarno drevo iskanja, drevo AVL, binarno drevo z navojem, B-drevo, itd. Stiskanje podatkov, shranjevanje datotek, manipulacija aritmetičnega izraza in drevesa iger so del aplikacije drevesa podatkovne strukture.
Lastnosti drevesa:
- Na vrhu drevesa je označeno vozlišče, znano kot koren drevesa.
- Preostale postavke podatkov so razdeljene na nepovezane podskupine, ki se imenujejo poddrevo.
- Drevo se razširi v višino proti dnu.
- Drevo mora biti povezano, kar pomeni, da mora obstajati pot od enega korena do vseh drugih vozlišč.
- Ne vsebuje nobenih zank.
- Drevo ima n-1 robov.
Obstajajo različni izrazi, povezani z drevesi, kot so terminalsko vozlišče, rob, raven, stopnja, globina, gozd itd. Med temi izrazi, nekateri so opisani spodaj.
- Edge - črta, ki povezuje dve vozlišču.
- Raven - drevo je razdeljeno na ravni tako, da je korensko vozlišče na ravni 0. Nato so njegovi neposredni otroci na ravni 1 in njegovi neposredni otroci so na ravni 2 in tako naprej do terminala ali vozlišča listov.
- Stopnja - To je število podplatov vozlišča v danem drevesu.
- Globina - je najvišja raven katerega koli vozlišča v danem drevesu in je znana tudi kot višina .
- Končno vozlišče - Vozlišče najvišje ravni je terminalsko vozlišče, medtem ko so druga vozlišča, razen terminalnega in korenskega vozlišča, znana kot ne-terminalna vozlišča.
Opredelitev grafa
Graf je tudi matematična nelinearna podatkovna struktura, ki lahko predstavlja različne vrste fizične strukture. Sestavljen je iz skupine tock (ali vozlišc) in niza robov, ki povezujejo obe tocki. Vertice na grafu so predstavljene kot točke ali krogovi in robovi so prikazani kot loki ali segmenti. Rob je predstavljen z E (v, w), kjer sta v in w pari tock. Odstranitev roba iz vezja ali povezanega grafa ustvari podgraf, ki je drevo.
Grafi so razvrščeni v različne kategorije, kot so usmerjeni, ne-usmerjeni, povezani, nepovezani, preprosti in več-grafični. Računalniško omrežje, transportni sistem, graf socialnih omrežij, električni tokokrogi in projektno načrtovanje so nekatere od aplikacij podatkovne strukture grafov. Uporablja se tudi v tehniki upravljanja, imenovani kot PERT (ocenjevanje in pregledovanje programov) in CPM (metoda kritične poti), v kateri se analizira struktura grafa.
Lastnosti grafa:
- Vrstico v grafu lahko povežemo s poljubnim številom drugih tock z robovi.
- Rob je lahko dvosmeren ali usmerjen.
- Rob se lahko uteži.
V grafu uporabljamo tudi različne izraze, kot so sosednja vozlišča, pot, cikel, stopnja, povezan graf, celoten graf, uteženi graf itd. Razumimo nekatere od teh izrazov.
- Sosednja tocka - tocka a je sosednja tocki b, ce obstaja rob (a, b) ali (b, a).
- Pot - Pot iz naključnega vozlišča w je sosednje zaporedje tock.
- Cycle - To je pot, kjer sta prva in zadnja tocka enaka.
- Stopnja - To je število robov, ki se pojavijo na vozlišču.
- Povezani graf - Če obstaja pot od naključnega vozlišča do katere koli druge točke, je ta graf znan kot povezan graf.
Ključne razlike med drevesom in grafom
- V drevesu obstaja samo ena pot med dvema točkama, medtem ko lahko graf ima enosmerne in dvosmerne poti med vozlišči.
- V drevesu je točno eno korensko vozlišče in vsak otrok lahko ima samo enega od staršev. V nasprotju s tem v grafu ni koncepta korenskega vozlišča.
- Drevo ne more imeti zanke in samoprepusti, medtem ko lahko graf ima zanke in samopovezave.
- Grafi so bolj zapleteni, saj imajo lahko zanke in samopovezave. V nasprotju s tem so drevesa preprosta v primerjavi z grafom.
- Drevo se prečka s pre-order, in-order in post-order tehnikami. Po drugi strani za prečkanje grafa uporabljamo BFS (prvo iskanje po širini) in DFS (prvo iskanje po globini).
- Drevo ima lahko n-1 robov. Nasprotno, v grafu ni vnaprej določenega števila robov in je odvisno od grafa.
- Drevo ima hierarhično strukturo, graf pa model omrežja.
Zaključek
Graf in drevo sta nelinearna podatkovna struktura, ki se uporablja za reševanje različnih kompleksnih problemov. Graf je skupina tock in robov, kjer rob povezuje par tock, medtem ko je drevo obravnavano kot minimalno povezan graf, ki mora biti povezan in brez zank.
