[prev] [index] [next]

Red-Black Tree Insertion

Insertion is more complex than for standard BSTs
  • need to recall direction of last branch (L or R)
  • need to recall whether parent link is red or black
  • splitting/promoting implemented by rotateL/rotateR
  • several cases to consider depending on colour/direction combinations
We first consider some of the components of this algorithm.

Assume: 

#define L(t)   (((t) == NULL) ? NULL : (t)->left)
#define R(t)   (((t) == NULL) ? NULL : (t)->right)
#define red(t) ((t) != NULL && (t)->colour == RED)