红黑树-算法导论
这个周看算法导论，看到红黑树，看的我云里雾里绕啊。虽然最后看懂了，据我估计，要是过一个星期不看保证忘干净，因此决定写篇博客记录下红黑树。
红黑树是二叉树的一种，所以学习红黑树必须先搞懂二叉树。
如图，一颗二叉树是按照结点（二叉树结构）组成的。每个结点可以用链表结构标示。每个结点都应该有left right p ，他们分别指向左儿子，右儿子和父结点。每个结点还应该有个关键字key。如果某个儿子结点不存在，则相应位置就是nil。跟结点是树中唯一的父结点值是nil的节点。
设x为二叉树中的一个结点，如果y是x的左子树中的一个结点，则key[y]<=key[x]。如果y是x的右子树中的一个结点，则key[x]<=key[y]
我们有很多结点，如何将他组合成符合二叉树性质的二叉树呢？
我们一般通过下面两种方式遍历二叉树中的key
树根的关键字（key）在左子树和右子树的关键字之间输出就是 中序遍历算法
树根的关键字（key）在左子树和右子树的关键字之前输出就是 前序遍历算法
从图中我们能看出只要沿着各个结点的left指针查找下去，知道遇见nil 时候为止，就是最小值，最大值正好相反。
如图，3的前趋是2， 后继是6。
前趋后继的规律是什么呢?
前趋：如果结点x的左子树为非空，则x的前趋就是做子树中的最右结点。要是x的左子树为nil ，并且有前趋y（key是最最小值对应的x是没有前趋的），那么y是x的最低祖先，并且y的右儿子也是x的祖先。（x必须出现在y的右儿子的分支中，并且y是最低祖先）
后继：如果结点x的右子树为非空，则x的后继就是右子树中的最左结点。要是x的右子树为nil ，并且有后继y（key是最大值对应的x是没有后继的），那么y是x的最低祖先，并且y的左儿子也是x的祖先。（x必须出现在y的左儿子的分支中，并且y是最低祖先）
这里一定要搞明白，因为这里是红黑树删除的基础部分。
二叉树结点的删除分三种情况。
这里针对第三种情况的删除，我们不是删除z，而是删除的是z的后继y，把y的值赋值给z，这样不破坏树中的结构。变成了只是删除了一个叶子，这个叶子的特点是 左儿子是nil 。
红黑树是一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是RED或者Black。通过对任何一条从跟到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
树中每个结点包含五个域：color，key ，left，right 和p。如果某结点没有一个子结点或者父结点，则该结点相应的指针为nil。
从图中我们能看出每个叶子节点都是nil。nil对象都是一样的。干嘛不用一个nil 代替呢。因此如下结构。
旋转应该是二叉树的性质，只是普通二叉树没必要旋转。红黑树需要旋转来平衡树结构。
结果如下。
右旋的过程只是相反而已。
左旋的作用是将右儿子变成父结点。
右旋的作用是将左儿子变成父结点。
这样变化有什么用处呢？
我们知道，红黑树就是二叉树，因此向二叉树中插入数据没有啥区别。只是不过，当我们插入结点的某些时候就破坏了红黑树性质。因此，我们需要对二叉树进行调整让其适合红黑树的特性。
下面我们应该分析什么情况下插入结点能破坏红黑树。
假如我们插入的结点是黑色的，肯定是破坏了二叉树的性质5。（除非是根节点不破坏。）
但是我们插入的结点是红色的，不一定破坏二叉树的五条性质，为了方便，我们还是将二叉树插入的结点染成红色的比较好。(情况变少)
当我们插入一个红色结点可能破坏那些性质呢？第一条和第三条肯定是不会被破坏的，恒成立的。第五条因为插入的结点是红色的肯定也是成立的。这里可能不成立的是第二条（跟结点是黑的，要是插入的结点就是根结点）和第四条（如果一个结点是红的，它的两个儿子是黑的，因为要是插入的结点的父结点是红的话，那么父父结点就不符合要求了）。
因此，红黑树的结构被破坏就两种情况，不是性质2就是性质4.
性质2好解决，将结点染成黑色的就行了。不做分析。
我们重点分析性质4破坏，我们如何修正。
我们知道性质4被破坏的条件是父节点是红色的。
如图
这里我们分情况讨论 s 的颜色。
第一种情况 ： s的结点是红色。
这个情况，我们从根到左边的黑色结点数是2 ，右边的黑色结点数是2。
那么我们如何将其变成从跟到叶子的所有路线的结点数是2还不破坏红黑树呢？
只有下面一种变化才能符合红黑树，这样从根向下就符合红黑树了。
将祖父结点（跟结点）变成红色，p 和s 结点都变成 黑节点。
从上面的结果图我们能看出来， 根父 的颜色不定，可能是红色的，也可能是黑色的，那么我们就应该让 根 当做被插入的新节点，遍历根父 的兄弟的结点的颜色情况情况。这其实就是递归了。
要是每个根父的兄弟结点都是红色的话，那么遍历到根就结束了。将根染成黑色即可。要是根父的兄弟不是红色，那么就应该进入到第二种情况了。
第二种情况：s结点是黑色的。
这种情况不管如何变化，让总结点数不变的情况下，单纯染色根本没有办法让所有结点符合红黑树特性。让从根到叶子的路径含有相同的黑色结点。 那么怎么办呢？
我们知道，二叉树可以旋转，旋转可以改变树的结构。
这里我们用根做旋转（左旋或者右旋），结果如下
我们看看旋转结果，结果1，根变成p儿子的一边黑色结点树没有变化。而x的一边黑色结点数量减少了1。那我们如何让x一边增加1呢？只有如下一种情况，将p染成黑色，根染成红色。
结果2是无法达到我们的要求的，因此我们需要抛弃掉这种情况，让s是黑的时候只能变成结果1。
结果1所有的情况下都满足红黑树，不需要进行递归了。
这里我们需要看看什么情况下，x结点是p结点的儿子而不是根结点的儿子。这里我们需要看左旋右旋逻辑图了。
因此这里我们总结下结果1 的条件
结果2 就是剩下的。那么要是结果2的情况，我们应该如何处理呢。
那么结果2 在右旋的结构图就很清晰了。如下。p的右儿子是插入的结点x。
这种情况如何解决呢？
因为x是p的右儿子，所以旋转只能是左旋转。我们以p为根节点旋转。
结果如下
这样就变成了结果1 准备右旋转的的情况了。
同理，情况2的左旋图就变成了结果1准备左旋图的情况了。
总结
这里上面的方法是算法导论给出的，下面的是自己实现的。
删除操作和二叉树的操作一样，同样的只不过是删除的时候，可能引起对红黑树性质的破坏。
这里把删除二叉树的总结搬过来
这里我们罗列下这三种情况各个删除结点的结构。
二叉树第一种情况：没有儿子的情况。
二叉树第二种情况：只有一个儿子。左儿子或者右儿子。有四种情况
二叉树第三种情况：最多有一个右儿子
我们看出来，第三种情况不是第一种情况，就是第二种情况。因此这里我们只需要研究第一种情况和第二种情况就行了。
当x是红色的时候
将x删除，我们发现红黑树的黑色结点的数量不会发生任何变化。红黑树结构正常
我们发现不管什么条件下，删除红色结点红黑树不会发生任何变化。
这里我们需要讨论下 p 和 s的颜色，我们知道p 和s 分别只有红色和黑色，并且p 和s 不能同时为红色。那么p 和s的组合情况只有三种了。
我们发现不管哪一种情况都删除x的那一支都缺少一个黑色结点。
组合1
组合一通过染色是不可能达到树的平衡的。（有人好说了，把p染成黑色，s染成红色不就行了？我刚开始也犯了这个错误，要是s的两个儿子是红色怎么办呢？红色是不参与节点数计算的。）
因此我们这里直能通过旋转来改变树的结构来看看能不能达到我们的要求。我们以p旋转看看结果如下。
这貌似也不行，因为SL 可能是红色的，违反性质4。因此我们可以看出来，p是红色的情况下，旋转一次想让红黑树平衡依赖S的两个结点的颜色。
要是p左旋，那么s的左孩子是黑色的就可以。要是p右旋，那么s的右孩子是黑色的就可以了。
因此这里讨论下s的两个孩子的颜色情况。
如果SL 和SR 都是红色怎么处理呢？
单纯的旋转根本不可能让红黑树成立。只能先改变颜色在旋转了。
颜色改变如下
要是SL 和SR都是黑色的情况下
结构图如下
这种结构图 SL SR 都是nil。这种情况下旋转一下 p就行了。
SR SL只有一个颜色是红色的。如果p的删除分支是左儿子。那么SL 是红色，只能以s先右旋转。这样就变成了 SL SR都是黑色，但是s是红色的情况。是SL ,SR变化成平衡树的中间过程
最后这种情况，和SL SR 都是黑色一样的处理。
组合2
这里我们单纯靠染色是不可能实现树平衡的。因为删除x的结点的一支的结点都是黑色的。没有可以改变的红色结点存在。怎么办呢？我们只能通过旋转将删除的节点的一支上面增加红色结点才行。这里有个s是红色的，我们需要让其到删除结点分支上。
旋转结果
这样组合2删除结点的分支上有红色结点了。到这里我们发现这个地方的树可能违反红黑树了。
违反1：根是红色的话，s是红色违反性质4.
违反2：p结点黑节点数量还是对不上。违反性质5
不过没关系，要是我们能通过染色让树平衡的话，不用再调整树的结构的话，那么组合2也就算是解决了。
貌似通过染色也解决不了这个树平衡的问题，不过违反的红黑树的地方可以减少，我们将s染成黑色，p染成红色。
这里我们发现只有 p删除结点的一支，黑色结点数量少一。正好是组合一的情况。按照组合一的情况做一次旋转就可以解决问题
组合三
这种情况是最复杂的了。我们知道S要是红色，这就是组合2的情况，要是p是红色，那么就是组合1了。那我们想办法怎么让s或者p变成红色的呢？我们先从叶子节点找红色结点，看能不能让s或者p变成红色的。肯定是可以的。不过有一定条件。这里需要依赖SL,SR的颜色了。
当SL,SR都是红色，这种变化只通过改变颜色就可以让s变成红色，变成组合2的情况。
当SL,SR 只有一个红色的时候，通过改变颜色是不能达到要求的。因此我们就需要做旋转来达到要求。
当SL SR 都是黑色。没有红色，p结点一下是不能解决这个问题的。那怎么办呢？这样只能依赖p的父类了。不过这里需要注意的是p本身不平衡，我们这里依赖p的父类的时候，p需要是平衡的。如何平衡p呢？
我们只需要将s变成红色就可以了。p就平衡了。
不过这里注意，p的这一整支的所有分支都是少黑色结点1 的。
这里我们注意到p只有一个儿子。这里我们需要把p当成删除结点x的一个儿子。这样就转换成了x带一个儿子的情况了。这种情况如何平衡树。下面讨论一个孩子的时候包含，暂时不在这里讲解。
先拿一种情况分析 x是p的左儿子，x有一个左儿子
分析L 如果L是黑色的话，肯定是nil。因此可以将这种只有一个儿子的情况转换成没有儿子的情况。也可以这么说，要是x有儿子，儿子的颜色一定不是黑色。而是红色。如图
