Mittelineaarne andmestruktuur koosneb elementidest, mis on jaotatud tasapinnal, mis tähendab, et elementide vahel puudub selline järjestus, nagu see on lineaarses andmestruktuuris.
Võrdluskaart
| Võrdluse alus | Puu | Graafik |
|---|---|---|
| Tee | Ainult üks kahe tipu vahel. | Lubatud on rohkem kui üks tee. |
| Juursõlm | Sellel on täpselt üks juursõlm. | Graafil ei ole root sõlme. |
| Silmus | Silmus ei ole lubatud. | Graafil võib olla silmuseid. |
| Keerukus | Vähem keeruline | Keerulisem on keerulisem |
| Liigutustehnikad | Eeltellimine, järjekorras ja järeltellimus. | Esimene otsing ja sügavuse esimene otsing. |
| Servade arv | n-1 (kus n on sõlmede arv) | Ei ole defineeritud |
| Mudelitüüp | Hierarhiline | Võrk |
Puu määratlus
Puu on piiratud kogum andmeid, mida tavaliselt nimetatakse sõlmedeks. Nagu ülalpool mainitud, on puu mittelineaarne andmestruktuur, mis korraldab andmete sorteerimise järjekorras. Seda kasutatakse hierarhilise struktuuri näitamiseks erinevate andmeelementide vahel ja andmete organiseerimiseks filiaalidesse, mis seostavad informatsiooni. Uue serva lisamine puusse toob kaasa silmuse või ahela moodustumise.
Puud on mitut tüüpi, näiteks binaarne puu, binaarotsingupuu, AVL-puu, keermestatud binaarpuu, B-puu jne. andmete struktuur.
Puu omadused:
- Puu ülaosas on määratud puu, mida nimetatakse puu juureks.
- Ülejäänud andmeühikud on jagatud lahutatud alamrühmadeks, viidates kui alamtagusele.
- Puu laieneb põhja poole.
- Tuleb ühendada puu, mis tähendab, et peab olema tee ühest juurest kõigisse teistesse sõlmedesse.
- See ei sisalda silmuseid.
- Puudel on n-1 servad.
Puudega on seotud mitmed terminid, nagu terminali sõlm, serv, tase, aste, sügavus, mets jne.
- Edge - joon, mis ühendab kahte sõlme.
- Tase - puu jaotatakse tasemeteks selliselt, et juuremoodul on 0. tasemel. Seejärel on tema otsesed lapsed tasemel 1 ja selle otsesed lapsed on tasemel 2 ja nii edasi kuni terminali või lehe noodini.
- Kraad - see on sõlme alampuude arv antud puus.
- Sügavus - see on mis tahes sõlme maksimaalne tase antud puus ja tuntud ka kui kõrgus .
- Terminali sõlme - kõrgeima taseme sõlme terminali sõlme, samas kui teised sõlmed, välja arvatud terminali ja juure sõlme, on tuntud kui mitteterminalsõlmed.
Graafi määratlus
Graafik on ka matemaatiline mittelineaarne andmestruktuur, mis võib esindada erinevaid füüsilisi struktuure. See koosneb tipudest (või sõlmedest) ja servadest, mis ühendavad kaks tippu. Graafil olevad vertikaalid on esitatud punktina või ringidena ja servadena näidatakse kaared või joonesegmendid. Serva esindab E (v, w), kus v ja w on tipude paarid. Servi või ühendatud graafiku serva eemaldamine loob alamgraafi, mis on puu.
Graafid on liigitatud erinevatesse kategooriatesse, nagu näiteks suunatud, mitte-suunatud, ühendatud, mitteühendatud, lihtne ja mitme graafikuga. Arvutivõrk, transpordisüsteem, sotsiaalse võrgustiku graafik, elektriskeemid ja projekti planeerimine on graafikandmete struktuuri mõned rakendused. Seda kasutatakse ka juhtimismeetodis, mida nimetatakse PERT-ks (programmi hindamine ja ülevaatustehnika) ja CPM-i (kriitilise tee meetod), milles graafikstruktuuri analüüsitakse.
Graafiku omadused:
- Graafi tipu saab ühendada mis tahes arvu teiste tippudega, kasutades servi.
- Serva saab suunata või suunata.
- Serva saab kaaluda.
Graafikus kasutame ka erinevaid termineid, nagu kõrvuti asetsevad tipud, tee, tsükkel, kraad, ühendatud graafik, täielik graafik, kaalutud graafik jne. Mõistame mõningaid neid termineid.
- Kõrvuti asetsevad tipud - tipp on a tipuga b, kui on serv (a, b) või (b, a).
- Tee - juhusliku tipu w tee on kõrvuti asetsev tippude järjestus.
- Tsükkel - See on tee, kus esimesed ja viimased tipud on samad.
- Kraad - see on mitu serva, mis asetseb tipus.
- Ühendatud graaf - kui juhusliku tipu tipust teise tippu on olemas tee, siis on see graafik tuntud ühendatud graafina.
Puu ja graafiku vahelised peamised erinevused
- Puudes eksisteerib ainult üks tee kahe tipu vahel, samas kui graafikul võivad olla üksiksuunalised ja kahesuunalised teed sõlmede vahel.
- Puudes on täpselt üks juuremoodul ja igal lapsel võib olla ainult üks vanem. Seevastu graafikus pole juure sõlme kontseptsiooni.
- Puudel ei saa olla silmuseid ja isesilmusi, samas kui graafikul võivad olla silmused ja isesilmused.
- Graafikud on keerulisemad, kuna neil võivad olla silmad ja isesilmused. Seevastu on puud graafikuga võrreldes lihtsad.
- Puu läbib eelregistreerimise, järjekorra ja järeltellimise tehnikat. Teisest küljest kasutame graafiku liikumise puhul BFS-i (Breadth First Search) ja DFS-i (Depth First Search).
- Puudel võib olla n-1 servi. Vastupidi, graafikus puudub eelnevalt määratud servade arv ja see sõltub graafikust.
- Puudel on hierarhiline struktuur, samas kui graafikul on võrgumudel.
Järeldus
Graaf ja puu on mittelineaarne andmestruktuur, mida kasutatakse erinevate keeruliste probleemide lahendamiseks. Graaf on tippude ja servade rühm, kus serv ühendab tipupiike, samas kui puu loetakse minimaalselt ühendatud graafiks, mis peab olema ühendatud ja vaba silmustest.
