Data Struct - Balanced Trees

0.0.1 Regular BST

          ^                   50
          |               /        \
          |           25              75
 height=3 |         /    \          /    \
  n=15    |       10     30        60     90
          |      /  \   /  \      /  \   /  \
          V     4   12 27  40    55  65 80  99

0.0.2 RB Tree

• root is black
• null nodes are black (Children of the leafs)
• If a node is red, it’s children are black

Left Rotation

      x              y
     / \            / \
    a   y    =>    x   c
       / \        / \  
      b   c      a   b   

Right Rotation

      y              x
     / \            / \
    x   c    =>    a   y
   / \                / \
  a   b              b   c

Recolor