红黑树
二叉查找树一种提高查询效率(O(logN))的二叉树，但是二叉查找树的查询效率在新节点不断的插入后查询效率有可能会退化为O(N)，相关原因请查看这篇文章二叉树遍历，为了消除这种弊端，二叉树在插入或删除节点后需要进行自平衡，因此就出现了很多自平衡的二叉查找树，这些自平衡二叉查找树的查询效率都会稳定在O(logN)，红黑树就是一种自平衡的二叉查找树。下面我们会红黑树的特征、插入以及删除来分析红黑树是如何进行自平衡的。
特征
想要了解红黑树如何自平衡，就必须了解红黑树的特征，因为自平衡操作都是围绕这些特征来的，一旦一个红黑树因为插入和删除节点打破了自身的特征，那么他就需要进行自平衡(变色、旋转)来使得二叉树重新满足红黑树的特征。
红黑树的主要特征如下：
- 每个节点只有红色和黑色两种
- 根节点必须是黑色
- 所有的叶子节点都是黑色(NIL节点)
- 每个红色节点必须有两个黑色子节点(从每个叶子节点到根节点的路径上不能有连续的红色节点)
- 从任一节点到其每个叶子节点的所有路径都必须包含相同数目的黑色节点
第4条规则保证了最短的路径上全是黑色节点，最长的路径上是红黑交替的路径(最短路径的两倍长)。同时第5条规则则保证了所有最长路径上具有相同的黑色节点，所以说任何路径的长度可以超过最短路径的两倍。
通过上述特征，决定了红黑树的一个重要特性：从根到叶子的最长的可能路径不多于最短路径的两倍长。
下图是一张红黑树示意图：
自平衡
红黑树进行自平衡的操作主要有两种：
- 变色
- 旋转
下面我们通过插入操作来分析一下何时进行变色，又是何时进行旋转。
插入操作
我们首先以二叉查找树的方法增加节点并标记它为红色。（如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过变色和树旋转来调整。下面要进行什么操作取决于其他临近节点的颜色。当我们插入节点时需要，红黑树的特征可能会遇到以下情况：
- 性质1和性质3总是保持着。
- 性质4只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁。
- 性质5只在增加黑色节点、重绘红色节点为黑色，或做旋转时受到威胁。
插入节点以后红黑树主要可能遇到以下情形，在下面的情形中我们就需要进行变色或者旋转，下面我们进行一一分析。
在分析之前我们先定义一些节点，我们将要插入的节点标为N，N的父节点标为P，N的祖父节点标为G，N的叔父节点标为U。下面会写一些伪代码。
情形1(case1)
新节点N位于树的根上，没有父节点。在这种情形下，我们把该节点变成黑色以满足特征2。因为它在每个路径上对黑色节点数目增加1，特征5符合。
if (N.parent == null) {
N.color = BLACK;
} else {
case2(N);
}情形2
新节点N的父节点P是黑色，所以特征4没有失效（新节点是红色的）。在这种情形下，树仍是有效的。特征5也未受到威胁，尽管新节点N有两个黑色叶子子节点；但由于新节点N是红色，通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点，所以依然满足这个特征。
if (N.parent.color == BLACK) {
return;
} else {
case3(N);
}情形3
如果父节点P和叔父节点U二者都是红色，（此时新插入节点N做为P的左子节点或右子节点都属于情形3，下面有个示意图仅显示N做为P左子节点的情形）则我们可以将P和U重绘为黑色并重绘祖父节点G为红色（用来保持特征5）。现在我们的新节点N有了一个黑色的父节点P。因为通过父节点P或叔父节点U的任何路径都必定通过祖父节点G，在这些路径上的黑节点数目没有改变。但是，红色的祖父节点G可能是根节点，这就违反了特征2，也有可能祖父节点G的父节点是红色的，这就违反了特征4。为了解决这个问题，我们在祖父节点G上递归地进行情形1的整个过程。（把G当成是新加入的节点进行各种情形的检查）
if (N.uncle != null && N.uncle.corlor == RED) {
N.parent.color = BLACK;
N.uncle.color = BLACK;
N.grandfather.color = RED;
case(N.grandfather);
} else {
case(4);
}情形4
父节点P是红色而叔父节点U是黑色或缺少，并且新节点N是其父节点P的右子节点而父节点P又是其父节点的左子节点。在这种情形下，我们进行一次左旋转调换新节点和其父节点的角色;接着，我们按情形5处理以前的父节点P以解决仍然失效的特征4。这个改变会导致某些路径通过它们以前不通过的新节点N（比如图中1号叶子节点）或不通过节点P（比如图中3号叶子节点），但由于这两个节点都是红色的，所以性质5仍有效。
if (N == N.parent.right && N.parent == N.grandfather.left) {
rotateLeft(N);
N = N.left;
} else if (N == N.parent.left && N.parent == N.grandfather.right) {
rotateRight(N);
N = N.right;
}
case5(N);情形5
父节点P是红色而叔父节点U是黑色或缺少，新节点N是其父节点的左子节点，而父节点P又是其父节点G的左子节点。在这种情形下，我们进行针对祖父节点G的一次右旋转；在旋转产生的树中，以前的父节点P现在是新节点N和以前的祖父节点G的父节点。我们知道以前的祖父节点G是黑色，否则父节点P就不可能是红色（如果P和G都是红色就违反了特征4，所以G必须是黑色）。我们切换以前的父节点P和祖父节点G的颜色，结果的树满足性质4。特征5也仍然保持满足，因为通过这三个节点中任何一个的所有路径以前都通过祖父节点G，现在它们都通过以前的父节点P。在各自的情形下，这都是三个节点中唯一的黑色节点。
N.parent.color = BLACK;
N.grandfather.color = RED;
if (N == N.parent.left && N.parent == N.grandfather.left) {
rotateRight(N);
} else {
rotateLeft(N);
}删除操作
红黑树是一种自平衡的二叉查找树，因此删除节点的时候符合删除二叉查找树节点的规律，假设删除的节点为N，那么我们需要找到N节点左子树下面最大的节点或者找到右子树中最小的节点M，然后用M的值替换N的值(注意这里只拷贝值，不需要拷贝颜色)，然后M节点删除。要删除的M节点必定是带有最多一个儿子节点的节点。
假设我们删除的节点是一个红色节点，说明这个节点的父亲和儿子节点都是黑色节点，我们可以简单的使用他的儿子节点直接代替他。如果我们删除的节点是一个黑色节点并且他的儿子是个红色节点的时候，我们可以使用他的儿子节点顶替它，并且将它重绘成黑色即可。需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候（这种情况下该节点的两个儿子都是叶子节点，否则若其中一个儿子是黑色非叶子节点，另一个儿子是叶子节点，那么从该节点通过非叶子节点儿子的路径上的黑色节点数最小为2，而从该节点到另一个叶子节点儿子的路径上的黑色节点数为1，违反了特征5）。我们首先把要删除的节点替换为它的儿子。出于方便，称呼这个儿子为N（在新的位置上），称呼它的兄弟（它父亲的另一个儿子）为S。在下面的示意图中，我们还是使用P称呼N的父亲，SL称呼S的左儿子，SR称呼S的右儿子。
replace_node(N, N.child);
if(N.color == BLACK){
if(N.child.color == RED) {
N.child.color = BLACK;
} else {
case1(child);
}
}
delete(N);
}情形1
N是新的根,。在这种情形下，可以直接结束。我们从所有路径去除了一个黑色节点，而新根是黑色的。
if (N.parent != null) {
case(N);
}情形2
S是红色。在这种情形下我们在N的父亲上做左旋转，把红色兄弟转换成N的祖父，我们接着对调N的父亲和祖父的颜色。完成这两个操作后，尽管所有路径上黑色节点的数目没有改变，但现在N有了一个黑色的兄弟和一个红色的父亲（它的新兄弟是黑色因为它是红色S的一个儿子），所以我们可以接下去按情形4、情形5或情形6来处理。
if (S.color == RED) {
N.parent.color = RED;
S.color = BLACK;
if (N == N.parent.left) {
rotateLeft(N.parent);
} else {
rotateRight(N.parent);
}
case3(N);
}情形3
N的父亲、S和S的儿子都是黑色的。在这种情形下，我们简单的重绘S为红色。结果是通过S的所有路径，它们就是以前不通过N的那些路径，都少了一个黑色节点。因为删除N的初始的父亲使通过N的所有路径少了一个黑色节点，这使事情都平衡了起来。但是，通过P的所有路径现在比不通过P的路径少了一个黑色节点，所以仍然违反特征5。要修正这个问题，我们要从情形1开始，在P上做重新平衡处理。
if (N.parent.color == BLACK && S.color == BLACK
&& S.left.color == BLACK && S.right.corlor == BLACK) {
S.color = RED;
case1(N.parent);
} else {
case4(N);
}情形4
S和S的儿子都是黑色，但是N的父亲是红色。在这种情形下，我们简单的交换N的兄弟和父亲的颜色。这不影响不通过N的路径的黑色节点的数目，但是它在通过N的路径上对黑色节点数目增加了一，添补了在这些路径上删除的黑色节点。
if (N.parent.color == RED && S.color == BLACK
&& S.left.color == BLACK && S.right.color == BLACK) {
N.parent.color == BLACK;
S.color == RED;
} else {
case(5);
}情形5
S是黑色，S的左儿子是红色，S的右儿子是黑色，而N是它父亲的左儿子。在这种情形下我们在S上做右旋转，这样S的左儿子成为S的父亲和N的新兄弟。我们接着交换S和它的新父亲的颜色。所有路径仍有同样数目的黑色节点，但是现在N有了一个黑色兄弟，他的右儿子是红色的，所以我们进入了情形6。N和它的父亲都不受这个变换的影响。
if (S.color == BLACK) {
if (N == N.parent.left && S.right.color == BLACK && S.left.color == RED) {
S.color = RED:
S.left.color = BLACK;
rotateRight(S);
} else if (N == N.parent.right && S.left.color == BLACK && S.right.color == RED) {
S.color = RED;
S.right.color = BLACK;
rotateLeft(S);
}
}
case(6);情形6
S是黑色，S的右儿子是红色，而N是它父亲的左儿子。在这种情形下我们在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。在示意图中的白色节点可以是红色或黑色，但是在变换前后都必须指定相同的颜色。
S.color = N.parent.color;
N.parent.color = BLACK;
if (N == N.parent.left) {
S.right.color = BLACK;
rotateLeft(N.parent);
} else {
S.left.color = BLACK;
rotateRight(N.parent);
}后序
红黑树的自平衡情况还是比较复杂的，需要我们细细揣摩，并且反复的研究，在了解红黑树的基本概念以后，我们后续会分析一下HashMap中红黑树的实现以及着手自己实现一个红黑树。