概念

1.每个结点是红的或者黑的
2.根结点是黑的
3.每个叶子结点是黑的
4.如果一个节点是红的，则它的两个儿子都是黑的
5.对每个节点，从该结点到其子孙结点的所有路径上包含相同数量的黑节点

旋转

1.左旋
2.右旋

x 左旋-> y
↖ ↗
y <-右旋 x