红黑树

红黑树 —— 红黑规则及添加节点的规则

红黑规则

• 每一个节点都是红色或黑色的
• 根节点是黑色的
• 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每一个叶节点（Nil）是黑色的
• 不能出现两个红色节点相连（如果节点是红色的，则他的子结点必须是黑色的）
• 对于每一个节点，到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点

节点的添加规则

添加节点时，默认添加的节点为红色（添加红色效率高）

添加节点的规则：

1. 根节点位置：直接变为黑色

2. 非根节点位置

   1. 父节点为黑色：不需要操作

   2. 父节点为红色

      1. 叔叔节点为红色：

         将父节点、叔叔节点设为黑色，将祖父节点设为红色，如果祖父节点为根节点，则将根节点再次变为黑色

      2. 叔叔节点为黑色：

         将父节点设为黑色，祖父节点设为红色，以祖父节点为支点进行旋转（左高右旋，右高左旋）