一红黑数的性质
1 每个节点 red or black
2 root is black
3 叶节点 （NIL） is black
4 red node 两个孩子必须是black
5 每个节点，从该节点到通往其他子孙节点的所有路径上包含的black 节点数 是一直的。
换句话说，如果我是老祖宗，我有两个儿子，每个儿子又可能有两个儿子，一次类推，但是
我这个总有一群辈分最低的后代，我通往最低辈分的后代的所有节点中，black的个数是一致的。
二 旋转
图像使用了v_JULY_vID： 博客的内容，学习红黑树也主要参考了他的博客，在此表示衷心感谢
三 为什么插入后，红黑树的性质遭到破坏
红黑树插入之后，默认新节点的color 为红色，这是红黑树性质遭到破坏的万恶之源。
1 红黑树为空
插入的新节点即位root_node，则root_node为红色red，参看上面第二条性质，根必须为黑色。
这种违背比较好办，直接将red 改成 black
2 新插入的节点是红色，如果它的父亲节点是黑色，这没有任何关系，因为，
1）第五条性质，并不关心每个支路上有几个 red 节点。
2）第三条性质，黑节点的孩子必须是红节点，这也没有违背。
这种情况是我们最希望的，因为，不需要做任何调整，自动保持红黑树的性质。
3 最要命的情况就是 新插入节点的父亲是红色的，这就违背了 第三条性质
即红色节点的孩子必须是黑色的。 从而引发了最严重的危机。 所谓 插入后的调整，
基本是应对这种情况。
我们在此只讨论 新插入节点父亲的祖父的左孩子 的情况，如果是其父亲是祖父的右孩子对称处理即可。
我在此讨论的是为什么这么做，而不是技术细节，技术细节，推荐大家去读内核源码 或者 那谁的技术博客。
他们讲的非常好。
四 如何调整：
1 如果 该节点的父亲和叔叔，都是红色的，这种情况我们比较喜欢
如下图中N对应的节点，P是其父亲（parent），U是其叔叔（uncle),G 是祖父 grandpa
如果是这种情况，直接将其父亲和叔叔一律red改成 black (这样就不违反性质3了)
将祖父的黑色 变成重色。
即 父辈 红变黑 祖父 黑变红。
大家可能有疑惑，我为什么确定祖父是黑色的 ？
我们可以确定，祖父G原来一定是黑色的，假如 祖父原来是红色的，那么他的两个儿子应该是黑色的，
但是我们看到了父亲和叔叔都是红色的，我们变化之前性质就已经违背了，这是不可能的。这就保证了，
祖父原来一定是黑色的。
祖父 黑变红 ，父亲和叔叔 红变黑，保证了从祖父这一枝 黑色的数目没有发生变化，性质5 得以保持
后遗症 ：祖父原来是黑色的，现在变成红色的了，如果祖父的父亲也是红色的，就再次 出现问题了。
所以将当前节点N 指向 祖父，根据祖父的父亲是否是红色来决定下一步操作。即当前节点上移到祖父位置，
判断是否需要调整。
调整前
调整后
2 叔叔是黑色的。
这种情况是比较复杂的。
我们说过了，只讨论 父亲是祖父的左孩子，那么叔叔是祖父的右孩子。
这种情况分其实又分两种情况
1） 自己是父亲的左孩子，
2） 自己是父亲的右孩子。
如果自己是父亲的左孩子，这种情况比较简单。
如下图，2是当前节点， 7是父亲节点，14 是叔叔。
我们看到，自己是父亲的左孩子，父亲是祖父的左孩子，
这种情况下只需要父亲变成 黑色，祖父变成红色，以祖父为轴 右旋转，即可。
具体请看调整后的图片。
有种疑惑是，这样做了之后第五条性质 能否保持。
其实这种旋转之后，叔叔这个根系来讲，黑色的个数没啥变化，
父亲的右孩子这个根系而言，除了父亲变成了祖父，祖父变成了父亲，
就黑色的个数而言也没有发生变化。
改变后
叔叔是黑色的情况下，自己是父亲的右孩子要首先转化成，上面的情况。转化的方法是做一次旋转。
如下图：
当前节点7 ，父亲是2 ，父亲是祖父的左孩子，自己是父亲的右孩子。
以父亲为轴右旋转。 当前节点7变成父亲，父亲节点2 变成了左孩子。
这么做的好处是 旋转完之后，变成了上面一种情况，即 自己是父亲左孩子，
父亲是祖父左孩子，这种情况，我们可以处理。
办法： 以父节点为轴，左旋转
思想：把解决不了的问题，转化成可以解决的问题。
旋转后，变成了左孩子--左孩子这种情况
叔叔是黑色的情况下，
父亲是左孩子，自己是右孩子，先以父亲为轴左旋转，转化成中间这种情况
对于中间这种情况，父亲是左孩子，自己是左孩子，父亲变黑，祖父变红，以祖父为轴右旋转。
阅读(3856) | 评论(0) | 转发(0) |
