- Root is black
- Leaf(NIL) is black
- If node is red, its children are black
- 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