högerunderträdet

Högerunderträdet är det delträd i ett binärt träd som utgår från nodens högra barn och består av den noden samt alla dess nedstigande noder. Det omfattar alltså alla noder som är nåbara via en väg som börjar vid den högra barnet.

I sammanhanget binära sökträd innehåller högerunderträdet nycklar som är större än nodens nyckel. I ett binärt sökträd uppdelas trädet omkring nodens nyckel i ett vänsterunderträd (nycklar mindre än nodens nyckel) och högerunderträdet (nycklar större än nodens nyckel). Det betyder att varje subträd bevarar den övergripande sorteringsordningen.

En viktig egenskap i relation till högerunderträdet är att en inorder-traversal av högerunderträdet producerar en del av den totala sorterade sekvensen där nycklarna är större än nodens nyckel. Om hela trädet traverseras i inorder, ges den fullständiga sorterade ordningen.

Storlek och struktur hos högerunderträdet kan räknas rekursivt: antalet noder i högerunderträdet är storleken av underträdet som har den högra barnet som roten. Höjden på högerunderträdet är längden i längst vägen från den högra barnet till ett blad inom det delträdet. Dessa egenskaper används i algoritmer för sökningar, insättningar och balanskontroller i BST samt vid beräkningar av urval och kvoter då man fokuserar på de större nycklarna.