红黑树

一种自平衡二叉搜索树。
每一个节点是黑或红，红黑树不是通过高度平衡的，而是通过红黑规则实现。

红黑规则

1. 每个节点要么是红色的，要么是黑色的，根节点必须是黑色的。
2. 如果一个节点没有子节点或者父节点，则该节点相应的指针属性为Nil，这些Nil视为叶节点，叶节点是黑色的
3. 如果一个节点是红色的，那么它的两个子节点必须是黑色的（不能出现两个红节点相连的情况）
4. 对每一个节点来说，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点

   3和4就决定了这棵树是一个平衡二叉树