红黑树

 红黑树顾名思义就是节点是红色或者黑色的平衡二叉树，它通过颜色的约束来维持着二叉树的平衡。

对于一棵有效的红黑树二叉树而言我们必须增加如下规则：

       1、每个节点都只能是红色或者黑色

       2、根节点是黑色

       3、每个叶节点（NIL节点，空节点）是黑色的。

       4、如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

       5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

   图解  http://www.sohu.com/a/201923614_466939