delträd

Delträd, ofta översatt till subtree, är inom datavetenskap termen för en del av ett rotnat träd som utgår från en viss nod och inkluderar alla dess efterkommande noder. Delträdet betraktas som ett eget träd med roten vid den valda noden och grenar som fortsätter nedåt genom trädet.

Definition och egenskaper: Givet ett rotnat träd T och en nod v, är delträdet rotat vid v mängden av v och alla dess barn, barnbarn och så vidare. Delträden bildar själv trädstrukturer och används som en enhet i algoritmer som traversering, sökningar och uppdateringar. Vanliga egenskaper att känna till är storlek (antal noder i delträdet), djup och höjd av delträdet.

Representation och operationer: Delträdet kan representeras med vanliga trädsstrukturer såsom grannlistor eller pekare. För att snabbt svara på frågor som räkna noder i ett delträd eller uppdatera alla noder i ett delträd används ofta specialtekniker som Euler-tur och intervallbaserade datastrukturer (till exempel segmentträd eller Fenwick-träd). Genom att märka varje nod med in- och ut-tider i en DFS-traversering kan delträdet motsvaras av ett kontinuerligt intervall, vilket gör subträdfrågor och uppdateringar effektiva.

Användning: Delträd är centrala i kompilatorers abstrakta syntaxträd, i hantering av dokumentobjektmodeller (DOM-träd) i webbteknik, samt i nätverk och databassammanhang där man vill känna igen eller manipulera en del av ett större träd. De används också i olika grafalgoritmer och i datastrukturer som stödjer dynamiska träden.

Se även: subtree i grafteori; domänspecifika delträd som används i optimeringar och updated-operations.