Red-Black Tree

1. Root is black
2. Leaf(NIL) is black
3. If node is red, its children are black
4. For each node, all simple paths from nide to descendant leaves contain the same number of black nodes.

N nodes --------> hieght : 2lg(n+1)

LEFT-ROTATE
Y = X.right
Target: 把X放到Y.left 的位置

y = x.right    x.right = y.left if y.left != T.nil       y.left.p = x       y.p = x.p if x.p == T.nil       T.root - y elseif x--x.p.left       x.p.left = y else x.p.right - y       y.left = x x.p = y