I informatikk og informatikk er et tre en mye brukt abstrakt datatype (ADT) som etterligner den hierarkiske strukturen til et tre , med en verdi ved roten og undertrær med en overordnet node, representert som et sett med noder koblet sammen.
En tredatastruktur kan defineres rekursivt (lokalt) som en samling av noder (starter fra en rotnode), der hver node er en datastruktur med en verdi, sammen med en liste med referanser til nodene. ( barna ), forutsatt at ingen referanse dupliseres og ingen node peker til roten.
Alternativt kan et tre abstrakt defineres som en helhet som et ordnet tre , med en verdi tildelt hver node. Begge perspektivene er nyttige: mens et tre kan analyseres matematisk, er det faktisk representert som en datastruktur der hver node behandles separat (i stedet for som en liste over noder og en liste over tilstøtende mellom noder, som en graf ). Ser man på et tre som et sett, kan man snakke om foreldrenoden til en gitt node, men generelt snakker man om en datastruktur til en gitt node som bare inneholder listen over dens barn uten referanse til dens overordnede (hvis noen) . ).
Et tre er en (muligens ikke-lineær) datastruktur sammensatt av noder, toppunkter og kanter som er asykliske. Et tre som ikke har noen noder kalles et tomt eller nulltre . Et ikke-tomt tre består av en rotnode og potensielt mange ekstra nodenivåer som danner et hierarki.
Det er et skille mellom et tre som en abstrakt datatype og som en konkret datastruktur, analogt med skillet mellom en liste og en koblet liste . Som datatype har et tre en verdi og barn, og barna er selv undertrær; verdien og barna til et tre tolkes som verdien til rotnoden og undertrærne til barna til rotnoden. For å tillate at trær er endelige, må man enten la listen over barn være tom, eller tillate at trær er tomme, i så fall kan listen over barn være av fast størrelse ( grenfaktor , spesielt 2 eller binær ), hvis ønsket.
Som en datastruktur er et koblet tre en gruppe noder, der hver node har en verdi og en liste med referanser til andre noder (deres barn). Denne datastrukturen definerer virkelig en rettet graf, [ 1 ] fordi den kan ha løkker eller flere referanser til samme node, akkurat som en koblet liste. Så er det også kravet om at ingen to referanser peker til samme node (at hver node har høyst en enslig forelder, og faktisk alle har det, bortsett fra roten), og et tre som bryter med dette er et korrupt tre. .
På grunn av bruken av referanser til trær i datastrukturen til et koblet tre, snakker vi ofte om trær der de implisitt blir representert ved referanser til rotnoden, siden dette vanligvis er måten de brukes på. For eksempel, i stedet for et tomt tre, kan man ha en nullreferanse: et tre er aldri tomt, men en referanse til et tre kan være null.
Rekursivt er et tre som datatype definert som en verdi (av en bestemt datatype, muligens tom), sammen med en liste over trær (muligens en tom liste), undertrærne til deres barn:
t: v [t[1], ..., t[k]](Et tre t består av en verdi v og en liste over andre trær.)
Mer elegant, gjennom gjensidig rekursjon , hvor et tre er et av de mest grunnleggende eksemplene, kan et tre defineres som en skog (en liste over trær), der et tre består av en verdi og en skog (undertrærne til dets barn):
f: [t[1], ..., t[k]] t: vfMerk at denne definisjonen er i form av verdier, og er hensiktsmessig i funksjonelt språk ( referensiell gjennomsiktighet antas ); forskjellige trær har ingen sammenheng, siden de bare er verdilister.
Som en datastruktur er et tre definert som en node (roten), som igjen består av en verdi (av en eller annen datatype, muligens tom), sammen med en liste med referanser til andre noder (eventuelt tom liste og muligens null). referanser):
n: v [&n[1], ..., &n[k]](En node n består av en verdi v og en liste med referanser til andre noder.)
Denne datastrukturen definerer en rettet graf, [ 1 ] og for at det skal være et tre, må en betingelse legges til i dens globale struktur (i dens topologi), og dette er at høyst én referanse kan peke til en gitt node ( en node har høyst én forelder), og ingen node i treet kan peke til roten. Faktisk må alle noder (annet enn roten) ha nøyaktig én forelder, og roten må ikke ha noen foreldre.
Faktisk, gitt en liste over noder, og for hver node i en liste over referanser til dens barn, kan man ikke vite om denne strukturen er et tre eller ikke uten å analysere dens globale struktur, som definert nedenfor.
Som en abstrakt datatype ( ADT ), er den abstrakte tretypen T med verdier av en eller annen type E definert ved å bruke skogabstrakttypen F (liste over trær), av funksjonene:
verdi: T → E sønn: T → F null: () → F node: E × F → Tmed aksiomene:
verdi(node( e , f )) = e child(node( e , f )) = fNår det gjelder typeteori , er et tre en induktiv type definert av null (tom skog) og node (rotet tre med gitt verdi og barn) konstruktører.
Sett som en helhet er en tredatastruktur et ordnet tre , vanligvis med verdier knyttet til hver node. Nærmere bestemt er det (hvis det kreves at det ikke er tomt):
Med:
Trær har ofte en forgreningsfaktor på to barnenoder (eventuelt tomme, altså høyst to ikke-tomme barnenoder ). I disse tilfellene snakker vi om et binært tre .
Å tillate tomme trær gjør noen enkle definisjoner litt mer kompliserte: et rotfestet tre må ikke være tomt, så hvis tomme trær tildeles definisjonen ovenfor, blir de i stedet et tomt tre, eller et tre forankret på en slik måte at ... . På den annen side forenkles tomme trær ved å definere en fast forgreningsfaktor: med tomme trær er et binært tre et tre slik at hver node har nøyaktig to barn, som hver er et (muligens tomt) tre. Settene med operasjoner i et tre må inkludere gaffeloperasjonen.
En node er en struktur som kan inneholde en verdi eller betingelse, eller representere en separat datastruktur (som kan være et tre). Hver node i et tre har null eller flere underordnede noder , som er arrangert under den i treet (ved konvensjon tegnes trær fra topp til bunn). En node som har et barn kalles barnets overordnede node (eller toppnode ). Alle noder har minst én forelder.
En intern node (også kjent som en undernode eller grennode ) er en hvilken som helst node i et tre som har undernoder. På samme måte er en ekstern node (også kjent som en ytre node , bladnode eller terminalnode ) en hvilken som helst node som ikke har underordnede noder.
Den høyeste noden i et tre kalles rotnoden . Avhengig av definisjonen, kan et tre bli tvunget til å ha en rotnode (i så fall ville ingen tre være tomt), eller tillates å være tomt, i så fall har det ikke nødvendigvis en rotnode. Som den øverste noden vil ikke rotnoden ha en forelder. Det er noden der algoritmene starter, siden den som en datastruktur bare kan overføres fra forelder til barn. Legg merke til at noen algoritmer starter ved roten, men besøk bladnodene først (for å få tilgang til verdien til bladnodene), og få tilgang til roten sist (det vil si at de først får tilgang til rotens barn). , men bare få tilgang til rotverdien som det siste trinnet). Alle andre noder kan nås ved å følge armene eller lenkene . (I den formelle definisjonen er hver av disse banene unik.) I diagrammer er rotnoden konvensjonelt tegnet øverst. I noen trær, for eksempel hauger , har rotnoden spesielle egenskaper. Hver node i et tre kan sees på som rotnoden til undertreet som er forankret i den noden.
Høyden på en node er lengden på den lengste synkende banen til et blad fra den noden. Høyden på roten er høyden på treet. Dybden til en node er lengden på banen til roten (det vil si banen til roten ). Dette er vanligvis nødvendig ved manipulering av forskjellige selvbalanserende trær ("AVL-trær" , spesielt). Rotnoden har null dybde, bladnodene har null høyde, og et tre med bare én node (derav både en rot og et blad) har null dybde og null høyde. Konvensjonelt har et tomt tre (tre uten noder, hvis de er tillatt) dybde og høyde -1.
Et undertre til et tre T er et tre som består av en node i T og alle dens etterkommere i T . [ 2 ] Da tilsvarer nodene undertrærne (hver node tilsvarer undertreet til seg selv og alle dets etterkommere) - undertreet som tilsvarer rotnoden er hele treet, og hver node er rotnoden til undertreet som bestemmer den; undertreet som tilsvarer en hvilken som helst annen node kalles det riktige undertreet (i analogi med properset ).
Trær er ofte tegnet på flyet. Ordnede trær kan representeres i hovedsak og bare i planet, og kalles derfor platantrær, på følgende måte: hvis man fikser en konvensjonell rekkefølge (for eksempel med klokken), og setter til underordnede noder i den rekkefølgen (første innkommende arm fra en forelder, deretter første arm fra et barn, etc.), dette resulterer i en innbygging av treet i flyet. Omvendt bestemmer en slik innbygging en rekkefølge av barnenodene.
Hvis man plasserer roten øverst (foreldre over barn, som i et slektstre ) og plasserer alle noder som er innenfor en gitt avstand fra roten (i form av antall kanter: nivået til et tre ) på en gitt horisontal linje, oppnås en standardtegning av treet. Gitt et binært tre, er det første barnet det til venstre (venstre node ), og det andre barnet er til høyre (høyre node ).
Det er mange forskjellige måter å representere trær på; de vanligste representasjonene representerer noder dynamisk som poster med pekere til deres barn, foreldre eller begge deler, eller som elementer i en vektor , med relasjoner mellom dem bestemt av deres posisjoner i den (for eksempel en binær haug ).
Faktisk kan et binært tre implementeres som en liste over lister (en liste der verdiene er lister): hodet på en liste (verdien av det første leddet) er det venstre barnet, mens halen (listen) av andre og påfølgende vilkår) er det rette barnet. Dette kan endres for å tillate verdier, som i symbolske uttrykkslister ( uttrykk S ), der hodet (verdien av første ledd) er verdien til noden, halehodet (verdien av andre ledd) er venstre barn, og halen på halen (liste over arvevilkår) er det rette barnet.
Generelt vil ikke en node i et tre ha pekere til foreldrene sine, men denne informasjonen kan inkluderes (ved å utvide datastrukturen til også å inkludere en peker til vektoren) eller lagres separat. Alternativt kan oppkoblingene inkluderes i barnenodens data, som i et koblet binært tre .
Hvis armene (til underordnede noder) er tenkt på som referanser, er et tre et spesialtilfelle av en graf, og tredatastrukturen kan generaliseres til å representere en rettet graf ved å fjerne begrensningene som en node maksimalt kan ha en forelder, og sykluser er ikke tillatt. Armene anses fortsatt for å være nodepar, men overordnede og underordnede termer erstattes vanligvis med annen terminologi (f.eks . kilde og mål ). Det er forskjellige implementeringsstrategier : en graf kan representeres av den samme lokale datastrukturen som et tre (noder med verdi og lister over deres barn), forutsatt at "listen over barn" er en liste over referanser, eller globalt av strukturer som f.eks. som tilknytningslister .
I grafteori er et tre en sammenhengende asyklisk graf ; Med mindre annet er angitt, antas trær og grafer i grafteori å være urettet. Det er ingen en-til-en korrespondanse mellom slike trær og trær som en datastruktur. Vi kan ta et vilkårlig tre uten retning, og vilkårlig velge en av dets toppunkter som roten , og ha alle armene peker bort fra roten - som produserer en trestruktur - og tildele en rekkefølge til alle nodene. Resultatet tilsvarer en tredatastruktur. Hvis du velger en annen rot eller en annen rekkefølge, får du en annen graf.
Gitt en node i et tre, definerer dens barn en ordnet skog (foreningen av undertrær gitt av alle dens barn, eller hva som tilsvarer, ta undertreet gitt av selve noden og slett roten). Akkurat som undertrær er vanlige rekursjonister (som i et dybdesøk), er skoger vanlige corecursions (som i et breddesøk).
Gjennom gjensidig rekursjon kan en skog defineres som en liste over trær (representert av rotnoder), der en node (av et tre) består av en verdi og en skog (dens barn):
f: [n[1], ..., n[k]] n: vfÅ krysse gjennom elementene i et tre via forbindelsene mellom foreldre og barn kalles å krysse treet , og handlingen er en vei gjennom treet. Ofte kan en operasjon utføres når en peker kommer til en bestemt node. En bane der hver overordnet node krysses før dens barn kalles en forhåndsbestillingsbane ; en sti der barna krysses før sine respektive foreldre kalles en sti av senere rekkefølge ; en bane der en nodes venstre undertre, selve noden og til slutt dens høyre undertre krysses, kalles en traverseringsrekkefølge . (Denne siste situasjonen, som refererer til nøyaktig to undertre, et venstre undertre og et høyre undertre, er spesifikt et binært tre .) En nivårekkefølge bane utfører et effektivt breddesøk på hele treet; noder krysses nivå for nivå, hvor rotnoden besøkes først, etterfulgt av dens direkte barnenoder og deres søsken, etterfulgt av deres barnebarnnoder og deres søsken osv., inntil alle noder i treet er krysset.