基本内容来自http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html
和维基百科https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91
定义
红黑树是每个节点都带有颜色属性的二叉查找树颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：
- 节点是红色或黑色。
- 根是黑色。
- 所有NULL结点称为叶子节点，且认为颜色为黑。
- 所有红节点的子节点都为黑色。
- 从任一节点到其每个叶子的所有简单路径(不往回走)都包含相同数目的黑色节点。
Paste_Image.png
1到5性质保证了红黑树的平衡性能，即该树上的最长路径不可能会大于2倍最短路径。到底是如何保证，如下所示：
由性质5可知从根节点走到叶子节点的最短路径经过的节点一定全都是黑色节点。
由性质4可知红色节点不能相连，所以最长的路径经过的节点是红黑相间的，所以最长路径最多为最短路径的两倍，即
最长路径<=2*最短路径。
所以确保了红黑树不会过多失衡。
一棵含有n个节点的红黑树的高度至多为2log(n+1)
操作
因为每一个红黑树也是一个特殊的二叉查找树。
因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。
然而，在红黑树上进行插入操作和删除操作会导致不再匹配红黑树的性质。
恢复红黑树的性质需要少量O(logn)的颜色变更（实际是非常快速的）和不超过三次[树旋转]（对于插入操作是两次）。
虽然插入和删除很复杂，但操作时间仍可以保持为O(logn)次。
插入操作
由于性质的约束：插入点不能为黑节点，应插入红节点。因为你插入黑节点将破坏性质5，所以每次插入的点都是红结点，但是若他的父节点也为红，就会破坏了性质4。所以要做一些“旋转”和一些节点的变色。另为叙述方便我们给要插入的节点标为N（红色），父节点为P，祖父节点为G，叔节点为U。下边将一一列出所有插入时遇到的情况：
情形1:
该树为空树，将N改为黑色，插入根节点的位置。
情形2:
插入节点N的父节点P为黑色,直接插入。
情形3:
N为红，P为红，（祖节点一定存在，且为黑，下边同理）U也为红，这里不论P是G的左孩子，还是右孩子；不论N是P的左孩子，还是右孩子。
Paste_Image.png
解析:N、P都为红，违反性质4；若把P改为黑，符合性质4，显然左边少了一个黑节点，违反性质5；所解析：N、P都为红，违反性质4；若把P改为黑，符合性质4，显然左边少了一个黑节点，违反性质5；所以我们把G，U都改为相反色，这样一来通过G的路径的黑节点数目没变，即符合4、5，但是G变红了，若G的父节点又是红的不就有违反了4，是这样，所以经过上边操作后未结束，需把G作为起始点，即把G看做一个插入的红节点继续向上检索----属于哪种情况，按那种情况操作要么中间就结束，要么知道根结点（此时根结点变红，一根结点向上检索，那木有了，那就把他变为黑色吧）。
情形4:
N为红，P为红，U为黑，P为G的左孩子，N为P的左孩子（或者P为G的右孩子，N为P的左孩子；反正就是同向的）。
操作：如图P、G变色，P、G变换即左左单旋（或者右右单旋），结束。
解析：要知道经过P、G变换（旋转），变换后P的位置就是当年G的位置，所以红P变为黑，而黑G变为红都是为了不违反性质5，而维持到达叶节点所包含的黑节点的数目不变！还可以理解为：也就是相当于（只是相当于，并不是实事，只是为了更好理解；）把红N头上的红节点移到对面黑U的头上；这样即符合了性质4也不违反性质5，这样就结束了。
情形5:
N为红，P为红，U为黑，P为G的左孩子，N为P的右孩子（或者P为G的右孩子，N为P的左孩子；反正两方向相反）。
操作：需要进行两次变换（旋转），图中只显示了一次变换-----首先P、N变换，颜色不变；然后就变成了情形4的情况，按照情况4操作，即结束。
解析：由于P、N都为红，经变换，不违反性质5；然后就变成4的情形，此时G与G现在的左孩子变色，并变换，结束。
删除操作
如果需要删除的节点有两个儿子，那么问题可以被转化成删除另一个只有一个儿子的节点的问题（为了表述方便，这里所指的儿子，为非叶子节点的儿子）。
将要删除的节点P的左孩子的值复制过来，将问题调整为删除N的左孩子L(或右孩子R)。若L(R)有两个儿子，就继续上述操作，直到要删除的节点只有一个儿子。因为只是复制值，所以不影响红黑树的性质。
情形1:
删除节点N是红色的,则父节点P和子节点都是黑色，子节点直接顶替N就可以解决且不违反性质。
情形2:
节点N是黑色，子节点是红色，把子节点变黑，直接顶替N就可以解决且不违反性质。
接下来的情形都是N和子节点都是黑色的情况，为方便构图，N为顶替N的子节点，以下情形都是顶替后的结果。
情形1:
N是新的根。在这种情形下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所以性质都保持着。
情形2:
S是红色。
Paste_Image.png
在这种情形下我们在N的父亲上做左旋转，把红色兄弟转换成N的祖父，我们接着对调N的父亲和祖父的颜色。完成这两个操作后，尽管所有路径上黑色节点的数目没有改变，但现在N有了一个黑色的兄弟和一个红色的父亲（它的新兄弟是黑色因为它是红色S的一个儿子），所以我们可以接下去按情形4、情形5或情形6来处理。
图中N是原来N的子节点。
情形3:
N的父亲、S和S的儿子都是黑色的。
Paste_Image.png
在这种情形下，我们简单的重绘S为红色。结果是通过S的所有路径，它们就是以前不通过N的那些路径，都少了一个黑色节点。因为删除N的初始的父亲使通过N的所有路径少了一个黑色节点，这使事情都平衡了起来。但是，通过P的所有路径现在比不通过P的路径少了一个黑色节点，所以仍然违反性质5。要修正这个问题，我们要从情形1开始，在P上做重新平衡处理。
情形4:
S和S的儿子都是黑色，但是N的父亲是红色。
Paste_Image.png
在这种情形下，我们简单的交换N的兄弟和父亲的颜色。这不影响不通过N的路径的黑色节点的数目，但是它在通过N的路径上对黑色节点数目增加了一，添补了在这些路径上删除的黑色节点。
情形5:
S是黑色，S的左儿子是红色，S的右儿子是黑色，而N是它父亲的左儿子。
Paste_Image.png
在这种情形下我们在S上做右旋转，这样S的左儿子成为S的父亲和N的新兄弟。我们接着交换S和它的新父亲的颜色。所有路径仍有同样数目的黑色节点，但是现在N有了一个黑色兄弟，他的右儿子是红色的，所以我们进入了情形6。N和它的父亲都不受这个变换的影响。
情形6:
S是黑色，S的右儿子是红色，而N是它父亲的左儿子。
Paste_Image.png
在这种情形下我们在N的父亲上做左旋转，这样S成为N的父亲（P）和S的右儿子的父亲。我们接着交换N的父亲和S的颜色，并使S的右儿子为黑色。子树在它的根上的仍是同样的颜色，所以性质3没有被违反。但是，N现在增加了一个黑色祖先：要么N的父亲变成黑色，要么它是黑色而S被增加为一个黑色祖父。所以，通过N的路径都增加了一个黑色节点。
此时，如果一个路径不通过N，则有两种可能性：
它通过N的新兄弟。那么它以前和现在都必定通过S和N的父亲，而它们只是交换了颜色。所以路径保持了同样数目的黑色节点。
它通过N的新叔父，S的右儿子。那么它以前通过S、S的父亲和S的右儿子，但是现在只通过S，它被假定为它以前的父亲的颜色，和S的右儿子，它被从红色改变为黑色。合成效果是这个路径通过了同样数目的黑色节点。
在任何情况下，在这些路径上的黑色节点数目都没有改变。所以我们恢复了性质4。在示意图中的白色节点可以是红色或黑色，但是在变换前后都必须指定相同的颜色。
网友评论