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 with n nodes has height at least log2 (n + 1) but no more than 2 * log2 (n + 1). A red-black tree with height h has at least pow (2, h / 2) - 1 nodes but no more than pow (2, h) - 1.

For comparison, an optimally balanced BST with n nodes has height ceil (log2 (n + 1)). An optimally balanced BST with height h has between pow (2, h - 1) and pow (2, h) - 1 nodes.