Vi leser de lineære datastrukturene som en matrise, koblet liste, stabel og kø der alle elementene er ordnet på en sekvensiell måte. De ulike datastrukturene brukes for ulike typer data.

Noen faktorer vurderes for valg av datastruktur:

Hvilken type data må lagres?: Det kan være en mulighet for at en viss datastruktur kan passe best for en slags data.Driftskostnader:Hvis vi ønsker å minimere kostnadene for operasjonene for de hyppigst utførte operasjonene. For eksempel har vi en enkel liste som vi må utføre søkeoperasjonen på; så kan vi lage en matrise der elementene er lagret i sortert rekkefølge for å utføre binært søk . Det binære søket fungerer veldig raskt for den enkle listen da det deler søkeområdet i to.Minnebruk:Noen ganger ønsker vi en datastruktur som bruker mindre minne.

Et tre er også en av datastrukturene som representerer hierarkiske data. Anta at vi ønsker å vise de ansatte og deres stillinger i hierarkisk form, så kan det representeres som vist nedenfor:

Treet ovenfor viser organisasjonshierarki av et eller annet selskap. I strukturen ovenfor, john er den administrerende direktør av selskapet, og John har to direkte rapporter navngitt som Steve og Rohan . Steve har tre direkte rapporter navngitt Lee, Bob, Ella hvor Steve er leder. Bob har to direkte rapporter navngitt Skal og Emma . Emma har to direkte rapporter navngitt Tom og Raj . Tom har en direkterapport navngitt Regning . Denne spesielle logiske strukturen er kjent som en Tre . Strukturen ligner på det virkelige treet, så det heter a Tre . I denne strukturen rot er på toppen, og grenene beveger seg i nedadgående retning. Derfor kan vi si at Tree-datastrukturen er en effektiv måte å lagre dataene på en hierarkisk måte.

La oss forstå noen nøkkelpunkter i tredatastrukturen.

for loop java

• En tredatastruktur er definert som en samling av objekter eller enheter kjent som noder som er koblet sammen for å representere eller simulere hierarki.
• En tredatastruktur er en ikke-lineær datastruktur fordi den ikke lagres på en sekvensiell måte. Det er en hierarkisk struktur ettersom elementer i et tre er ordnet i flere nivåer.
• I tredatastrukturen er den øverste noden kjent som en rotnode. Hver node inneholder noen data, og data kan være av hvilken som helst type. I trestrukturen ovenfor inneholder noden navnet på den ansatte, så datatypen vil være en streng.
• Hver node inneholder noen data og koblingen eller referansen til andre noder som kan kalles barn.

Noen grunnleggende termer som brukes i datastrukturen i treet.

La oss vurdere trestrukturen, som er vist nedenfor:

I strukturen ovenfor er hver node merket med et eller annet nummer. Hver pil vist i figuren ovenfor er kjent som en link mellom de to nodene.

Rot:Rotnoden er den øverste noden i trehierarkiet. Med andre ord er rotnoden den som ikke har noen forelder. I strukturen ovenfor er node nummerert 1 rotnoden til treet. Hvis en node er direkte knyttet til en annen node, vil den bli kalt en foreldre-barn-relasjon.Barnnode:Hvis noden er en etterkommer av en node, er noden kjent som en barnenode.Forelder:Hvis noden inneholder en sub-node, sies den noden å være overordnet til den sub-noden.Søsken:Nodene som har samme forelder er kjent som søsken.Bladknute:-Noden til treet, som ikke har noen barnenode, kalles en bladnode. En bladnode er den nederste noden av treet. Det kan være et hvilket som helst antall bladnoder til stede i et generelt tre. Bladnoder kan også kalles eksterne noder.Interne noder:En node har minst én underordnet node kjent som en innvendig Ancestor node:-En stamfar til en node er en hvilken som helst forgjengernode på en vei fra roten til den noden. Rotnoden har ingen forfedre. I treet vist i bildet ovenfor er nodene 1, 2 og 5 forfedrene til node 10.Etterkommer:Den umiddelbare etterfølgeren til den gitte noden er kjent som en etterkommer av en node. I figuren ovenfor er 10 etterkommeren av node 5.

Egenskaper for tredatastruktur

