- 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(jié).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
