trädstrukturer

Trädstrukturer är hierarkiska datastrukturer som består av noder sammankopplade av grenar i en trädliknande form. En rot-nod saknar förälder; varje annan nod har exakt en förälder och kan ha noder som kallas barn. Mellan noderna finns alltid en unik stig via förälder–barn-relationerna och trädet är vanligtvis acykliskt. Träd används i datorer för att organisera data och stödja effektiva operationer som sök, infogning och borttagning. Vanliga tillämpningar inkluderar filsystem, kompilatorers syntaxträd och databashuvudstrukturer.

Grundläggande begrepp är nod, rot, barn, löv (noder utan barn), underträd, höjd och djup. Traversering av träd kan göras i olika ordningar, till exempel pre-order, in-order och post-order, ofta med rekursion eller en stack. Komplexiteten för grundläggande operationer beror på trädet: i ett balanserat träd är sök, infogning och borttagning vanligtvis O(log n), medan de i ett obalanserat träd kan vara O(n).

Vanliga varianter inkluderar binära träd, där varje nod har högst två barn (vänster och höger). Binära sökträd ordnar nycklar så att vänstra delträd innehåller mindre nycklar och högra större. Balanserade varianter som AVL-träd och röd-svarta träd upprätthåller balans för att bevara O(log n)-prestanda. Andra strukturer är B-träd och B+-träd som används i databaser och filsystem för effektiv lagringsåtkomst, samt tries för snabba prefix- och ordsökningar.

Användningar omfattar språk- och tolkningsverktyg, databassökningar, indexstrukturer, dokument- och ordbehandling samt algoritmiskt byggande av syntaktiska eller semantiska träd.