Buy GNU books!
|[ < ]||[ > ]||[ << ]||[ Up ]||[ >> ]||[Top]||[Contents]||[Index]||[ ? ]|
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 \ASCII\ - 1, 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 \ASCII\\rceil, ceil (log2 (n + 1))}. An optimally balanced BST with height h has between \ASCII\, pow (2, h - 1)} and pow (2, h) - 1 nodes.
See also: [ Cormen 1990], lemma 14.1; [ Sedgewick 1998], property 13.8.
|webmaster donations bookstore||delorie software privacy|
|Copyright © 2003 by The Free Software Foundation||Updated Jun 2003|