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. 

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

#include <stddef.h>

<Table types; tbl => trb 14>
<RB maximum height; rb => trb 195>
<TBST table structure; tbst => trb 250>
<TRB node structure 335>
<TBST traverser structure; tbst => trb 267>
<Table function prototypes; tbl => trb 15>

#endif /* trb.h */


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

<TRB functions 336>