Tre (datavitenskap)

I informatikk er et tre- eller trestruktur datastrukturen som fører tilbake til konseptet med rotetre som finnes i grafteori . Et tre består av to typer grunnleggende understrukturer: noden , som vanligvis inneholder informasjon, og buen , som etablerer en hierarkisk forbindelse mellom to noder: vi snakker da om en overordnet node som det kommer en orientert bue fra som forbinder den . til en barnenode .

Det er også bedt om at hver node maksimalt kan ha en enkelt innkommende bue, mens forskjellig antall utgående buer kan gå ut fra de forskjellige nodene. Til slutt blir treet bedt om å ha en enkelt node uten en innkommende bue: denne noden kalles roten til treet. Hver node som ikke har utgående buer kalles en bladnode og i hvert endelig tre, det vil si med et begrenset antall noder, er det minst én bladnode. Åpenbart kan en node være både overordnet (hvis den har utgående kanter) og underordnet (hvis den har en innkommende kant, det vil si hvis den er forskjellig fra roten) på samme tid.

Vanligvis bærer hver node med seg informasjon og veldig ofte også en nøkkel som det er mulig å identifisere den unikt med i treet. Høyden eller dybden til treet er maksimum av lengdene på dets maksimale stier, stier som går fra roten til bladene.

Tretyper

Hovedsakelig er trær delt inn i uordnede trær og ordnede trær . Førstnevnte følger ingen regler angående foreldre-barn-relasjoner, mens sistnevnte krever at det er en presis rekkefølge mellom foreldrenoden og barnetnodene. De mest brukte innen IT-feltet er absolutt de ordnede trærne . En annen klassifisering kan gjøres basert på det maksimale antallet barn en node kan ha. Vi kan derfor snakke om binære trær der hver node maksimalt kan ha to barn, eller om n-ære trær der det ikke er noen grense for maksimalt antall barnenoder.

En ytterligere karakterisering er den som er basert på den såkalte balanseringen: et tre er perfekt balansert hvis det har alle bladene på samme nivå, det vil si hvis hvert blad på treet har samme avstand fra roten. Et tre er balansert hvis , for hver node N , kalt K , settet med maksimumsnivåer som kan nås etter alle bladene til N , forskjellen mellom maksimum og minimum av K ikke er større enn .

Settet med noder over en node utgjør settet med forgjengere, følgende er etterkommerne.

De vanligste typene trær er følgende:

Implementeringer

Den vanligste implementeringen av trær er basert på koblede lister , det vil si etter objekter (noder) som refererer til andre objekter.

Java

Et typisk grensesnitt for en node til et binært tre i Java kan være følgende:

public class Node { public Venstre underordnet node ; offentlig Høyre barnenode ; // informasjonen i noden, av typen Objekt for å generalisere offentlig Objektinformasjon ; // en unik nøkkel for å identifisere noden, for eksempel en hel offentlig int -nøkkelUnivoca ; }

Notorisk er haugtrær også implementerbare via matriser eller vektorer

C

