ADS, Red-Black Diagrams

Supplement to BST notes.

• [3.15] Standard Insert and colour red. If red-red violation,
  • Uncle is red \(\to\) recolour parent, uncle and grandparent.

  

  • Uncle is black, zig-zag. Rotate node with parent.

  

  • Uncle is black, zig-zig. Rotate parent with grandparent. Recolour root.