högerunderträden

Högerunderträden är ett begrepp inom graf- och datastrukturteori som används för att beskriva delträd i ett rottbart binärt träd. För en nod v i ett binärt träd är högerunderträdet det delträd som är roten till nodens högra barn och omfattar alla dess avkomlingar. Om noden saknar en högra barn är högerunderträdet tomt.

I formell bemärkelse är högerunderträdet av en nod v det delträd som uppstår genom att följa högerbarnet från v och fortsätta längs höger- eller vänsterbarn i varje efterföljande nod. Högerunderträden används ofta i rekursiva definitioner och algoritmer där problemställningen uppdelas i delproblem som behandlas inom ett underträd.

Ett enkelt exempel: anta ett rott träd med rotnoden A, där A:s högra barn är C och C har sina egna barn. Högerunderträdet av A består av C och alla noder som är kopplade till C via rätt- eller vänsterbarn under C. Om A saknar ett högerbarn är högerunderträdet bara tomt.

Användningsområden inkluderar beräkningar av storlek eller höjd av subträd, jämförelser av olika delar av ett träd och algoritmer i binära sökträd där operationer ofta fokuserar på höger underträdet. Begreppet står i närrelation till vänsterunderträdet och utgör en byggsten i många rekursiva algoritmer och teoretiska resultat om binära träd.