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).