[prev] 65 [next]

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   colour; // relationship to parent
   RBTree left;   // left subtree
   RBTree right;  // right subtree
} node;

#define colour(tree) ((tree)->colour)
#define isRed(tree)  ((tree) != NULL && (tree)->colour == 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