www.delorie.com/gnu/docs/avl/libavl_113.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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