A red black tree which contains n internal nodes has a height of O(log(n)).

Definitions:

• h(v) = height of subtree rooted at node v
• bh(v) = the number of black nodes (not counting v if it is black) from v to any leaf in the subtree (called the black-height).

Continue reading →