Trädstruktur

Trädstruktur, eller träd, är en hierarkisk datastruktur där element organiseras i noder som följer en förälder-barn-relation. Den översta noden kallas rot. Varje nod har högst en förälder (utom roten) och kan ha ett godtyckligt antal barn. Noder utan barn kallas löv. Om trädet betraktas som en sammanhängande enhet finns det en unik väg från roten till varje nod, vilket gör strukturen acyklisk.

Träd kan vara rotade eller oberoende av rot (i så kallade skogar). I datorvetenskap används rotade träd som kärnstruktur för organisering av data, syntaks- och uttrycksparsing samt sökträd. Viktiga egenskaper är relationen mellan rot, förälder, barn, djup och höjd, liksom att varje nod har exakt en väg från roten.

Vanliga typer inkluderar generella träd, där en nod kan ha många barn; binära träd, där varje nod har högst två barn; och specialiserade varianter som balanserade träd (till exempel AVL- och röd-svarta träd) samt B-träd, som används i databaser och filsystem. Representationer kan byggas på pekare mellan noder eller använda arrayer (särskilt i binära träd).

Traversering och operationer: vanliga metoder för att besöka noder är pre-ordning, in-ordning, post-ordning och nivå-ordning. Typiska operationer inkluderar insättning, sökning och borttagning. Trädhöjd och antal noder påverkar prestanda vid dessa operationer.

Tillämpningar: träd används inom filsystem, kompilatorer och uttrycksgrenar, databaser, minnes- och cacheorganisering samt beslutsprocesser i maskininlärning. Inom biologi används fylogenetiska träd för att illustrera släktskap mellan arter.