数据结构学习——红黑树

红黑树（red-black tree）,满足以下规则：

1. 节点是红色或黑色
2. 根是黑色
3. 所有叶子都是黑色（叶子是NIL节点）
4. 每个红色节点必须有两个黑色的子节点（从每个叶子到根的所有路径上不能有两个连续的红色节点）
5. 从任一节点到其每个叶子(NIL)的所有简单路径都包含相同数目的黑色节点

事实上，如上所有的规则都只想做一件事，让二叉树尽可能的平衡。

1. 对于定义4，即代表了红黑树中不可能出现两个连续的红色节点，也就是说支树上最多是红黑交替的情况(可以出现连续的黑节点)。
2. 对于定义5，结合定义4，即代表红黑树中最长路径最多是最短路径的两倍。