• a Red-Black Tree enforces ‘balance’ on a binary search tree
• this self-balancing binary search tree has the following properties →
  • every node is either red or black
  • the root is black
  • every null link is black
  • if a node is red, both children are black
  • all paths from the root to a null link have the same number of black nodes/links after the root (a.k.a. black height)

Height

insert(k)

Left-Leaning Trees

oops — will finish whenever I remember Lol