  • Strukturdefinisjon
typedef int TKey ; typedef int TSat ; struct SIinfo { TKey nøkkel ; TSat satellitt ; }; typedef struct SIinfo TInfo ; struct SNode { TInfo info ; struct SNode * venstre ; struct SNode * høyre ; }; typedef struct SNode TNode ; typedef TNode * TTree ;
  • Treoppretting
TTree tree_create () { returner NULL ; }
  • Ødeleggelse av tre
TTree tree_destroy ( TTree tree ) { if ( tre_tom ( tre ) == sant ) returner NULL ; else if (( tre -> venstre == NULL ) && ( tre -> høyre == NULL )) { gratis ( tre ); returner NULL ; } annet { tre -> venstre = tre_ødelegge ( tre -> venstre ); tre -> høyre = tre_ødelegge ( tre -> høyre ); gratis ( tre ); returner NULL ; } }
  • Søk element
TNode * tree_search_recursive ( TTree tree , TKey key ) { if (( tre_tom ( tre ) == sann ) || lik ( tre -> info . nøkkel , nøkkel )) returtre ; _ annet { if ( større ( nøkkel , tre -> info . nøkkel )) return tree_search_recursive ( tre -> høyre , nøkkel ); ellers return tree_search_recursive ( tre -> venstre , nøkkel ); } }
  • Sett inn element
TTree tree_insert_recursive ( TTree tree , TInfo info ) { if ( tree_empty ( tre ) == sant ) { TNode * nynode ; newnode = ( TNode * ) malloc ( størrelse på ( TNode )); if ( nynode == NULL ) { printf ( "Tildelingsfeil" ); gå ut ( 1 ); } nynode -> høyre = nynode -> venstre = NULL ; nynode -> info = info ; returnere nynode ; } else if ( ! større ( info . key , tree -> info . key )) { tre -> venstre = tree_insert_recursive ( tre -> venstre , info ); returtre ; _ } annet { tre -> høyre = tre_innsett_rekursivt ( tre -> høyre , info ); returtre ; _ } }
  • Slett element
TTree_delete_ver2 ( TTree tree , TKey key ) { if ( tree_empty ( tre ) == sant ) / * Tomt tre * / returner NULL ; else if ( større ( tre -> info . nøkkel , nøkkel )) { / * Kansellering i venstre gren * / tre -> venstre = tree_delete_ver2 ( tre -> venstre , nøkkel ); returtre ; _ } else if ( større ( nøkkel , tre -> info . nøkkel )) { / * Slett i høyre gren * / tre -> høyre = tree_delete_ver2 ( tre -> høyre , nøkkel ); returtre ; _ } annet { /*tree->info.key==key * / / * Sletting av rot * / TNode * min_right , * alias ; if ( tre_tom ( tre -> høyre ) == sant ) alias = tre -> venstre ; annet { min_right = tree_min ( tre -> høyre ); min_høyre -> venstre = tre -> venstre ; alias = tre -> høyre ; } gratis ( tre ); return alias ; } }

Besøk av trær i dybden

Mange algoritmer som opererer på trær krever at du besøker alle nodene i treet, eller definerer en (under)algoritme som, gitt et tre, bygger permutasjon av settet med nodene. Metodene for dybdebesøk er som følger.

  • Besøk i forhåndsbestilling : roten besøkes først, etter venstre undertre og til slutt høyre undertre
void visitapreorder ( Nodepointer start ) { if ( start == NULL ) returner ; start -> markup = 1 ; printf ( " % d % d \ n " , start -> verdi , start -> markering ); visitapreorder ( start -> son_sx ); visitapreorder ( start -> son_dx ); }

Nodepeker er en peker til rotnoden som forhåndsbestillingssøket starter fra. son_sx og son_dx er henholdsvis venstre og høyre barn til noden som søket starter fra. Algoritmen som beskrives er begrenset til å skrive ut verdien og markeringen av den betraktede noden på skjermen.

  • Besøk i rekkefølge : Det venstre undertreet besøkes først, deretter roten og til slutt det høyre undertreet
void visiteinorder ( Nodepointer start ) { if ( start == NULL ) returner ; visitinorder ( start -> son_sx ); start -> markup = 1 ; printf ( " % d % d \ n " , start -> verdi , start -> markering ); visitinorder ( start -> son_dx ); }

Nodepeker er en peker til rotnoden som søket starter i rekkefølge. son_sx og son_dx er henholdsvis venstre og høyre barn til noden som søket starter fra. Algoritmen som beskrives er begrenset til å skrive ut verdien og markeringen av den betraktede noden på skjermen.

  • Etterbestillingsbesøk : Venstre undertre besøkes først, deretter høyre undertre og til slutt roten
void visitapostorder ( Nodepointer start ) { if ( start == NULL ) returner ; visitapostorder ( start -> son_sx ); visitapostorder ( start -> son_dx ); start -> markup = 1 ; printf ( " % d % d \ n " , start -> verdi , start -> markering ); }

Nodepeker er en peker til rotnoden som etterbestillingssøket starter fra. son_sx og son_dx er henholdsvis venstre og høyre barn til noden som søket starter fra. Algoritmen som beskrives er begrenset til å skrive ut verdien og markeringen av den betraktede noden på skjermen.

Hver metode kan brukes rekursivt , dvs. med "besøk til et undertre" mener vi bruken av den samme algoritmen for å besøke rotnoden til det undertreet. Alternativt er det mulig å gjennomføre besøket i dybden ved hjelp av et batteri .

Et eksempel på en utelukkende ikke -rekursiv metode for å besøke et tre er gitt av besøket i bredden .

Relaterte elementer

Andre prosjekter

Eksterne lenker