www.delorie.com/gnu/docs/avl/libavl_113.html | search |
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 | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |