12.1 Data Types

Like any right-threaded tree node, an RTRB node has a right tag, and like any red-black tree node, an RTRB node has a color, either red or black. The combination is straightforward, as shown here.

456. <RTRB node structure 456> =
/* Color of a red-black node. */
enum rtrb_color 
  {
    RTRB_BLACK,                     /* Black. */
    RTRB_RED                        /* Red. */
  };

/* Characterizes a link as a child pointer or a thread. */
enum rtrb_tag 
  {
    RTRB_CHILD,                     /* Child pointer. */
    RTRB_THREAD                     /* Thread. */
  };

/* A threaded binary search tree node. */
struct rtrb_node 
  {
    struct rtrb_node *rtrb_link[2]; /* Subtrees. */
    void *rtrb_data;                /* Pointer to data. */
    unsigned char rtrb_color;       /* Color. */
    unsigned char rtrb_rtag;        /* Tag field. */
  };

This code is included in 454.