Introduksjon til trær i datastruktur

Før vi forstår tresortene i datastruktur, skal vi først studere trærne i datastruktur. Treet i datamaskinfeltet er også referert til som det virkelige treet. Imidlertid er forskjellen mellom den virkelige verden og databehandlingsfeltet at det blir visualisert som opp ned og rot på toppen av det og gren fra rot til tre blader. Blant forskjellige applikasjoner i den virkelige verden brukes tredatastrukturen da den kan demonstrere forhold mellom forskjellige noder med foreldre-barn-hierarkiet. Det kalles også en hierarkisk datastruktur på grunn av dette. Det er mest populært for å forenkle og fremskynde søk og sortering. Det blir sett på som en av de sterkeste og mest avanserte datastrukturene. Et tre er en representasjon av den ikke-lineære datastrukturen. Et tre kan vises ved bruk av forskjellige brukerdefinerte eller primitive datatyper. Vi kan bruke matriser, klasser tilkoblede lister eller andre typer datastrukturer for å implementere treet. Det er en gruppe noder som henger sammen. Noder er festet til kantene for å demonstrere forholdet.

Relasjoner i et tre: I diagrammet ovenfor er P roten til treet, også er P foreldre til Q, R og S. Q er barn av P. Derfor er Q, R og S søsken. Mens P er oldeforelder til A, B, C, D og E.

Hva er trær?

Et tre er en hierarkisk datastruktur som naturlig lagrer informasjonen på en hierarkisk måte. Tredatastrukturen er en av de mest effektive og modne. Knutepunktene som er forbundet med kantene er representert.

Egenskaper til tre: Hvert tre har en spesifikk rotnode. Hver treknute kan krysses av en rotnode. Det kalles rot, ettersom treet var den eneste roten. Hvert barn har bare én forelder, men foreldrene kan få mange barn.

Typer trær i datastruktur

Nedenfor er tresortene i en datastruktur:

1. Generelt tre

Hvis det ikke blir satt noen begrensning i hierarkiet til treet, kalles et tre et generelt tre. Hver node kan ha uendelig mange barn i General Tree. Treet er supersettet til alle andre trær.

2. Binærtre

Det binære treet er den typen tre der de fleste to barn kan bli funnet for hver av foreldrene. Ungene er kjent som venstre barn og høyre barn. Dette er mer populært enn de fleste andre trær. Når visse begrensninger og egenskaper blir brukt i et binærtre, brukes også en rekke andre som AVL-tre, BST (Binary Search Tree), RBT-tre, etc.. Når vi går fremover, vil vi forklare alle disse stilene i detalj.

3. Binary Search Tree

Binary Search Tree (BST) er et binært treutvidelse med flere valgfrie begrensninger. Verdien til venstre for en node skal i BST være mindre enn eller lik foreldreverdien, og den rette barneverdien skal alltid være større enn eller lik foreldrenes verdi. Denne egenskapen Binary Search Tree gjør den ideell for søkeoperasjoner siden vi nøyaktig kan bestemme ved hver node om verdien er i venstre eller høyre under-tre. Dette er grunnen til at Search Tree heter.

4. AVL-tre

AVL-tre er et selvbalanserende binært søketrær. På oppdrag fra oppfinnerne Adelson-Velshi og Landis, er navnet AVL gitt. Dette var det første treet som balanserte dynamisk. En balanseringsfaktor tildeles for hver node i AVL-treet, basert på om treet er balansert eller ikke. Høyden på node barna er på det høyeste 1. AVL vintreet. I AVL-treet er riktig balansefaktor 1, 0 og -1. Hvis treet har en ny node, vil det roteres for å sikre at treet er balansert. Den blir deretter rotert. Vanlige operasjoner som visning, innsetting og fjerning tar O (log n) tid i AVL-treet. Det brukes mest når du arbeider med oppslag.

5. Rød-svart tre

En annen type auto-balanserende tre er rød-svart. Det rød-svarte navnet er gitt fordi det rød-svarte treet har enten rød eller svart malt på hver node i henhold til det rød-svarte treets egenskaper. Den opprettholder balansen i skogen. Selv om dette treet ikke er et fullt balansert tre, tar søkeoperasjonen bare O (log n) tid. Når de nye nodene legges til i rød-svart tre, vil knutene roteres igjen for å opprettholde det rød-svarte treets egenskaper.

6. N-ary Tree

Maksimalt antall barn i denne typen tre som kan ha en node er N. Et binært tre er et toårig tre, som høyst 2 barn i hver binær treknute. Et komplett N-ary-tre er et tre der barn av en node enten er 0 eller N.

Fordeler med tre

Nå skal vi forstå fordelene ved tre:

  • Tre reflekterer i dataene strukturelle forbindelser.
  • Treet brukes til hierarki.
  • Det tilbyr en effektiv prosedyre for søk og innsetting.
  • Trærne er fleksible. Dette gjør det mulig å flytte undertrær med minimal innsats.

Konklusjon - Typer trær i datastruktur

Så her i denne artikkelen har vi sett hva som er trestruktur, hva er forskjellige tresorter i datastrukturen og fordelene med det. Jeg håper du fikk en ide om noen av de vanlige trærne i strukturen til dataene.

Anbefalte artikler

Dette er en guide til typer trær i datastruktur. Her diskuterer vi hva som er trær, 6 typer trær i datastruktur, med fordeler. Du kan også gå gjennom andre relaterte artikler for å lære mer -

  1. AWS Data Pipeline
  2. Oracle Data Warehousing
  3. Flerdimensjonal database
  4. Datastruktur Java-intervjuspørsmål

Kategori:

Stor Data