högerunderträd

Högerunderträdet till en nod i ett binärt träd är det underträd som uppstår från nodens högra barn och inkluderar alla dess nedstammningar. Om noden saknar högra barn är högerunderträdet tomt. Högerunderträdet betraktas ofta som en del av den rekursiva uppbyggnaden av trädet och kan beskrivas som högerunderträdet till nodens högra barn.

I ett binärt sökträd (BST) finns det en särskild regel kopplad till högerunderträdet: alla nycklar i högerunderträdet är större än nodens nyckel, medan vänsterunderträdet innehåller nycklar som är mindre än nodens nyckel. Denna ordning gör att in-order-traversering av trädet genererar nycklar i sorterad ordning.

Egenskaper och användning: högerunderträdet används vid sökning, insättning och deletion i BST, och storleken eller höjden på högerunderträdet påverkar operationernas prestanda. Tidskomplexiteten för operationer som beror på trädet höjs eller sänks i förhållande till höjden h på trädet; generellt är O(h). I balanserade binära sökträd som AVL-träd eller RB-träd är höjden O(log n), medan den i ett odeterminerat träd kan närma sig O(n). Högerunderträdet kan vara helt tomt eller innehålla en betydande del av trädet, beroende på nyckelvärdenas fördelning. Separerad hänvisning till högerunderträdet följer ofta av dess rot, som är nodens högra barn.