15.1 Data Types

The PRB node structure adds a color and a parent pointer to the basic binary tree data structure. The other PRB data structures are the same as the ones used for TBSTs.

555. <PRB node structure 555> =
/* Color of a red-black node. */
enum prb_color 
  {
    PRB_BLACK,   /* Black. */
    PRB_RED      /* Red. */
  };

/* A red-black tree with parent pointers node. */
struct prb_node 
  {
    struct prb_node *prb_link[2];  /* Subtrees. */
    struct prb_node *prb_parent;   /* Parent. */
    void *prb_data;                /* Pointer to data. */
    unsigned char prb_color;       /* Color. */
  };

This code is included in 553.

See also:  [Cormen 1990], section 14.1.