红黑树

红黑树具有以下特点：

1. 每个结点不是红色就是黑色；
2. 不可能有连在一起的红色结点；
3. 根结点都是黑色结点；
4. 每个红色结点的子结点都是黑色结点；
5. 任一结点到其子树中每个叶子结点的路径都有相同数量的黑色结点。

任何一颗红黑色都必须满足以上5个特点，当新插入一个结点，不满足以上结点时，此时红黑树会进行旋转和变色。
下面说下红黑树旋转和颜色变化的规则：

• 变颜色的情况：当前结点的父亲是红色，且它的叔叔结点也是红色（叔叔结点：祖父结点的子结点）

  • 把父节点设为黑色
  • 把叔叔也设为黑色
  • 把祖父也就是父亲的父亲设为红色
  • 把指针定义到祖父结点设为当前要操作的

• 左旋：当前父结点是红色，叔叔是黑色的时候，且当前的结点是右子树。左旋 以父结点作为左旋

• 右旋：当前父结点是红色，叔叔是黑色的时候，且当前的结点是左子树。右旋
  • 把父结点变为黑色
  • 把祖父结点变为红色 （爷爷）
  • 以祖父结点旋转（爷爷）