红黑树4个性质
1. 节点要么红要么黑
2. 根节点和空节点是黑
3. 红节点的父节点一定是黑（或说红节点的两个子节点一定是黑，或说不能有两个红节点为父子节点）
4. 从根到空节点的黑节点数相同

插入

插入新节点时，新节点是红，只可能违反性质3。考虑新节点N、父节点P、叔节点U、祖节点G，这时N、P是红（违反性质3），G是黑（不违反性质3），根据U是红或黑、P和N是左子节点或右子节点分情况讨论，实际上只有三种情况：

1. U是红。这时把P和U变黑、G变红就行
接下来U是黑，分两种情况：
2. 从N到P、从P到G的路线是z形的
3. 从N到P、从P到G的路线是直的
情况2，经过一次P上的旋转，可以捋直变成情况3
情况3，只要G上一次旋转，然后交换P和G的颜色

现在G的子树满足红黑树性质，而G自己可能变红违反红黑树性质，但我们把N的问题向上推到了G。依样继续，最后的最后把问题推到根节点，不管根节点是什么颜色，直接变成黑色就行。

见ctci p639。情况2和3的旋转是标准的旋转操作，根据路线是z形的还是直的来操作，AVL树中也用这种旋转。