深入分析-红黑树

红黑树定义

1. 每个节点或是黑色或是红色
2. 根节点是黑色
3. 每个叶节点是黑色（叶节点为空节点）
4. 如果一个节点是红色，则它的子节点必须是黑色
5. 从一个节点到该节点的所有叶节点的路径包含相同数目的黑色节点

规则

• 当前红色，父红色，叔叔空的：旋转 + 变色（子节点变红色）
• 当前红色，父红色，叔叔红色：父+叔叔变黑色，祖父变红色
• 当前红色，父红色，叔叔黑色：旋转 + 变色（子节点变红色）