[prev] 119 [next]

Red-Black Tree Insertion

Insertion is more complex than for standard BSTs
  • splitting/promoting implemented by rotateLeft/rotateRight
  • several cases to consider depending on colour/direction combinations
New nodes are always red by default: 

RBTree newNode(Item it) {
   RBTree new = malloc(sizeof(Node));
   assert(new != NULL);
   data(new) = it;
   color(new) = RED;
   left(new) = right(new) = NULL;
   return new;
}