Epälineaarinen datarakenne koostuu kokoelmasta elementeistä, jotka jakautuvat tasolle, mikä tarkoittaa, että elementtien välillä ei ole sellaista sekvenssiä, joka on lineaarisessa datarakenteessa.
Vertailukaavio
| Vertailun perusteet | Puu | kaavio |
|---|---|---|
| polku | Vain yksi kahden pisteen välillä. | Useampi kuin yksi polku on sallittu. |
| Root-solmu | Siinä on täsmälleen yksi juurisolmu. | Kaaviossa ei ole juuri solmua. |
| silmukat | Silmukoita ei sallita. | Kuvassa voi olla silmukoita. |
| Monimutkaisuus | Vähemmän monimutkainen | Monimutkaisempi verrattuna |
| Traversal-tekniikat | Ennakkotilaus, järjestys ja postimyynti. | Ensimmäisen haun ja syvyyden ensimmäinen haku. |
| Reunojen lukumäärä | n-1 (jossa n on solmujen lukumäärä) | Ei määritelty |
| Mallin tyyppi | Hierarkkinen | verkko |
Puun määritelmä
Puu on rajallinen kokoelma dataelementtejä, joita kutsutaan yleensä solmuiksi. Kuten edellä on mainittu, puu on epälineaarinen tietorakenne, joka järjestää datayksiköt lajitellussa järjestyksessä. Sitä käytetään osoittamaan hierarkkinen rakenne eri tietoelementtien välillä ja järjestää tiedot haaroihin, jotka liittyvät informaatioon. Uuden reunan lisääminen puuhun johtaa silmukan tai piirin muodostumiseen.
Puutyyppejä ovat esimerkiksi binaaripuu, binäärinen hakupuu, AVL-puu, kierteinen binaaripuu, B-puu jne. Tiedon pakkaaminen, tiedostojen tallennus, aritmeettisen lausekkeen käsittely ja pelipuut ovat osa puun sovellusta tietorakenne.
Puun ominaisuudet:
- Puun yläreunassa on nimetty solmu, joka tunnetaan puun juurena.
- Jäljelle jäävät tiedot on jaettu osajoukko-osajoukkoihin viitaten aliverkkoon.
- Puu laajenee korkeutta kohti pohjaa.
- Puu on kytkettävä, mikä tarkoittaa, että on oltava polku yhdestä juuresta kaikkiin muihin solmuihin.
- Se ei sisällä silmukoita.
- Puun reunat ovat n-1.
Puissa on erilaisia termejä, kuten terminaalisolmu, reuna, taso, aste, syvyys, metsä jne. Näistä termeistä osa niistä on kuvattu alla.
- Edge - Linja, joka yhdistää kaksi solmua.
- Taso - Puu on jaettu tasoille siten, että juurisolmu on tasolla 0. Sitten sen välittömät lapset ovat tasolla 1, ja sen välittömät lapset ovat tasolla 2 ja niin edelleen päätelaitteeseen tai lehtisolmuun asti.
- Tutkinto - Se on tietyn puun solmujen lukumäärä.
- Syvyys - Se on minkä tahansa solmun maksimitaso tietyssä puussa ja tunnetaan myös nimellä korkeus .
- Päätelaite - Korkeimman tason solmu on päätelaite, kun taas muut solmut, lukuun ottamatta päätelaitteita ja root-solmua, tunnetaan ei-terminaalisina solmuina.
Graafin määritelmä
Kaavio on myös matemaattinen epälineaarinen datarakenne, joka voi edustaa erilaisia fyysisiä rakenteita. Se koostuu joukosta pisteitä (tai solmuja) ja reunoja, jotka yhdistävät nämä kaksi huippua. Kaavion pisteet näkyvät pisteenä tai ympyrät ja reunat näkyvät kaarina tai viivasegmentteinä. Reunaa edustaa E (v, w), jossa v ja w ovat huippupareja. Reunan poistaminen piiristä tai kytketystä kaaviosta luo alikuvan, joka on puu.
Kaaviot luokitellaan eri luokkiin, kuten suunnattu, ei-suunnattu, yhdistetty, ei-liitetty, yksinkertainen ja monikuvaaja. Tietokoneverkko, kuljetusjärjestelmä, sosiaalisen verkoston kuvaaja, sähköpiirit ja projektisuunnittelu ovat eräitä kaavion tietorakenteen sovelluksia. Sitä käytetään myös hallintatekniikassa, jonka nimi on PERT (ohjelman arviointi ja tarkistusmenetelmä) ja CPM (kriittinen polkumenetelmä), jossa käyrästruktuuri analysoidaan.
Kaavion ominaisuudet:
- Graafin kärki voidaan liittää mihin tahansa muuhun pisteeseen käyttämällä reunoja.
- Reunaa voidaan ohjata tai suunnata.
- Reunaa voidaan painottaa.
Kaaviossa käytämme myös erilaisia termejä, kuten vierekkäisiä pisteitä, polkua, sykliä, astetta, liitettyä kuvaajan, täydellisen kaavion, painotetun kaavion jne. Ymmärrämme joitakin näistä termeistä.
- Vierekkäiset pisteet - Piste a on vieressä pisteeseen b, jos on reuna (a, b) tai (b, a).
- Polku - Polku satunnaisesta pisteestä w on viereinen pisteiden sekvenssi.
- Cycle - Se on polku, jossa ensimmäinen ja viimeinen huippu ovat samat.
- Tutkinto - Se on useita reunoja, jotka tulevat kärjessä.
- Yhdistetty kuvaaja - Jos satunnaisesta huippupisteestä toiseen polkuun on olemassa polku, kyseinen kaavio tunnetaan yhdistetynä kuvaajana.
Puun ja graafin väliset keskeiset erot
- Puussa on olemassa vain yksi polku kaikkien kahden pisteiden välillä, kun taas kaaviossa voi olla yksisuuntaisia ja kaksisuuntaisia polkuja solmujen välillä.
- Puussa on juuri yksi juurisolmu, ja jokaisella lapsella voi olla vain yksi vanhempi. Vastaanotettuna, kaaviossa ei ole juurisolmun käsitettä.
- Puun ei voi olla silmukoita ja itsesilmukoita, kun taas kaaviossa voi olla silmukoita ja itsesilmukoita.
- Kuviot ovat monimutkaisempia, sillä niissä voi olla silmukoita ja itsesilmukoita. Sitä vastoin puut ovat yksinkertaisia verrattuna kuvioon.
- Puu kulkee ennakkotilaus-, järjestys- ja jälkitilaustekniikalla. Toisaalta käytämme kaavion kulkua varten BFS: ää (Breadth First Search) ja DFS: tä (Depth First Search).
- Puun voi olla n-1 reunoja. Päinvastoin, kaaviossa ei ole ennalta määritettyä määrää reunoja, ja se riippuu kaaviosta.
- Puun hierarkkinen rakenne, kun taas kaaviossa on verkko-malli.
johtopäätös
Kuvaaja ja puu ovat epälineaarisia tietorakenteita, joita käytetään erilaisten monimutkaisten ongelmien ratkaisemiseen. Graafi on joukko pisteitä ja reunoja, joissa reuna yhdistää pari pisteitä, kun taas puuta pidetään minimaalisesti yhdistetynä kuvaajana, joka on liitettävä ja vapautettava silmukoista.
