15 Red-Black Trees with Parent Pointers [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

As our twelfth and final example of a table data structure, this chapter will implement a table as a red-black tree with parent pointers, or “PRB” tree for short. We use prb_ as the prefix for identifiers. Here's the outline:

553. <prb.h 553> =
<Library License 1>
#ifndef PRB_H
#define PRB_H 1

#include <stddef.h>

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

#endif /* prb.h */

554. <prb.c 554> =
<Library License 1>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "prb.h"

<PRB functions 556>