9 Threaded Red-Black Trees [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

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. 

335. <trb.h 335> =
<Library License 1>
#ifndef TRB_H
#define TRB_H 1

#include <stddef.h>

<Table types; tbl => trb 15>
<RB maximum height; rb => trb 197>
<TBST table structure; tbst => trb 252>
<TRB node structure 337>
<TBST traverser structure; tbst => trb 269>
<Table function prototypes; tbl => trb 16>

#endif /* trb.h */


336. <trb.c 336> =
<Library License 1>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "trb.h"

<TRB functions 338>