Invariants

  • Root node is black, leaf nodes are EMPTY black nodes
  • Parent and child can NOT be both R
  • From any node, the paths to ALL leaves pass through same # of B

Insertion

  • Use the standard BST way to insert a R leaf node, and then try to fix the invariant
  • Case 1: P is B, we are good, because the old paths to the P can not extened to the current node (the new leaf that replaced the old P), with no additional cost
  • Case 2: P is R, and sibling of P is R too
  • Paint U and P B, and G R
  • RECURSIVELY fix the invariants with G (now R) as the leaf param
  • Case 3: P is R, and U is B or U does not exist
  • if necessary, left rotate or right rotate P so that C is on the “outside” of the G, i.e., it is not the left-right or right-left of G. No color change at this step
  • Then rotate the grandparent to make C the new grand parent, and paind the old G red, C black

Removal

  • Idea similar to BST - we just find the in-order predecessor or successor to the node , swap the value, and then delete that predecessor/successor node
  • However, the actual cases are complicated. If both P and child are B, there are SIX cases to consider