红黑树

1. 每个结点或是红的，或是黑的

2. 根节点是黑的

3. 每个叶结点是黑的

4. 如果一个结点是红的，则它的两个儿子都是黑的

5. 对每个结点，从该结点到其子孙节点的所有路径上包含相同数目的黑结点

插入

1. 插入的节点是红色

2. 如果父节点是黑色，不用进行调整
3. 如果父节点是红色
   1. 叔叔是空的，旋转+变色
   2. 叔叔是红色，父节点和叔叔变黑色，祖父节点变红色
   3. 叔叔是黑色，旋转+变色