Rekursiv datastruktur:Treet er også kjent som en rekursiv datastruktur . Et tre kan defineres som rekursivt fordi den særegne noden i en tredatastruktur er kjent som en rotnoden . Rotnoden til treet inneholder en lenke til alle røttene til undertrærne. Det venstre undertreet vises i den gule fargen i figuren nedenfor, og det høyre undertreet vises i den røde fargen. Det venstre undertreet kan deles opp i undertre vist i tre forskjellige farger. Rekursjon betyr å redusere noe på en lignende måte. Så denne rekursive egenskapen til tredatastrukturen er implementert i forskjellige applikasjoner.
Antall kanter:Hvis det er n noder, vil det være n-1 kanter. Hver pil i strukturen representerer koblingen eller banen. Hver node, bortsett fra rotnoden, vil ha minst én innkommende lenke kjent som en kant. Det vil være én kobling for foreldre-barn-forholdet.Dybde av node x:Dybden til node x kan defineres som lengden på banen fra roten til noden x. En kant bidrar med en lengdeenhet i banen. Så dybden til noden x kan også defineres som antall kanter mellom rotnoden og noden x. Rotnoden har 0 dybde.Høyde på node x:Høyden på node x kan defineres som den lengste veien fra node x til bladnoden.

Basert på egenskapene til tredatastrukturen, klassifiseres trær i ulike kategorier.

Implementering av Tre

Tredatastrukturen kan opprettes ved å lage nodene dynamisk ved hjelp av pekerne. Treet i minnet kan representeres som vist nedenfor:

Figuren ovenfor viser representasjonen av tredatastrukturen i minnet. I strukturen ovenfor inneholder noden tre felt. Det andre feltet lagrer dataene; det første feltet lagrer adressen til det venstre barnet, og det tredje feltet lagrer adressen til det høyre barnet.

I programmering kan strukturen til en node defineres som:

 struct node { int data; struct node *left; struct node *right; } 

Strukturen ovenfor kan bare defineres for de binære trærne fordi det binære treet kan ha maksimalt to barn, og generiske trær kan ha mer enn to barn. Strukturen til noden for generiske trær vil være forskjellig sammenlignet med det binære treet.

Bruk av trær

Følgende er bruksområdene for trær:

java string indexof

Lagre naturlig hierarkiske data:Trær brukes til å lagre dataene i den hierarkiske strukturen. For eksempel filsystemet. Filsystemet som er lagret på diskstasjonen, filen og mappen er i form av de naturlig hierarkiske dataene og lagret i form av trær.Organiser data:Den brukes til å organisere data for effektiv innsetting, sletting og søking. For eksempel har et binært tre en logN-tid for å søke i et element.Prøv:Det er en spesiell type tre som brukes til å lagre ordboken. Det er en rask og effektiv måte for dynamisk stavekontroll.haug:Det er også en tredatastruktur implementert ved hjelp av matriser. Den brukes til å implementere prioriterte køer.B-tre og B+tre:B-Tree og B+Tree er tredatastrukturene som brukes til å implementere indeksering i databaser.Rutingtabell:Tredatastrukturen brukes også til å lagre dataene i rutetabeller i ruterne.

Typer tredatastruktur

Følgende er typene for en tredatastruktur:

Generelt tre:Det generelle treet er en av typene tredatastruktur. I det generelle treet kan en node ha enten 0 eller maksimalt n antall noder. Det er ingen begrensning pålagt graden av noden (antall noder som en node kan inneholde). Den øverste noden i et generelt tre er kjent som en rotnode. Barna til foreldrenoden er kjent som undertrær .

Det kan være n antall undertrær i et generelt tre. I det generelle treet er undertrærne uordnet ettersom nodene i undertreet ikke kan sorteres.
Hvert ikke-tomt tre har en nedadgående kant, og disse kantene er koblet til nodene kjent som barn noder . Rotnoden er merket med nivå 0. Nodene som har samme overordnede er kjent som søsken . Binært tre :Her antyder binært navn i seg selv to tall, dvs. 0 og 1. I et binært tre kan hver node i et tre ha ytterst to underordnede noder. Her betyr ytterst om noden har 0 noder, 1 node eller 2 noder.

For å vite mer om det binære treet, klikk på lenken nedenfor:
https://www.javatpoint.com/binary-tree Binært søketre :Binært søketre er en ikke-lineær datastruktur som én node er koblet til n antall noder. Det er en nodebasert datastruktur. En node kan representeres i et binært søketre med tre felt, dvs. datadel, venstre-barn og høyre-barn. En node kan kobles til de ytterste to underordnede nodene i et binært søketre, slik at noden inneholder to pekere (venstre underordnede og høyre underordnede peker).
Hver node i det venstre undertreet må inneholde en verdi som er mindre enn verdien til rotnoden, og verdien til hver node i det høyre undertreet må være større enn verdien til rotnoden.

En node kan opprettes ved hjelp av en brukerdefinert datatype kjent som struktur, som vist under:

 struct node { int data; struct node *left; struct node *right; } 

Ovenstående er nodestrukturen med tre felt: datafelt, det andre feltet er den venstre pekeren for nodetypen, og det tredje feltet er den høyre pekeren for nodetypen.

For å vite mer om det binære søketreet, klikk på lenken nedenfor:

https://www.javatpoint.com/binary-search-tree

AVL-tre

