Delträdet

Delträdet av en nod v i ett rotat träd är det delträd som utgår från v. Det består av noden v och alla dess ättlingar – noder som v är en avlägsen föregångare till genom en kedja av föräldrar. Om trädet inte är rotat är begreppet delträd inte entydigt utan kräver att en rot väljs.

Storlek och struktur: I ett rotat träd har varje nod exakt en förälder utom roten. Delträdet av v innehåller v och alla dess nedstigande noder. Antalet noder i delträdet kallas storleken av delträdet och betecknas ofta n(v). Delträdet är i sin tur ett rotat träd med v som rotnod.

Beräkningar och representation: En vanlig teknik är att utföra en DFS (djupet först-sökning) och erhålla in- och ut-tiderna tin[v] och tout[v]. Delträdet av v motsvarar intervallet [tin[v], tout[v]] i dfs-sekvensen, vilket gör det möjligt att utföra snabba frågor och uppdateringar över hela delträdet med segmentträd eller Fenwick-träd. En annan teknik är heavy-light-decomposition, som utnyttjar delträden i uppdelningen av trädet för effektiv väg- och tröskelberäkning.

Användningar: Delträden används i algoritmer och datastrukturer där operationer ska tillämpas på alla noder i ett delträd, till exempel att summera värden eller uppdatera värden i hela delträdet samtidigt. Vanliga tillämpningar finns inom XML/HTML DOM-träd, kompilatorer som uttrycksträd, samt filsystemsstrukturer och databassökningar.

Noter: Begreppet är meningsfullt endast när trädet är rotat eller när en rot har definierats. I ett orotat träd saknas en universell definition av delträdet utan en vald rot.