STL提供了许多好用的数据结构与算法，使我们不必为做许许多多的重复劳动。STL里实现了一个树结构-Red-Black Tree，它也是STL里唯一实现的一个树状数据结构，并且它是map， multimap，set，multiset的底层实现，如果学会了Red-Black Tree，那么对我们高效的运用STL是很有帮助的。

1. 什么是红黑树

红黑树是二叉查找树的一种，由于它能够保证树的高度比较底，所以是一种性能较好的查找树。它需要满足以下几条性质： 
1.每个结点或是红的，或是黑的 
2.根结点是黑的 
3.如果一个结点是红的，那么它两个儿子都是黑的 
4.对于每个结点，从该结点到其子孙结点的所有路径上包含数目相同的黑结点

2. 红黑树的操作

红黑树的操作与大多数二叉树操作相同，主要有增加新结点，删除结点，查找结点等等。但是它并不支持直接修改结点，因为结点被修改后会破坏结构，所以在STL中我们也不对一个迭代器的key进行修改。

对于删除与添加操作，因为可能会破坏平衡树的性质，所以我们需要重新对结构进行调整，以使整个树结构保持上述五个性质。由于插入与添加操作涉及比较复杂，我们等到正式讲解STL里实现的时候再详细说明。

因为红黑树可以保证对于N个结点的树，树深度不超过log(2N)，所以效率还是相同高的哦。

3. 红黑树结点的定义

下面代码定义了红黑树的结点： 

由上面的定义可以看出来，每个结点维护了三个指针：父结点_M_parent，左子结点_M_left，右子结点_M_right，同时还有一个颜色标记_M_color，再就是结点的值_M_value_field。同时可以求得当以某个结点为根的最小与最大结点。因为最小结点一定是最左的子孙结点，最大一定是最右的子孙结点。

4. 红黑树的迭代器定义

迭代器是STL里面非常重要的一部分，这里就不细说了，要说的话几天也说不完。RB Tree里提供的迭代哭是双向迭代器bidirectional_iterator_tag，即可以向前走一步，也可以向后走一步，但是不能像操作指针一样，一下子就走好几步。但考虑到它是树结构，所以它所谓的走向前一个或后一个结点也不是那么简单。还好，STL迭代器里定义了两个函数做到这一步。这其实有点像树的中序遍历，把树的结点排起来，前一个结点就是中序的前一个结点（比它小但是最大的结点），后一个结点就是中序的后一个结点（比它大但是最小的结点）。

现在还是看起来有点迷糊，后面分析到红黑树以及header结点的作用时才会有一种恍然大悟的感觉。来看看iterator结口提供了哪些功能。 

可以看到，迭代器的比较是基于指针的比较，并且重载了前置和后置的++,--运算符。它调用的就是_M_decrement()和_M_increment()函数。

5. 红黑树的空间配置器

因为红黑树是动态增长的，所以每次增加或删除结点时都要进行配置，它有一个专用的空间配置器，用来每次申请一个结点的内存或归还一个结点的内存。 

总体来看也没什么特别有用的信息，_M_get_node()就是申请一个结点的空间，_M_put_node()就是归还了。它调用了allocater()和deallocate()，这是STL里面的内存分配的类。讲这个也可以讲一天。有兴趣的可以看Stl_alloc.h和Stl_construct.h这两个头文件。

6. RB-Tree代码分析

前面讲了这么多废话，终于进行正题了。期待己久的header结点终于出现了。 

一直到这里，还没有什么比较难理解的地方，不过我们现在知道了，实现上需要的header结点是这样一个结点，它的父结点是根，它的左右子结点分别指向树中的最左和最右子结点，也就是最小和最大的子结点。

再来看看它的构造函数与析构函数的定义： 

除了拷贝构造函数外，其余构造函数都是直接将header的父指针指向NULL，左右子结点指向自己。拷贝构造函数调用了_M_copy()，它的作用类似于将__x._M_root()为根的树结点复制到_M_header()为根的树结构中。它是通过_M_clone()来完成的。这样就得到了参数一样的树了。析构函数回收所有申请的内存，这里不再讲述。

看上面的代码可以知道，header结点就是end()结点，它的左子结点是begin()，从begin()刚好把树遍历一次。树为空时，begin()与end()都指向header，这样就不用对树为空作特殊判断了。可能比较困惑的地方就是rebegin()了，看看它返回的是_M_header，即我们添加的那个header结点，不是它的右儿子么？即最大的那个结点，同理rend()是指向的第一个结点，我们知道一般写代码是这样： 
for(auto itr = mapTree.rbegin(); itr != mapTree.rend(); ++itr) 
看上去好像是有问题，但是如果熟悉迭代器的就能知道，其实反向迭代器在取值是取它下一个结点的值。即正向迭代中上一个结点的值。所以在rend()上一个结点时，它的值己经被遍历到了。

下面代码开始涉及红黑树的操作了，查找树的三大操作就是：查找，添加，删除。查找操作是最简单的，因为它不涉及树结构的改变。所以我们先来看查找操作的代码：

可以看到find()函数查找的时候，并不是在查找过程中找到一个key相同的就直接返回了。我们知道左子树都是比根结点小的结点，当相同时，我们再往左子树查找，如果找到，再往左子树查找，这样其实find()返回的就是第一个相同的结点，即在迭代过程中第一个相同的结点。

lower_bound()与find()很类似。但它不用最后比较结点，因为如果这个key大于所有的，那么它在比较的时候会一直向右，那么返回的就是end()。如果它向左走过，就表示有一个key大于等于它了，所以肯定返回的不是end()。

upper_bound()也与find()类似，但是查找第一个大于key的结点。如果x小于或等于key时就向右走，否则向左走。可以看到__M_header的力量真是无穷的。

