1. 介绍
红黑树是一种自均衡二叉查找树。它的统计分析特性好些于平衡二叉树（AVL树），因而，红黑树在许多 地区都是有运用。在C STL中，许多 一部分(现阶段包含set, multiset, map, multimap)运用了红黑树的组合(SGI STL中的红黑树有一些转变，这种改动出示了更强的特性，及其对set实际操作的适用)。它是繁杂的，但它的实际操作拥有 优良的最坏状况运作時间，而且结合实际是高效率的: 它能够在O(log n)時间内做搜索，插进和删掉等实际操作。
文中详细介绍了红黑树的基础特性和操作过程。
2. 红黑树的特性
红黑树，说白了，根据黑红二种色调域确保树的高宽比类似均衡。它的每一个连接点是一个五元组：color（色调），key（数据信息），left（左小孩），right（右小孩）和p（父节点）。
红黑树的界定也是它的特性，有下列五条：
- 特性1. 连接点是鲜红色或灰黑色
- 特性2. 根是灰黑色
- 特性3. 全部叶片全是灰黑色（叶片是NIL连接点）
- 特性4. 假如一个连接点是红的，则它的兄弟俩全是黑的
- 特性5. 从任一连接点到其叶片的全部简易途径都包括同样数量的灰黑色连接点。
这五个特性强制性了红黑树的重要特性: 从根到叶片的最多的很有可能途径不超过最少的很有可能途径的二倍长。为什么呢？特性4预示着一切一个简易途径上不可以有两个毗邻的鲜红色连接点，那样，最少的很有可能途径都是灰黑色连接点，最多的很有可能途径有更替的鲜红色和灰黑色连接点。另外依据特性5了解：全部最多的途径都是有同样数量的灰黑色连接点，这就说明了沒有途径能超过一切别的途径的二倍长。
的鲜红色连接点，那样，最少的很有可能途径都是灰黑色连接点，最多的很有可能途径有更替的鲜红色和灰黑色连接点。另外依据特性5了解：全部最多的途径都是有同样数量的灰黑色连接点，这就说明了沒有途径能超过一切别的途径的二倍长。
3. 红黑树的操作过程
由于红黑树也是二叉查找树，因而红黑树上的搜索实际操作与一般二叉查找树上的搜索实际操作同样。殊不知，红黑树上的插进实际操作和删掉实际操作会造成不会再合乎红黑树的特性。修复红黑树的特性必须小量(O(log n))的色调变动(具体是十分迅速的)和不超过三次树转动(针对插进实际操作是2次)。尽管插进和删掉很繁杂，但实际操作時间仍能够维持为 O(log n) 次。
3.1 插进实际操作
插进实际操作能够归纳为下列好多个流程：
(1) 搜索要插进的部位，算法复杂度为：O(N)
(2) 将新连接点的color赋为鲜红色
(3) 由上而下再次调节该树为红黑树
在其中，第(1)步的搜索方式跟一般二叉查找树一样，第(2)步往往将新插进的连接点的色调赋为鲜红色，是由于：假如设为灰黑色，便会造成根到叶片的途径上有一条路上，多一个附加的黑连接点，这个是难以调节的。可是设为鲜红色连接点后，很有可能会造成出現2个持续鲜红色连接点的矛盾，那麼能够根据色调替换（color flips）和树转动来调节，那样简易多了。下边探讨流程(3)的一些关键点：
设要插进的连接点为N，父亲连接点为P，其爸爸G的弟兄连接点为U（即P和U是同一个连接点的两个子连接点）。
[1] 假如P是灰黑色的，则整棵树无须调节就是红黑树。 [2] 假如P是鲜红色的（得知，父亲连接点G一定是灰黑色的），则插进z后，违反了特性4，必须开展调节。调节时候下列3种状况：（a）N的大伯U是鲜红色的
如圖所显示，大家将P和U重绘为灰黑色并举绘连接点G为鲜红色(用于维持特性5)。如今新连接点N拥有一个灰黑色的父节点P，由于根据父节点P或堂叔连接点U的一切途径都必然根据爷爷连接点G，在这种途径上的黑连接点数量沒有更改。可是，鲜红色的爷爷连接点G的父节点也是有可能是鲜红色的，这就违背了特性4。为了更好地处理这个问题，我们在爷爷连接点G上递归调节色调。
（b）N的大伯U是灰黑色的，且N是右小孩
如圖所显示，大家对P开展一次左转动替换新连接点和父亲连接点的人物角色; 然后，按情况(c)解决之前的父节点P以处理依然无效的特性4。
（c）N的大伯U是灰黑色的，且N是左小孩
如圖所显示，对爷爷连接点G 的一次右转动; 在转动造成的树中，之前的父节点P现在是新连接点N和之前的爷爷连接点G 的父节点， 随后互换之前的父节点P和爷爷连接点G的色调，結果的树考虑特性4，另外特性5[4]也依然维持考虑。
3.2 删掉实际操作
删掉实际操作能够归纳为下列好多个流程：
(1) 搜索要删掉部位，算法复杂度为：O(N)
(2) 用删掉连接点后续或是连接点更换该连接点（只开展数据信息更换就可以，无须调节表针，后续连接点是中序遍历中紧挨着该连接点的连接点，即：右小孩的最左小孩连接点）
(3) 假如删掉连接点的更换连接点为灰黑色，则需再次调节该树为红黑树
在其中，第(1)步的搜索方式跟一般二叉查找树一样，第(2)步往往用后续连接点更换删掉连接点，是由于那样能够确保该后续连接点以上仍是一个红黑树，而后续连接点可能是一个叶连接点或是仅有右子树的连接点，那样只要用有连接点更换后续连接点就可以做到删掉的目地。假如必须删掉的连接点有兄弟俩，那麼难题能够被转换成删掉另一个只有一个孩子的连接点的难题。（没看懂？？？可参照：http://zh.wikipedia.org/wiki/红黑树 ）在第(3)步中，假如，假如删掉连接点为鲜红色连接点，则他的爸爸和小孩全为黑连接点，那样立即删掉该连接点就可以，无须开展一切调节。假如删掉连接点是黑连接点，分四种状况：
设要删掉的连接点为N，父亲连接点为P，其弟兄连接点为S。
因为N是灰黑色的，则P可能是灰黑色的，也可能是鲜红色的，S也可能是灰黑色的或是鲜红色的
（1）S是鲜红色的
这时P肯定是鲜红色的。大家对N的父节点开展左转动，随后把鲜红色弟兄转化成N的爷爷。大家然后互换 N 的爸爸和爷爷的色调。虽然全部的途径依然有同样数量的灰黑色连接点，如今 N 拥有一个灰黑色的弟兄和一个鲜红色的爸爸，因此我们可以接下来按 (2)、(3)或(4)状况来解决。
（2）S和S的小孩都是灰黑色的
在这类状况下，P可能是灰黑色的或是鲜红色的，大家简易的重绘S 为鲜红色。結果是根据S的全部途径，他们便是之前不通过 N 的这些途径，都少了一个灰黑色连接点。由于删掉 N 的原始的爸爸使根据 N 的全部途径少了一个灰黑色连接点，这使事儿都均衡了起來。可是，根据 P 的全部途径如今比不通过 P 的途径少了一个灰黑色连接点。下面，要调节以P做为N递归调节树。
（3）S是灰黑色的，S的左小孩是鲜红色，右小孩是灰黑色
这类状况下我们在 S 上做右转动，那样 S 的左孩子变成 S 的爸爸和 N 的新弟兄。大家然后互换 S 和它的新爸爸的色调。全部途径仍有一样数量的灰黑色连接点，可是如今 N 拥有一个右孩子是鲜红色的灰黑色弟兄，因此大家进入了状况（4）。N 和它的爸爸也不受这一转换的危害。
（4）S是灰黑色的，S的右小孩是鲜红色
在这类状况下我们在 N 的爸爸上做左转动，那样 S 变成 N 的爸爸和 S 的右孩子的爸爸。大家然后互换 N 的爸爸和 S 的色调，并使 S 的右孩子为灰黑色。子树在它的根上的仍是一样的色调，因此特性 3 沒有被违背。可是，N 如今提升了一个灰黑色先祖: 要不 N 的爸爸变为灰黑色，要不它是灰黑色而 S 被提升为一个灰黑色爷爷。因此，根据 N 的途径都提升了一个灰黑色连接点。
4. 参考文献
(1) 《算法导论》，第二版
(2) http://zh.wikipedia.org/wiki/红黑树
