在学习红黑树的时候，我发现很多博客都没有把红黑树讲清楚，于是我就去wikipedia看红黑树的定义。中文网站（链接）介绍的红黑树总有机翻的味道，介绍的不是特别清楚，我在这里拿英文网站（链接）配套的做一下介绍。可能会有大段文字絮絮叨叨，但是我都是尽可能地把思路理了出来。
红黑树：
是一种自平衡的二叉查找树，它的成查找，插入和删除时间复杂度均为O(logn) 。许多人一开始学习红黑树拿的是二叉平衡树做比较，这样的话会很难理解，实际上红黑树等同于2-3-4树，在2-3-4树上的插入和删除操作也等同于红黑树中的颜色翻转核旋转。
红黑树的性质：
红黑树依然是一个二叉查找树，但是每个节点都带有颜色属性，节点要么是红色，要么是黑色。
在拥有二叉查找树的性质前提下，红黑树的性质如下：
1.节点是红色或者黑色
2.根是黑色
3.所有叶子都是黑色叶子（所有的叶子都为空NIL）
4.从每个叶子到根的所有路径上不能有两个连续的红色节点（红色节点不直接相连）
5.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
如下图：
红黑树高效的原因：
虽然我的图例上红黑树是红黑相间的，而且很多人在开始学习的时候认为红黑树的颜色的按层次相间，但是实际上这个看法是错误的。红黑树的5个性质只为了确保一个性质：从根到叶子的最长距可能路径离不多于最短可能路径的两倍长。这个性质区别于平衡二叉树，使得红黑树是大致平衡的。由于插入、删除核查找某个值得最坏情况时间都要求与树得高度成比例，这个高度理论上上限允许最坏情况下都是高效的。
为什么叶子节点为空节点：
为了方便插入和删除，使得红黑树中叶子节点为空节点（Null），而且将其定义为黑色，这一点在讲插入的时候会提到。
操作
由于每个红黑树也是二叉查找树，因此红黑树上的只读操作与普通二叉查找树相同，然而红黑树的插入删除有可能导致失去红黑树的性质，因此需要O(logn)的颜色变更，和不超过三次的旋转（插入是俩次），使得时间为O(logn)。
插入
首先明确的一点，我们要插入的节点首先是红色的，然后再根据插入的情况进行调整。这个时候叶子设为黑色空节点的优势在于，空节点意味着我可以用插入的节点替换该为空的位置，如果插入的节点颜色是黑色，则会使得根到叶子的路径上多出一个额外的黑节点，这是很难调整的。如果插入的节点为红色，不会出现上面的情况，但是会导致俩个连续红色节点冲突，这个时候，就可以通过改变颜色和树旋转来调整。
引入三个定义：
左旋
友旋
叔父节点
值得注意的是
性质4只在增加红色节点，将黑色节点变为红色，或做旋转的时候受到威胁。
性质5只在增加黑色节点，红色节点变为黑色，或做旋转的时候受到威胁。
在下面的示意图中，设插入的节点为N，N的父亲节点为P，N的祖父节点为G，N的叔父节点为U。
case1：新节点N插入后位于树的根上，即没有父亲节点，这种情况下，把N变为黑色，满足性质2，它的每个路径上黑节点数目加一（空节点），满足性质5。
case2：新节点N插入后父节点P为黑，性质4满足，性质5满足。
注意，下面的情况是在父节点为非根节点的情况下进行的，因为这些情况父节点为红，因此父节点也有自己的兄弟节点，尽管在case4，case5的情况下该叔叔节点可能为黑色空节点。
case3：如果父节点P和叔父节点U都为红，此时不管N是插P的左边还是右边，都属于case3。以插左边为例，性质4不满足，将P，U变黑，G变红。但是有可能G的父节点是红色的，违法了性质4，也有可能G是根节点，违反了性质4，此时将G向上递归进行case1检查（把G当成是一个新加入的节点）。
注意:下面的情况，我们假定P是G的左子节点，如果是右子节点，case4和case5的左右需要对调。
case4：父亲节点P为红而叔父节点U为黑（或者空），并且新节点N是P的右子节点，P是S的左子节点（这么讲比较麻烦，看图）。这种情况下，对P进行左旋，此时依然违反性质4，但是我们把问题转换成了case5，进入case5。
case5：相对于case4，现在红色冲突跑到左边去了，你也可以把这个情况看成是case4的第二步。此时父子关系被重新改变了如下图，我们以新的父子关系为准，将新的父亲节点P右旋，以前通过NPU三个系欸但的任何一个所有路径都要通过G，现在需要通过P，于是将P，G变色。满足性质4，5。
删除：
删除的问题可以转换成如下问题：
如果需要删除的节点有俩个儿子，那么问题可以被转化成删除另一个只有一个儿子的节点的问题（这里的儿子为非叶子节点的儿子）。因为对于二叉查找树而言，在删除带有俩个非叶子儿子的节点的时候，步骤是这样的：我们要么找到它的左子树中的最大元素、要么找到它右子树中的最小元素，并且它们的值转移到需要删除的节点中，然后把删除我们复制出的值的那个节点。对于要删除的那个复制出值的那个节点，它一定是有小于俩个非叶子的儿子（要么只有一个非叶子儿子，要么只有空叶子）。此时只是复制了一个值，没有没有违反任何性质。
这样，对于红黑树，问题就简化为如何删除最多只有一个儿子的节点，同时还要注意一下颜色的变化问题（如果它的俩个儿子均为空，即均为黑色叶子，那么我们就把其中一个叶子当成儿子）。
如果我们删除一个红色节点，那么它的父亲和儿子一定是黑色的，我们可以简单的用黑色的儿子替换它，并不会破坏性质3，4，而且少了一个红色节点对性质5也没有影响。
如果我们删除一个黑色节点的时候，如果它替上来的儿子是红色，且先不管删除的黑色节点父亲是什么颜色，首先会破坏性质5。因此我们把该红色儿子变色，则曾经通过它的所有路径将通过它的黑色儿子，保证了性质5，而且相对的，上面的性质4也被保持了。
所以，需要特殊讨论的只有在要删除的节点和它的儿子二者都是黑色的时候。这种情况下该节点的俩个儿子都是叶子节点（否则违反性质5）。
我们首先把要删除的节点替换成它的儿子N，称呼它的兄弟S，称呼它的父亲P，SL称呼S的左二子，SR称呼S的右儿子。
注意：如果N和它的初始父亲是黑色的，那么删除它的父亲导致通过N的路径都比不通过它的路径少一个黑色节点，违反了性质5，树需要重新平衡。
case1：N是新的根，那么就做完了，我们从所有路径中都去除了一个黑色节点，什么性质都被保持了。
case2:S是红色的，这种情况下，中文维基百科上的图是错的。我们拿英文维基百科为例。由于P的左子边少了一个黑色节点，我们要对P进行左旋，S成为了祖父节点，此时导致所有需要通过祖父节点的黑色节点都少了一个，因此将S变色，此时导致从祖父节点出发经过SL的简单路径黑色节点增多了，因此将P变色。但是此时还是违反了性质5。因此根据情况进入case4,5,6进行调节。
case3：如果N的父亲，S和S的儿子都是黑色的，那么将S变红。但是由于所有通过P的路径都比不通过P的路径要少一个黑色节点，那么又要重新回到case1，在P上重新做平衡处理。
case4：S和S的儿子都是黑色，而N的父亲是红色。看起来就像我们case2举例的第二部分操作。这个时候，让P,S互换颜色，这不影响不通过N的路径的黑色节点数目，但是通过N的路径上对黑色节点数目增加了一个，性质5满足.
case5：这种情况我们不讨论P的颜色，因为P的俩个儿子都是黑色的，P点可黑可红。S是黑色，SL是红色，SR是黑色，N是S父亲的左儿子。我们在S上做右旋转，然后将S,SL变色。在转换完成的子树上，SL成为了根节点，且所有路径满足性质。这样，N就有了一个黑色的兄弟。这个情况下N这边的问题还是没有解决，于是转到case6。
case6：这里维基百科中文的图也是有问题，换成英文维基百科的图。S是黑色，SL是黑色，SR是红色，同样我们不关心P的颜色。此时对P进行左旋，将其置为黑色，补上了N这边少的黑色节点，将SR置为黑色，补上了由于S成为祖父节点所失去的黑色节点，将S置为原来P的颜色，保证了通过祖父节点的所有简单路径的黑色节点数不变。