equal_range()是查找key为k的一段区间，是[lower_bound(), upper_bound()),所以不存在时lower_bound()是与upper_bound()相等的，所以为空。

下面来看看插入的代码，前面和平常的二叉查找树相同，但是由于插入新结点后，可能破坏红黑树的性质，所以在后面对其作了修正。

这么多insert,其实主要的还是_M_insert函数的调用，其余函数先和其它的查找树一样，先找到插入点，然后再进行插入，插入后再调整树结构，使其符合红黑树的性质。注意在_M_insert()中新增加的结点颜色还没有被赋值，它是在_Rb_tree_rebalance()函数中被赋值为红结点，新增加的结点初始颜色都是红色。

在讨论_Rb_tree_rebalance()之前，我们要先来看看两个函数，即左旋和右旋。故名思义，就是对于子结点和其父结点围着边向左旋转或向右旋转。当然，它会改变树结点，但经过调整后它并不会改变查找树的性质，即左子树永远比根结点的值小，右子树的结点不会比根结点小。

看下图：X，Y代表结点，A，B，C代表子树，子树可能为空。 
 

可以看到，左旋和右旋其实是一对互逆的过程。从图中也可以看到，不论是左旋还中右旋，它们还是满足左子树结点一定比根小，右子树结点一定不比根小的规律。从红黑树的性质来看，当插入一个结点后，唯一可能不满足的条件就是2和3了。2是因为当空树插入一个结点时，因为初始颜色为红，而3就很显然了。现在我们就需要通过从下往上来调整树结构，使其满足其性质。OK，来看看代码：

OK，看最后一行，性质2满足了。唯一可能不满足的现在就是性质3了。关于调整总共是有六种情况，但这六种情况是对称的，所以总得来说我们分析三种情况就可以了。记住第一个while循环的条件，它结束的条件第一个很好理解，为根的时候父结点是_M_header了，所以就看父结点是红才继续，如果有调整结构的时候我们一直保证红黑树的性，即我们现在不满足的条件就是性质3，那么只有父结点是黑，那么所有条件都是满足的。

这六种情况，我用case_x在代码中表示出来了。先看case_1.case_1调整前后对经如下图： 
xp表示x的parent结点，xpp表示x的parent的parent结点 
 
可以看到，它并不改变树结构，只是改变结点颜色，由于它将那个黑色结点下沉，所以其它性质依然不会被破坏，唯一可能不满足的还是性质3，即红结点的儿子结点也有红色的。当时，经过case_1后，结点向上走了两层。 
其实case_2与case_3是在一起处理的，从代码中也可以看出来，case_2后，会继续执行case_3，这是因为case_2经过处理刚好与case_3完全一样。case_2, case_3如下图所示： 

case_2经过左旋变为case_3时，x还是在同一层上面，而再经过处理后，x的父结点己经是黑色了，也就是while循环条件不满足了，所以从这也可以看出，在RB-Tree调整中，最多经过两次旋转就结束了。case_4,5,6与case_1,2,3就是一个相反的过程了。

最后来看RB Tree最后一个操作——删除，下面这段代码很简单，阅读起来没有问题：

执行删除的代码在这里： 

上面的代码还是不痛不痒，删除区间的时候是一个一个删除的，在删除的时候我们主要调用的就是_Rb_tree_rebalance_for_erase()函数，它有四个参数，要删除的结点，根，最左结点和最右结点。下面是_Rb_tree_rebalance_for_erase函数的定义。

我们想想平常的二叉查找树中是怎么删除一个结点的：
1. 如果结点至多只有一个子结点，那么将其链接到父结点
2.否则找到其后继结点，先删除后继，再将后继结点的值放到原来要删除的结点中。

恩，很长的一段代码：

同样，从上面那个if (__y->_M_color != _S_rb_tree_red) 之前，操作代码与二叉查找树是一样的，就是判断，再链接。但是这样操作可能会破坏红黑树的性质，所以后面就再做了调整，为什么有这个if判断呢？这是因为如果删除的是一个红结点，RB-Tree的性质还是符合的：
1. 从各点到任何一个叶结点经过的黑结点个数相同（删除之前就满足的条件）
2. 不存在两个相邻的红结点（删除之前满足的条件）
3. 根结点是黑的（原来根结点是黑的，删的是红结点，所以不可能被删除的是根）

由于被删除的结点是一个黑结点，所以任何经过x的路径上的黑结点个数将会少1. 所以我们先x视为还有一重黑色。其改变方法总共是八种，也是两两对称的。根据代码中的case_1,2,3,4,我们直接看图是怎么旋转的(橙色结点表示颜色可能是红色也可能是黑色):
case_1: x的兄弟结点是红色的：
 
case_2:x的兄弟结点是黑色的，且两个儿子也是黑色的
 
case_3:x的兄弟结点是红色的,且左儿子是黑色的，右儿子是红色的
 
case_4:x的兄弟结点是红色的,且右儿子是红色的，左儿子颜色随意

x一直是指向具有双重黑色的结点，它也有一个很好的性质，即最多做三次旋转就会结束。对比上面的图我们可快可以知道红黑的在删除时是怎么维持结点的性质的。

因为红黑树是map, multimap, set, multiset的底层实现，所以上述代码里基本上包含了所有上述操作的集合。代码挺长，想要高效的运用STL，虽然不要通读其源码，但是读源码还是能给人很多好的思路，如红黑树实现中header结点，它使人们对许多特殊情况都不再需要判断了。不过在读STL算法与数据结构的源代码之前，你需要了解的就是STL里的迭代器和内存分配器的原理，这样读起来才不会让人感觉到云里雾里，同时你还需要了解其数据结构的实现原理，这样就能事半功倍了

[转]SGI STL 红黑树(Red-Black Tree)源代码分析