红黑树简介
红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。
在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。
红黑树的性质
红黑树的5个性质：
- 每个结点要么是红的要么是黑的。
- 根结点是黑的。
- 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
- 如果一个结点是红的，那么它的两个儿子都是黑的。
- 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。
旋转操作
当在对红黑树进行插入和删除等操作时，对树做了修改可能会破坏红黑树的性质。为了继续保持红黑树的性质，可以通过对结点进行重新着色，以及对树进行相关的旋转操作，即通过修改树中某些结点的颜色及指针结构，来达到对红黑树进行插入或删除结点等操作后继续保持它的性质或平衡的目的。
树的旋转分为左旋和右旋，下面借助图来介绍一下左旋和右旋这两种操作。
如上图所示，当在某个结点pivot上，做左旋操作时，我们假设它的右孩子y不是NIL[T]，pivot可以为任何不是NIL[T]的左子结点。左旋以pivot到Y之间的链为“支轴”进行，它使Y成为该子树的新根，而Y的左孩子b则成为pivot的右孩子。
|
|
左旋之后，privot变成了y的左节点。右旋之后，y变成privot的右节点。【互逆的过程】
2.右旋
右旋中的x，对应于上图右侧的Y。
右旋与左旋差不多，再此不做详细介绍。左右旋也是相互对称的，只要理解其中一种旋转就可以了。
树在经过左旋右旋之后，树的搜索性质保持不变，但树的红黑性质则被破坏了，所以，红黑树插入和删除数据后，需要利用旋转与颜色重涂来重新恢复树的红黑性质。
插入操作
首先以二叉查找树的方法增加结点并标记它为红色。（如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑结点，这个是很难调整的。但是设为红色结点后，可能会导致出现两个连续红色结点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。）下面要进行什么操作取决于其他临近结点的颜色。
设要插入的结点为N，N的父结点标为P，N的叔父结点标为U，N的祖父结点标为G。（即P和U是G的孩子结点）。图中展示的任何颜色要么是由它所处情形这些所作的假定，要么是假定所暗含（imply）的。
情形1. 新结点N位于树的根上，没有父结点。（插入树的第一个结点）
在这种情形下，我们把它重绘为黑色以满足性质2。因为它在每个路径上对黑结点数目增加一，性质5符合。
情形2. 父结点P是黑色，则整棵树不必调整便是红黑树。新结点是红色的，所以性质4没有失效。尽管新结点N有两个黑色叶子子结点；但由于新结点N是红色，通过它的每个子结点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色结点，性质5也未受到威胁。
情形3. 父结点P是红色（祖父结点G一定为黑色），叔父结点U也是红色。则我们可以将P，U重绘为黑色并重绘祖父结点G为红色（用来保持性质5）。但是，红色的祖父结点G可能是根结点，这就违反了性质2，也有可能祖父结点G的父结点是红色的，这就违反了性质4。为了解决这个问题，在祖父结点G上递归调整颜色。
（此时新插入结点N做为P的左子结点或右子结点都属于情形3，这里仅显示N做为P左子的情形）
情形4. 父结点P是红色（祖父结点G一定为黑色），叔父结点U是黑色或缺少，并且新结点N是左孩子。则针对祖父结点G进行一次右旋转；在旋转产生的树中，以前的父结点P现在是新结点N和以前的祖父结点G的父结点。以前的祖父结点G是黑色，切换以前的父结点P和祖父结点G的颜色，结果的树满足性质4，5。
（此时P为祖父结点G的左子结点或右子结点都属于情形4，这里仅显示P为G左子的情形）
情形5. 父结点P是红色（祖父结点G一定为黑色），叔父结点U是黑色或缺少，并且新结点N是右孩子。则针对父结点P进行一次左旋转调换新结点N和P的角色，接着按情形4进行处理。
删除操作
首先以二叉查找树的方法找到要删除的结点，如果需要删除的结点有两个非叶子的孩子结点，那么问题可以转化成删除的结点最多有一个非叶子的孩子结点。（对于二叉查找树，在删除带有两个非叶子儿子的结点的时候，要么找到它的前驱（左子树中的最大元素）、要么找到后继（右子树中的最小元素），并把它的值拷贝到要删除的结点中。接着删除前驱（或后继），注意前驱（后继）的非叶子孩子结点数必定少于2。因为拷贝前驱（后继）值时不违反任何性质，所以上面的问题转化成立）。
如果被删除的结点没有非叶子的孩子，那么直接删除，然后用一个叶子结点代替它的位置，不用作其它树调整。
下面只讨论删除的结点只有一个非叶子结点孩子的情况。如果删除的是一个红色节点，它的父亲和孩子一定是黑色的，所以我们可以简单的用它的黑色儿子替换它，并不会破坏红黑树的性质。另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候。我们重绘它的儿子为黑色，则曾经通过它的所有路径将通过它的黑色儿子，这样可以继续保持性质5。
需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候，这是一种复杂的情况。我们首先把要删除的节点替换为它的儿子。出于方便，称呼这个儿子为N（在新的位置上），称呼它的兄弟（它父亲的另一个儿子）为S。在下面的示意图中，我们使用P称呼N的父亲，SL 称呼S的左儿子，SR 称呼S的右儿子。
情形1. N是新的根。在这种情形下，从所有路径去除了一个黑色节点，而新根是黑色的，所以性质都保持着。
情形2. S是红色（N的父亲P是黑色）。在N的父亲P上做左旋转，把 S 转换成N的祖父，接着对调新的父亲P和新的祖父S的颜色。完成这两个操作后，N有了一个黑色的兄弟和一个红色的父亲（它的新兄弟是黑色因为它是红色S的一个儿子），接下去按情形4、情形5或情形6来处理。
情形3. S和S的儿子都是黑色，N的父亲P是黑色。简单的重绘S为红色。结果是通过S的所有路径，都少了一个黑色节点，因为删除N的初始的父亲使通过N的所有路径少了一个黑色节点。但是，通过P的所有路径现在比不通过P的路径少了一个黑色节点，所以仍然违反性质5。要修正这个问题，我们要从情形1开始，在P上做重新平衡处理。
情形4. S和S的儿子都是黑色，N的父亲P是红色。简单的交换N的兄弟和父亲的颜色。这不影响不通过N的路径的黑色节点的数目，但是它在通过N的路径上对黑色节点数目增加了一，添补了在这些路径上删除的黑色节点。
情形5. S是黑色，S的左儿子是红色，S的右儿子是黑色。在S上做右旋转，这样S的左儿子成为S的父亲和N的新兄弟。接着交换S和它的新父亲的颜色，所有路径仍有同样数目的黑色节点，但是现在N有了一个黑色兄弟，它的右儿子是红色的，所以我们进入了情形4。
情形6. S是黑色，S的右儿子是红色。在N的父亲上做左旋转，这样S成为N的父亲（P）和S的右儿子的父亲。我们接着交换N的父亲和S的颜色，并使S的右儿子为黑色。子树在它的根上的仍是同样的颜色，所以性质3没有被违反。但是，N现在增加了一个黑色祖先：要么N的父亲变成黑色，要么它是黑色而S被增加为一个黑色祖父。
