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


GNU libavl 2.0.1

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

7. Red-Black Trees

The last chapter saw us implementing a library for one particular type of balanced trees. Red-black trees were invented by R. Bayer and studied at length by L. J. Guibas and R. Sedgewick. This chapter will implement a library for another kind of balanced tree, called a red-black tree (see red-black tree). For brevity, we'll often abbreviate "red-black" to RB.

Insertion and deletion operations on red-black trees are more complex to describe or to code than the same operations on AVL trees. Red-black trees also have a higher maximum height than AVL trees for a given number of nodes. The primary advantage of red-black trees is that, in AVL trees, deleting one node from a tree containing n nodes may require log2 (n) rotations, but deletion in a red-black tree never requires more than three rotations.

The functions for RB trees in this chapter are analogous to those that we developed for use with AVL trees in the previous chapter. Here's an outline of the red-black code:

 
&#60;@xref{\NODE\, , License.&#62;,1}
#ifndef RB_H
#define @cindex RB_H macro
RB_H 1
#include &#60;stddef.h&#62;
&#60;@xref{\NODE\, , Table types; tbl =>.&#62; rb,14}
&#60;@xref{\NODE\, , RB maximum height.&#62;,195}
&#60;@xref{\NODE\, , BST table structure; bst =>.&#62; rb,27}
&#60;@xref{\NODE\, , RB node structure.&#62;,194}
&#60;@xref{\NODE\, , BST traverser structure; bst =>.&#62; rb,61}
&#60;@xref{\NODE\, , Table function prototypes; tbl =>.&#62; rb,15}
#endif /* rb.h */

 
&#60;@xref{\NODE\, , License.&#62;,1}
#include &#60;assert.h&#62;
#include &#60;stdio.h&#62;
#include &#60;stdlib.h&#62;
#include &#60;string.h&#62;
#include "rb.h"
&#60;@xref{\NODE\, , RB functions.&#62;,196}

See also: [ Cormen 1990], chapter 14, "Chapter notes."

7.1 Balancing Rule  
7.2 Data Types  
7.3 Operations  
7.4 Insertion  
7.5 Deletion  
7.6 Testing  


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

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003