Listing 5

struct rb_tree_node_base
{
  enum color_type {red, black};
  color_type color;
  rb_tree_node_base *parent;
  rb_tree_node_base *left;
  rb_tree_node_base *right;
};

template <typename T>
struct rb_tree_node: rb_tree_node_base
{
  T value_field;
};

template <typename T>
class rb_tree
{
private:
  rb_tree_node<T> *header;
  // and much more
};