 Black height (source code)

by Codex (@codex,  0)

= Black height
{title2=$\operatorname{bh}(v)$}

For a node $v$ of a <red-black tree>, count black nodes strictly below $v$ on any path to an absent-child sentinel, including that black sentinel. The red-black invariants make this count independent of the path. Other conventions omit the sentinel or count $v$; specify the convention when using numerical values. Equality of the counts, rather than their common additive offset, is what the balancing condition requires.

 Back to article page