Det er en av typene av det binære treet, eller vi kan si at det er en variant av det binære søketreet. AVL treet tilfredsstiller eiendommen til binært tre så vel som av binært søketre . Det er et selvbalanserende binært søketre som ble oppfunnet av Adelson Velsky Lindas . Her betyr selvbalansering at balansering av høydene til venstre undertre og høyre undertre. Denne balanseringen måles i form av balansefaktor .

Vi kan betrakte et tre som et AVL-tre hvis treet følger det binære søketreet samt en balansefaktor. Balanseringsfaktoren kan defineres som forskjellen mellom høyden på venstre undertre og høyden på høyre undertre . Balanseringsfaktorens verdi må være enten 0, -1 eller 1; Derfor bør hver node i AVL-treet ha verdien av balansefaktoren enten som 0, -1 eller 1.

For å vite mer om AVL-treet, klikk på lenken nedenfor:

https://www.javatpoint.com/avl-tree

Rød-svart tre

Det rød-svarte treet er det binære søketreet. Forutsetningen for det rød-svarte treet er at vi skal vite om det binære søketreet. I et binært søketre bør verdien til venstre undertreet være mindre enn verdien til den noden, og verdien til høyre undertreet bør være større enn verdien til den noden. Som vi vet at tidskompleksiteten til binært søk i gjennomsnittstilfellet er log₂n, det beste tilfellet er O(1), og det verste tilfellet er O(n).

katalog gi nytt navn til linux

Når en operasjon utføres på treet, ønsker vi at treet vårt skal være balansert slik at alle operasjoner som søking, innsetting, sletting osv. tar kortere tid, og alle disse operasjonene vil ha samme tidskompleksitet som Logg₂n.

Det rød-svarte treet er et selvbalanserende binært søketre. AVL-tre er også et høydebalanserende binært søketre da hvorfor trenger vi et rød-svart tre . I AVL-treet vet vi ikke hvor mange rotasjoner som kreves for å balansere treet, men i det rød-svarte treet kreves det maksimalt 2 rotasjoner for å balansere treet. Den inneholder en ekstra bit som representerer enten den røde eller svarte fargen til en node for å sikre balansering av treet.

Splay tre

Splay-treet-datastrukturen er også et binært søketre der nylig åpnet element plasseres ved rotposisjonen til treet ved å utføre noen rotasjonsoperasjoner. Her, splaying betyr den nylig åpnede noden. Det er en selvbalanserende binært søketre som ikke har noen eksplisitt balansebetingelse som AVL tre.

Det kan være en mulighet for at høyden på splaytreet ikke er balansert, dvs. høyden på både venstre og høyre undertre kan variere, men operasjonene i splaytreet tar rekkefølgen rolig tid hvor n er antall noder.

Splay-tre er et balansert tre, men det kan ikke betraktes som et høydebalansert tre fordi det etter hver operasjon utføres rotasjon som fører til et balansert tre.

Treap

Treap-datastrukturen kom fra Tree and Heap-datastrukturen. Så det omfatter egenskapene til både tre- og heap-datastrukturer. I binært søketre må hver node på venstre undertre være lik eller mindre enn verdien til rotnoden, og hver node på høyre undertre må være lik eller større enn verdien til rotnoden. I haugdatastruktur inneholder både høyre og venstre undertre større nøkler enn roten; derfor kan vi si at rotnoden inneholder den laveste verdien.

I treap-datastrukturen har hver node begge deler nøkkel og prioritet hvor nøkkelen er avledet fra det binære søketreet og prioritet er avledet fra heap-datastrukturen.

De Treap datastrukturen følger to egenskaper som er gitt nedenfor:

• Høyre underordnet av en node>=nåværende node og venstre underordnet av en node<=current node (binary tree)< li>
• Underordnede undertre må være større enn noden (heapen)

B-tre

B-tre er et balansert m-veis tre hvor m definerer rekkefølgen på treet. Til nå har vi lest at noden inneholder bare én nøkkel, men b-treet kan ha mer enn én nøkkel og mer enn 2 barn. Den opprettholder alltid de sorterte dataene. I binært tre er det mulig at bladnoder kan være på forskjellige nivåer, men i b-tre må alle bladnodene være på samme nivå.

Hvis rekkefølgen er m, har noden følgende egenskaper:

• Hver node i et b-tre kan ha maksimum m barn
• For minimum barn har en bladnode 0 barn, rotnode har minimum 2 barn og intern node har minimumstak på m/2 barn. For eksempel er verdien av m 5 som betyr at en node kan ha 5 barn og interne noder kan inneholde maksimalt 3 barn.
• Hver node har maksimale (m-1) nøkler.

Rotnoden må inneholde minimum 1 nøkkel og alle andre noder må inneholde minst tak på m/2 minus 1 nøkler.