红黑树

对某个节点左旋转是把某个节点变成左节点
对某个节点右旋转是把某个节点变成右节点

1、根节点是黑节点
2、叶节点是黑节点，也叫NIL节点，不存储信息。
3、新插入节点为红节点
4、红节点的两个子节点为黑节点
5、任何节点到叶节点的路径中黑节点个数一致

黑红树做插入、删除操作时，需要通过旋转、着色完成上述要求。

黑红树与平衡二叉树差别：
红黑树放弃追求严格平衡，通过3次以内旋转完成平衡
平衡二叉树追求严格平衡，做插入、删除操作时需要的旋转操作次数不可控制。

红节点不连续，黑节点可以连续，所以最短路径是连续黑节点，最长路径是黑红节点交替出现，也就是最长路径长度为最短路径长度两倍。