Trädstrukturen

Trädstrukturen är en hierarkisk datastruktur som består av noder och kopplingar kallade kanter. Den har vanligtvis en särskild nod som kallas rot, från vilken alla övriga noder härstammar. Varje nod kan ha ett antal barnnoder och noder utan barn kallas löv. Ett träd är i allmänhet acykliskt och varje nod har exakt en förälder utom roten, vilket gör att det finns en unik väg från roten till varje nod.

Vanliga typer är binära träd där varje nod har högst två barn, och generella träd där antalet barn kan vara olika. Sök-träd (BST) ordnar nycklar så att vänster barn har mindre eller lika nyckel och höger större. Andra varianter inkluderar heap-träd, samt balanserade träd som AVL-träd och röd-svarta träd, vilket förbättrar sök- och uppdateringshastigheter.

Operationer som vanligtvis utförs på träd omfattar traverseringar i olika ordningar (pre-order, in-order, post-order och nivåordning) samt grundläggande modifieringar som insättning, sökning och borttagning av noder. Många träd används för effektiv dataorganisation i programvara och lagring, ofta i varianter som B-träd eller B+-träd för lagring på skiva.

Användningar finns inom filsystem, kompilatorers syntaxträd, XML/HTML DOM-träd, organisationsscheman och databaser. Trädstrukturen är en viktig byggsten för att modellera hierarkier och genomföra effektiva sökningar och sorteringar i stora datamängder.

Historiskt kommer begreppet från grafteori och har varit centralt inom datavetenskapen sedan mitten av 1900-talet.