trestrukturer

Trestrukturer er en datastruktur som organiserer elementer i en hierarkisk grenstruktur. De består av noder (eller vertices) og kanter som forbinder dem. En trestruktur har vanligvis én roten, og hver node har én forelder (unntatt roten) og kan ha flere barn. Det finnes ingen sykluser, og treet er ofte koblet slik at alle noder er forbundet til roten. En samling treer som ikke er koblet sammen kalles en skog.

En nøkkelbegrepspakke i trestrukturer er rotnoden, som fungerer som startpunktet. I binære treer har hver node høyst to barn, ofte betegnet venstre og høyre. En binær søketre (BST) er et binært tre der alle verdier i venstre subtre er mindre enn nodens verdi, og alle verdier i høyre subtre er større, noe som muliggjør effektiv søking og innsetting.

Generelle treer kalles n-ære treer, hvor hver node kan ha et varierende antall barn. Balanserte treer søker å holde trehøyden lav for å sikre effektive operasjoner, og eksempler inkluderer AVL-trær og rødt-svart treer. Fullstendige og komplette treer beskriver hvordan nodene er fordelt på nivåene i treet.

Traversering er sentralt i treoperasjoner og inkluderer preordre, inorder (inordner), postordre og nivåorden. Disse operasjonene brukes ved søk, utskrift, bygging og modifikasjon av treet. I tillegg kan operasjoner som innsetting, sletting og balanserotasjoner være viktige i vedlikehold av balanserte treer.

Trestrukturer brukes bredt i databehandling: filsystemer, XML/HTML-DOM, syntaks- og uttrykstrær i kompilatorer og tolkere, samt beslutningstrær i maskinlæring og beslutningsstøttesystemer.