15.1 Data Types [ToC] [Index]     [Skip Fwd]     [Prev] [Up] [Next]

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.

553. <PRB node structure 553> =
/* 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 551.

See also:  [Cormen 1990], section 14.1.