16 红黑树

红黑树

• 
  红黑树的规则

1. 节点是红色或黑色的（必须有这个两个颜色的其中一个哦）。
2. 规定根节点是黑色的。
3. 每个叶子节点（就是这个树的末梢）都必须有空节点（这里为NIL节点）使得所有的叶子节点都是补齐左右的，然而这个补齐了‘末梢’（NIL节点）必须是黑色的。
4. 每个红色节点的两个子节点都是黑色的，从每个叶子到根的所有路径上不能有两个连续的红色节点。
5. 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点（NIL节点也是黑色节点哦）。

红黑树的相对平衡