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


GNU libavl 2.0.1

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

10. Threaded Red-Black Trees

In the last two chapters, we introduced the idea of a threaded binary search tree, then applied that idea to AVL trees to produce threaded AVL trees. In this chapter, we will apply the idea of threading to red-black trees, resulting in threaded red-black or "TRB" trees.

Here's an outline of the table implementation for threaded RB trees, which use a trb_ prefix.

 
&#60;@xref{\NODE\, , License.&#62;,1}
#ifndef TRB_H
#define @cindex TRB_H macro
TRB_H 1
#include &#60;stddef.h&#62;
&#60;@xref{\NODE\, , Table types; tbl =>.&#62; trb,14}
&#60;@xref{\NODE\, , RB maximum height; rb =>.&#62; trb,195}
&#60;@xref{\NODE\, , TBST table structure; tbst =>.&#62; trb,250}
&#60;@xref{\NODE\, , TRB node structure.&#62;,335}
&#60;@xref{\NODE\, , TBST traverser structure; tbst =>.&#62; trb,267}
&#60;@xref{\NODE\, , Table function prototypes; tbl =>.&#62; trb,15}
#endif /* trb.h */

 
&#60;@xref{\NODE\, , License.&#62;,1}
#include &#60;assert.h&#62;
#include &#60;stdio.h&#62;
#include &#60;stdlib.h&#62;
#include "trb.h"
&#60;@xref{\NODE\, , TRB functions.&#62;,336}

10.1 Data Types  
10.2 Operations  
10.3 Insertion  
10.4 Deletion  
10.5 Testing  


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