Week 4: Search Tree Data Structures and Algorithms (115)

Red-Black Trees (cont)

Red-black tree implementation:

typedef enum {RED,BLACK} Colr;
typedef struct node *RBTree;
typedef struct node {
   Item   data;   // actual data
   Colr   color; // relationship to parent
   RBTree left;   // left subtree
   RBTree right;  // right subtree
} node;

#define color(tree) ((tree)->color)
#define isRed(tree)  ((tree) != NULL && (tree)->color == RED)

RED = node is part of the same 2-3-4 node as its parent (sibling)

BLACK = node is a child of the 2-3-4 node containing the parent