www.delorie.com/gnu/docs/avl/libavl_169.html

search

	Buy GNU books!

GNU libavl 2.0.1

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.

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

<@xref{\NODE\, , License.>,1} #include <assert.h> #include <stdio.h> #include <stdlib.h> #include "trb.h" <@xref{\NODE\, , TRB functions.>,336}

10.1 Data Types
10.2 Operations
10.3 Insertion
10.4 Deletion
10.5 Testing