I denne opplæringen vil du lære om tredatastruktur. Du vil også lære om forskjellige typer trær og terminologiene som brukes i treet.
Et tre er en ikke-lineær hierarkisk datastruktur som består av noder forbundet med kanter.
Et tre
Hvorfor tredatastruktur?
Andre datastrukturer som matriser, koblet liste, stabel og kø er lineære datastrukturer som lagrer data sekvensielt. For å utføre en hvilken som helst operasjon i en lineær datastruktur, øker tidskompleksiteten med økningen i datastørrelsen. Men det er ikke akseptabelt i dagens beregningsverden.
Ulike tredatastrukturer gir raskere og enklere tilgang til dataene, da det er en ikke-lineær datastruktur.
Treterminologier
Node
En node er en enhet som inneholder en nøkkel eller verdi og peker til sine underordnede noder.
De siste nodene i hver bane kalles bladnoder eller eksterne noder som ikke inneholder en lenke / peker til undernoder.
Noden som har minst en undernode kalles en intern node .
Kant
Det er koblingen mellom to noder.
Noder og kanter på et tre
Rot
Det er den øverste noden til et tre.
Høyden på en node
Høyden på en node er antall kanter fra noden til det dypeste bladet (dvs. den lengste banen fra noden til en bladnode).
Dybde av en node
Dybden til en node er antall kanter fra roten til noden.
Høyde på et tre
Høyden på et tre er høyden på rotnoden eller dybden på den dypeste noden.
Høyde og dybde på hver node i et tre
Grad av en node
Graden av en node er det totale antallet grener av den noden.
skog
En samling av usammenhengende trær kalles en skog.
Å lage skog fra et tre
Du kan lage en skog ved å kutte roten til et tre.
Typer av tre
- Binært tre
- Binært søketre
- AVL Tree
- B-treet
Tree Traversal
For å utføre noen operasjoner på et tre, må du nå til den spesifikke noden. Treetraversalalgoritmen hjelper deg med å besøke en nødvendig node i treet.
Hvis du vil vite mer, kan du gå til treovergang.
Tre applikasjoner
- Binary Search Trees (BSTs) brukes til å raskt sjekke om et element er tilstede i et sett eller ikke.
- Haug er et slags tre som brukes til haugsortering.
- En modifisert versjon av treet som heter Tries brukes i moderne rutere for å lagre rutinformasjon.
- De fleste populære databaser bruker B-Trees og T-Trees, som er varianter av trestrukturen vi lærte ovenfor for å lagre dataene deres
- Kompilatorer bruker et syntakstre for å validere syntaksen til hvert program du skriver.
