Interactive Red-Black Trees

Animation step duration:

Insert value:

  1. Red nodes don't have red parents
    1. Red parent and red uncle - flip colours [eg. 2 1 3 4]
    2. Red parent and black or no uncle; parent and child same orientation - rotate [eg. 1 2 3]
    3. Red parent and black or no uncle; parent and child opposite orientation - double rotate [eg. 1 3 2]
  2. The root node must be black