6.2 Data Types

Red-black trees need their own data structure. Otherwise, there's no appropriate place to store each node's color. Here's a C type for a color and a structure for an RB node, using the rb_ prefix that we've adopted for this module:

196. <RB node structure 196> =
/* Color of a red-black node. */
enum rb_color 
  {
    RB_BLACK,   /* Black. */
    RB_RED      /* Red. */
  };

/* A red-black tree node. */
struct rb_node 
  {
    struct rb_node *rb_link[2];   /* Subtrees. */
    void *rb_data;                /* Pointer to data. */
    unsigned char rb_color;       /* Color. */
  };

This code is included in 194.

The maximum height for an RB tree is higher than for an AVL tree, because in the worst case RB trees store nodes less efficiently:

197. <RB maximum height 197> =
/* Maximum RB height. */
#ifndef RB_MAX_HEIGHT
#define RB_MAX_HEIGHT 128
#endif

This code is included in 194, 335, 454, and 553.

The other data structures for RB trees are the same as for BSTs or AVL trees.

Exercises:

1. Why is it okay to have both an enumeration type and a structure member named rb_color? [answer]