Tre (datastruktur)

Trær er en av de mest brukte datastrukturene innenfor informatikken. Den bygger på matematikkens grafteori.

Et tre er en samling elementer kalt noder, som forbindes med pekere (kanter). Én node er definert som roten i treet. Det kan ikke finnes sykler i et tre, og det må være sammenhengende.

Et tre med $N$ noder vil ha $N-1$ kanter.

En node sies å være barnet til noden den pekes på fra nivået over, og er forelderen til nodene den peker på i nivået under. Noder som ikke har noen barn kalles bladnoder. Et tre inneholder mange subtrær, der roten i et subtre er barnet til en node i treet på nivået over.

En sti fra node n₁ til n_k er definert som en sekvens av noder n₁, n₂, ..., n_k slik at n_i er forelderen til n_{i 1} for alle i fra og med én til k. I et tre er det nøyaktig én sti fra roten til hver node. Dybden av en node er lengden på en sti fra roten av treet til noden. Høyden av en node er lengden på den lengste stien fra noden ned til en bladnode.

Binære trær

Et binært tre er et tre der hver node kan ha maksimum to barn. Man kan derfor la hver node ha en direkte peker til hvert enkelt barn. Trær av denne typen vil ha en gjennomsnittlig dybde på $O({\sqrt {n}})$ .

Binære trær brukes innenfor flere områder av informatikken, og spesielt innenfor kompilatordesign.

Binære søketrær

I et binært søketre har hver node fått tilordnet en verdi. Et binært søketre kjennetegnes av at verdien i en node er større enn alle verdiene i venstre subtre, og mindre enn alle verdiene i høyre subtre.

Et binært søketre vil ha en gjennomsnittlig dybde på $O(\log _{2}n)\,$ . Dette gjør at man raskt kan finne et element i et binært søketre.

Innsetting av et element i et slikt tre er også relativt enkelt. Det gjøres ved å søke seg frem til riktig plass i treet, på samme måte som for finn-operasjonen, og deretter dytte noden man tar plassen til ned som barnet til noden man setter inn.

Det er noe verre å slette en node fra det binære søketreet. Om noden man vil slette er en bladnode, kan den slettes umiddelbart. Om noden man vi lette bare har ett barn, kan man slette den og la foreldrenoden til den man slettet peke på barnenoden til noden man slettet. Om noden man vil slette har to barn, må man erstatte noden man sletter, men det minste barnet i høyre subtre, og rekursivt slette noden man flytter opp.

Rød-svarte trær

En variant av binære søketrær kalles rød-svarte trær. I denne tretypen får hver node tildelt en farge, enten rød eller svart, basert på tre regler:

Roten i treet er svart
Om en node er rød, må barna være svarte
Alle stier fra en node til en null-referanse må inneholde det samme antallet svarte noder.

Disse reglene fører til at høyden på et rød-svart tre med n noder er maksimum $2log_{2}(n 1)\,$ . Søking blir derfor alltid en logaritmisk operasjon, faktisk kan alle operasjoner på rød-svarte trær gjøres med tidsforbruk $O(log_{2}n)\,$ .

Det er relativt fiklete å sette inn nye elementer i et rød-svart tre. Dette gjør at denne datastrukturen ikke lenger brukes så mye.

B-trær

B-trær brukes ofte når datamengden blir så stor at et helt tre ikke kan legges i hovedminnet, slik at deler av det må legges på platelageret. Da man typisk kan gjøre hundrevis av tusen regneoperasjoner i prosessoren i løpet av tiden det tar å gjøre én diskaksess, er det viktigste å minimere antallet diskoperasjoner i slike tilfeller.

I et B-tre av orden M lagres alle data i bladnodene. Ikke-bladnoder vil inneholde nøkler som brukes i søkingen i treet. Roten i B-treet har mellom to og M barn, og de andre ikke-bladnodene har mellom M/2 (rundet av oppover) og M barn. Alle bladnoder har mellom L/2 (rundet av oppover) og L dataverdier i seg, der L er en konstant typisk valgt på grunnlag av størrelsen på diskblokkene til disken treet skal lagres på.

Binærheaper

En binærheap er en form for prioritetskø som representeres ved hjelp av et tre. I motsetning til andre typer trær implementeres vanligvis ikke en binærheap ved hjelp av grafer, men med bruk av et array.

En binærheap er et binærtre som er fullstendig fylt opp, med et mulig unntak for det nederste nivået, som fylles opp fra venstre mot høyre. En binærheap med høyde $h$ vil derfor inneholde mellom $2^{h}$ og $2^{h 1}-1$ noder. Dette gjør at at operasjoner på en binærheap vil være $O(logN)$ .

Ved hjelp av denne datastrukturen er det lett å finne det minste elementet i en datamengde (eventuelt det største, om man velger å heller implementere treet slik). Dette kommer av at det minste elementet i en binærheap alltid ligger i roten. Siden hvert subtre også er en binærheap, vil hver node ha mindre verdi enn alle deres barn, barnebarn og andre «etterkommere».

Disse attributtene gjør også at det er greit å sette nye elementer inn i en binærheap. En sett inn-operasjon vil være $O(1)$ gjennomsnittlig, og $O(logN)$ i verste fall. Dette fører også med seg at oppbygningen av en binærheap vil i gjennomsnitt være en $O(N)$ -operasjon.