En ikke-lineær datastruktur består av en samling av elementene som er fordelt på et fly som betyr at det ikke finnes en slik sekvens mellom elementene som den eksisterer i en lineær datastruktur.
Sammenligningstabel
| Grunnlag for sammenligning | Tre | Kurve |
|---|---|---|
| Sti | Bare en mellom to hjørner. | Mer enn en sti er tillatt. |
| Rotnøkkel | Den har nøyaktig en rotnode. | Graf har ikke en rotnode. |
| Loops | Ingen løkker er tillatt. | Graf kan ha løkker. |
| kompleksitet | Mindre kompleks | Mer komplisert relativt |
| Traversal teknikker | Pre-order, In-order og Post-order. | Bredde-første søk og dybde-første søk. |
| Antall kanter | n-1 (hvor n er antall noder) | Ikke definert |
| Modell type | Hierarkisk | Network |
Definisjon av tre
Et tre er en endelig samling av dataposter som vanligvis betegnes som noder. Som nevnt ovenfor er et tre en ikke-lineær datastruktur som ordner dataposter i rekkefølge. Det brukes til å vise en hierarkisk struktur mellom de ulike dataelementene og organiserer dataene i grener som relaterer informasjonen. Tillegg av en ny kant i et tre resulterer i en formasjon av sløyfen eller kretsen.
Det finnes flere typer trær som et binært tre, binært søketre, AVL-tre, gjenget binært tre, B-tre osv. Datakomprimering, arkivering, manipulering av det aritmetiske uttrykket og spilltrærne er noe av bruken av treet data struktur.
Egenskaper av treet:
- Det er utpekt knutepunkt øverst på treet kjent som en rot av treet.
- De gjenværende datapostene er delt inn i disjoint undergrupper, referert til som subtree.
- Træret er utvidet i høyden mot bunnen.
- Et tre må være koblet, noe som betyr at det må være en sti fra en rot til alle andre noder.
- Den inneholder ingen løkker.
- Et tre har n-1 kanter.
Det er ulike termer knyttet til trær som terminal node, kant, nivå, grad, dybde, skog, etc. Blant disse vilkårene, er noen av dem beskrevet nedenfor.
- Kant - En linje som forbinder to noder.
- Nivå - Et tre er delt inn i nivåer på en slik måte at rotnoden er på nivå 0. Deretter er de nærmeste barna på nivå 1, og de nærmeste barna er på nivå 2 og så videre opp til terminalen eller bladknuten.
- Grad - Det er antall subtreer av en node i et gitt tre.
- Dybde - Det er maksimumsnivået til en node i et gitt tre og også kjent som høyde .
- Terminal node - Høyeste nivå node er terminal node mens andre noder unntatt terminal og root node er kjent som ikke-terminale noder.
Definisjon av graf
En graf er også en matematisk ikke-lineær datastruktur som kan representere ulike typer fysisk struktur. Den består av en gruppe vertikaler (eller noder) og sett med kanter som forbinder de to vertikaler. Vertikaler på grafen er representert som punkt eller sirkler og kanter vises som buer eller linjesegmenter. En kant er representert ved E (v, w) hvor v og w er parene av vertikaler. Fjerning av en kant fra en krets eller tilkoblet graf skaper en subgraph som er et tre.
Grafer er klassifisert i ulike kategorier, for eksempel instruert, ikke-rettet, tilkoblet, ikke-tilkoblet, enkel og multi-graf. Datanettverk, transportsystem, sosiale nettverkskort, elektriske kretser og prosjektplanlegging er noen av bruksområdene til grafdatastruktur. Det er også ansatt i ledelsesteknikk kalt PERT (program evaluering og gjennomgangsteknikk) og CPM (kritisk banemetode) der grafstrukturen analyseres.
Egenskaper av en graf:
- Et toppunkt i en graf kan kobles til et hvilket som helst antall andre vinkler ved hjelp av kanter.
- En kant kan bli direkte eller rettet.
- En kant kan vektes.
I graf bruker vi også ulike termer som tilstøtende kryss, vei, syklus, grad, koblet graf, komplett graf, vektet graf etc. La oss forstå noen av disse vilkårene.
- Tilgrensende hjørner - Et toppunkt a ligger ved siden av vertex b hvis det er en kant (a, b) eller (b, a).
- Sti - En sti fra et tilfeldig vertex w er en tilstøtende sekvens av punkter.
- Syklus - Det er en sti hvor de første og siste kryssene er de samme.
- Grad - Det er en rekke kanter hendelse på et toppunkt.
- Koblet graf - Hvis det finnes en bane fra et tilfeldig vertex til et annet toppunkt, så er grafen kjent som en koblet graf.
Viktige forskjeller mellom tre og graf
- I et tre eksisterer det bare en bane mellom noen to hjørner, mens en graf kan ha enveis og toveisbaner mellom knutepunktene.
- I treet er det akkurat en rotnode, og hvert barn kan bare ha en forelder. I motsetning til, i en graf, er det ikke noe konsept for rotnoden.
- Et tre kan ikke ha løkker og selvløkker mens grafen kan ha sløyfer og selvløkker.
- Grafer er mer kompliserte, da det kan ha sløyfer og selvløkker. Derimot er trærne enkle sammenlignet med grafen.
- Træret er krysset ved hjelp av forhåndsordre-, ordre- og postorderteknikker. På den annen side bruker vi BFS (bredde første søk) og DFS (dybde første søk) for graf-traversal.
- Et tre kan ha n-1 kanter. Tvert imot, i grafen, er det ikke forhåndsdefinert antall kanter, og det avhenger av grafen.
- Et tre har en hierarkisk struktur mens grafen har en nettverksmodell.
Konklusjon
Graf og tre er den ikke-lineære datastrukturen som brukes til å løse ulike komplekse problemer. En graf er en gruppe av vinkler og kanter hvor en kant forbinder et par krysser, mens et tre betraktes som en minimal koblet graf som må være koblet og fri fra sløyfer.
