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

The last chapter saw us implementing a library for one particular type of balanced trees. Red-black trees were invented by R. Bayer and studied at length by L. J. Guibas and R. Sedgewick. This chapter will implement a library for another kind of balanced tree, called a red-black tree (see red-black tree). For brevity, we'll often abbreviate “red-black” to RB.

Insertion and deletion operations on red-black trees are more complex to describe or to code than the same operations on AVL trees. Red-black trees also have a higher maximum height than AVL trees for a given number of nodes. The primary advantage of red-black trees is that, in AVL trees, deleting one node from a tree containing n nodes may require log2 (n) rotations, but deletion in a red-black tree never requires more than three rotations.

The functions for RB trees in this chapter are analogous to those that we developed for use with AVL trees in the previous chapter. Here's an outline of the red-black code: 

194. <rb.h 194> =
<Library License 1>
#ifndef RB_H
#define RB_H 1

#include <stddef.h>

<Table types; tbl => rb 15>
<RB maximum height 197>
<BST table structure; bst => rb 28>
<RB node structure 196>
<BST traverser structure; bst => rb 62>
<Table function prototypes; tbl => rb 16>

#endif /* rb.h */


195. <rb.c 195> =
<Library License 1>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "rb.h"

<RB functions 198>

See also:  [Cormen 1990], chapter 14, “Chapter notes.”