6.1.1 Analysis |

As we were for AVL trees, we're interested in what the red-black balancing rule guarantees about performance. Again, we'll simply state the results:

A red-black tree withnnodes has height at leastlog2(n+ 1) but no more than 2 *log2(n+ 1). A red-black tree with heighthhas at leastpow(2,h/ 2) - 1 nodes but no more thanpow(2,h) - 1.For comparison, an optimally balanced BST with

nnodes has heightceil(log2(n+ 1)). An optimally balanced BST with heighthhas betweenpow(2,h- 1) andpow(2,h) - 1 nodes.

**See also:**
[Cormen 1990], lemma 14.1;
[Sedgewick 1998], property 13.8.