# 红黑树
# 红黑树的规则
- 1、节点是红色或黑色
- 2、根节点是黑色
- 3、每个叶子节点都是黑色的空节点（NIL节点）
- 4、每个红色节点的两个子节点都是黑色（从每个叶子到根的所有路径树干不能有两个连续的红色节点）
- 5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
# 红黑树的相对平衡
前面的约束，确保了红黑树的关键特性：
- 从根到叶子的最长可能路径，不会超过最短可能路径的两倍长
- 结果就是这个数基本是平衡的
- 虽然没有做到绝对平衡，但是可以保证在最坏的情况下，依然是高效的
为什么可以做到最长路径不超过最短路径的两倍呢？
性质4决定了路径不能有两个相连的红色节点。
最短的可能路径都是黑色节点
最长的可能路径是红色和黑色交替
性质5所有的路径都有相同数目的黑色节点
这就表明了没有路径能多余任何其他路径的两倍长。
# 红黑树的变色
插入一个新节点时，有可能树不在平衡，可以通过三种方式，让树保持平衡。
- 换色
- 左旋转
- 右旋转
# 变色
为了重新符合红黑树的规则，尝试把红色节点变为黑色节点，或者把黑色节点变为红色。
首先，需要知道插入的新节点通常是红色节点。因为在插入节点为红色的时候，有可能插入一次是不违反红黑树任何规则的。而插入黑色节点，必然会导致有一条路径上多了黑色节点，这是很难调整的。红色节点可能导致出现红红相连的情况，但是这种情况可以通过颜色调换和旋转来调整。
# 左旋转
逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己称为自己的左孩子。
图中，身为右孩子的Y取代了X的位置，而X变成了Y的左孩子。此为左旋转。
问题：如果他们有子树是否会影响旋转？（不会受影响）
以 50 为中心，逆时针旋转后：
# 右旋转
顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己称为自己的右孩子。
图中，身为左孩子的Y取代了X的位置，而X变成了Y的右孩子。
问题：如果他们有子树是否影响旋转呢？（不会受影响）
以 75 为中心，顺时针旋转后：
# 插入数据
假设要插入的节点为N，其父节点为P，其祖父节点为G，其父亲的兄弟节点为U（即P和U是同一个节点的子节点）
情况一：
新节点N位于树的根节点上，没有父节点。 在这种情况下，直接将红色变成黑色即可，这样满足性质2
情况二：
新节点的父节点P是黑色 性质4没有失效（新节点是红色的），性质5也没有任何问题。 尽管新节点N有两个黑色的叶子节点Nil，但是新节点N是红色的。所以通过他的路径中黑色节点的个数依然相同。满足性质5
情况三： P为红色，U也为红色
操作步骤： 将P和U变换成黑色，并且将G变换成红色。现在新节点N有了一个黑色的父节点P，所以每条路径上黑色节点数目没有变化。而从最高的路径上，必然都会经过G节点。所以那些路径的黑色节点的数据也是不变的，符合性质5。
可能出现的问题： N的祖父节点G的父节点也可能是红色的，这样就违反了性质3，可以递归的调整颜色。但是如果递归调整颜色到了根节点，就需要进行旋转了。
情况四：
N的父节点是红色，叔叔节点是黑色，N是左子节点。（父红叔黑，N是左儿子）
操作方案：（父黑祖红，叔不变，右旋转、先变色在旋转即可）
对祖父节点G进行依次右旋转。 在旋转中，以前的父节点P现在是新节点，以前祖父节点G现在是叔叔节点。 交换以前的父节点P和祖父节点G的颜色（P为黑色，G变成红色，G以前一定是黑色的） B节点向右平移，变为G节点的左子节点。
情况五：
N 的叔叔节点是黑色节点，且N是右子节点（父红叔黑祖黑，N是右儿子）
操作方案：
- 以P为根左旋转
- 将P作为新插入的红色节点考虑即可
- 自己变黑
- 祖父变红
- 以祖为根，进行右旋转
对P节点进行依次左旋转、形成情况四的结果。 对祖父节点G进行依次右旋转，并且改变颜色即可
将P和B看成一个整体来对待
案例：依次插入 10 9 8 7 6 5 4 3 2 1
10
插入红色节点10
将节点10的颜色变为黑色
9
创建红色新节点9
放到10的左侧，不需要任何变化
8