CONTENTS
备注：
本读书笔记基于侯捷先生的《STL源码剖析》，截图和注释版权均属于原作者所有。
本读书笔记中的源码部分直接拷贝自SGI-STL，部分代码删除了头部的版权注释，但代码版权属于原作者。
小弟初看stl，很多代码都不是太懂，注释可能有很多错误，还请路过的各位大牛多多给予指导。
为了降低学习难度，作者这里换到了SGI-STL-2.91.57的源码来学习，代码下载地址为【 http://jjhou.boolan.com/jjwbooks-tass.htm 】
以下内容转自【 http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91 】，有较多修改。
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，他称之为”对称二叉B树”，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。
用途和好处:
红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如实时应用（real time application）中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树。
红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构之一，它们用来构造关联数组和集合，在突变之后它们能保持为以前的版本。除了O(log n)的时间之外，红黑树的持久版本对每次插入或删除需要O(log n)的空间。
红黑树是 2-3-4树的一种等同。换句话说，对于每个 2-3-4 树，都存在至少一个数据元素是同样次序的红黑树。在 2-3-4 树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得 2-3-4 树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍 2-3-4 树的原因，尽管 2-3-4 树在实践中不经常使用。
性质:
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
注意这里的一些定义和一般的树的定义有点差别，【子节点】是指有实际数据的节点。这里【叶子】是指NIL节点，其没有实际数据，仅仅表示树在此结束，因此，这里所有的节点都有两个孩子，孩子可以是叶子，也可以是子节点。
性质1. 【子节点】是红色或黑色。
性质2. 根是黑色。
性质3. 所有叶子都是黑色（叶子是指NIL节点，注意这里的叶子并不是【子节点】）。
性质4. 每个红色【子节点】的【子节点】必须是黑色的。(从每个叶子到根的所有路径上不能有两个连续的红色子节点。)，但是每个黑色【子节点】的【子节点】可以为黑色也可以为红色。
性质5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色【子节点】。
下面是一个具体的红黑树的图例：
这些约束确保了红黑树的关键特性:
从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
原因如下：
性质4导致了路径不能有两个毗连的红色节点。最短的可能路径都是黑色子节点，最长的可能路径有交替的红色和黑色子节点。因为根据性质5所有最长的路径都有相同数目的黑色子节点，这就表明了没有路径能多于任何其他路径的两倍长。
操作:
因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n) 次。
插入:
我们首先以二叉查找树的方法增加子节点并初始化标记它为红色。（如果初始化为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑子节点，这个是很难调整的。但是设为红色子节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。）
插入节点对红黑树的性质的挑战：
性质1和性质3总是保持着。
性质4只在增加红色子节点、重绘子黑色节点为红色，或做旋转时受到威胁。【性质4：每个红色【子节点】的【子节点】必须是黑色的。】
性质5只在增加黑色子节点、重绘子红色节点为黑色，或做旋转时受到威胁。【性质5：从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色【子节点】。】
下面要进行什么操作取决于其他临近节点的颜色。同人类的家族树中一样，我们将使用术语叔父节点来指一个节点的父节点的兄弟节点，将要插入的节点标为N，N的父节点标为P，N的祖父节点标为G，N的叔父节点标为U，G的父节点标为GG。如下图：
对于每一种情形，我们将使用 C 示例代码来展示。通过下列函数，可以找到一个节点的叔父和祖父节点：
node* grandparent(node *n) {
return n->parent->parent;
}
node* uncle(node *n) {
if (n->parent == grandparent(n)->left)
return grandparent(n)->right;
else
return grandparent(n)->left;
}
情形1: 新子节点N位于树的根上，没有父节点。
在这种情形下，我们把它重绘为黑色以满足性质2【根是黑色。】。因为它在每个路径上对黑节点数目增加一，性质5符合。如果新子节点有父节点，那么执行情形2。
void insert_case1(node *n) {
if (n->parent == NULL)
n->color = BLACK;
else
insert_case2(n);
}
情形2: 新子节点的父节点P是黑色。
所以性质4没有失效（新子节点默认是红色的）。在这种情形下，树仍是有效的。性质5也未受到威胁，尽管新节子点N有两个黑色叶子；但由于新子节点N是红色，通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点，所以依然满足这个性质。
如果新子节点的父节点是红色，那么执行情形3，如下代码所示：
void insert_case2(node *n) {
if (n->parent->color == BLACK)
return; /* 树仍旧有效 */
else
insert_case3(n);
}
如下图：
注意: 在下列情形下我们假定新子节点的父节点为红色，所以它有祖父节点【否则违反性质2】，因为如果父节点是根节点，那父节点就应当是黑色。因为父节点为红色，所以祖父节点必须为黑色【否则违反性质4】。新节点总有一个叔父节点，尽管叔父节点可能是叶子。
情形3: 如果父节点P和叔父节点U二者都是红色。
(此时新插入节点N做为P的左子节点或右子节点都属于情形3)则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色(用来保持性质4)。现在我们的新节点N有了一个黑色的父节点P。因为通过父节点P或叔父节点U的任何路径都必定通过祖父节点G，在这些路径上的黑节点数目没有改变。但是，红色的祖父节点G的父节点也有可能是红色的，这就违反了性质4。为了解决这个问题，我们在祖父节点G上递归地进行情形1的整个过程。（把G当成是新加入的节点进行各种情形的检查，G下面的P，U，N不受任何影响。）
其他的情况，叔父节点U为黑色节点或者为NIL节点（叶子），会调用到情形4，如下代码所示：
void insert_case3(node *n) {
if (uncle(n) != NULL && uncle(n)->color == RED) {
n->parent->color = BLACK;
uncle(n)->color = BLACK;
grandparent(n)->color = RED;
insert_case1(grandparent(n));
}
else
insert_case4(n);
}
如下图：
注意，到了这里，下面的情形已经不是正常的一棵红黑树了，而是一棵正常的红黑树经过情形3下的插入后，G节点作为新的节点插回树中时当前树的情况（不符合情形3时进入）。正常的红黑树不会在第一次插入节点时直接进入下面的情形。
这里我们先笔记情形5，再笔记情形4。
情形5: 父节点P是红色而叔父节点U是黑色，新节点N是其父节点的左子节点，而父节点P又是其父节点G的左子节点（左左情况）。
在这种情形下，我们进行针对祖父节点G的一次右旋转; 在旋转产生的树中，以前的父节点P现在是新节点N和以前的祖父节点G的父节点。我们切换以前的父节点P和祖父节点G的颜色，结果的树满足性质4。性质5也仍然保持满足。
说的比较乱，这里贴一张图解释一下，如图可以看到，当N节点插入到最下面时，根据情形3，会使G节点变红，P,U变黑。由于GG为红色节点，B为黑色节点，当G作为新节点插入树时，当前情形符合情形5（左左情况）：新节点N（节点G）为红色，其父节点P（节点GG）为红色，叔父节点U（节点B）为黑色。根据上面的描述，进行右旋转，针对节点为祖父节点G（节点A），将节点A，节点B旋转下去，将节点GG，节点G旋转上来，然后切换颜色，（未画出NIL节点，未画出GG的右侧子节点，但是该树是正常的红黑树）：
右右情况和左左情况对称，如下图（未画出NIL节点，未画出GG的左侧子节点，但是该树是正常的红黑树）：
代码如下：
void insert_case5(node *n) {
n->parent->color = BLACK;
grandparent(n)->color = RED;
if (n == n->parent->left && n->parent == grandparent(n)->left) {
rotate_right(grandparent(n));
} else {
/* Here, n == n->parent->right && n->parent == grandparent(n)->right */
rotate_left(grandparent(n));
}
}
情形4: 父节点P是红色而叔父节点U是黑色，并且新节点N是其父节点P的右子节点而父节点P又是其父节点G的左子节点（右左情况）。
在这种情形下，我们进行一次左旋转调换新节点和其父节点的角色; 接着，我们按情形5处理以前的父节点P以解决仍然失效的性质4。
说的比较乱，这里贴一张图解释一下，如图可以看到，当N节点插入到最下面（图1）时，根据情形3，会使G节点变红，P,U变黑（图2）。由于GG为红色节点，B为黑色节点，当G作为新节点插入树时，当前情形符合情形4（右左情况）（图2）。根据上面的描述，先进行左旋转，将节点GG旋转下去，将节点G旋转上来，旋转后如图3，这时图3又符合情形5，因此我们按照情形5的操作步骤先右旋，旋转后如图4，再切换颜色，最后如图5，结束。（未画出NIL节点，未画出GG的左侧子节点，但是该树是正常的红黑树）：
左右情况和右左情况对称，如下图（未画出NIL节点，未画出GG的右侧子节点，但是该树是正常的红黑树）：
代码如下：
void insert_case4(node *n) {
if (n == n->parent->right && n->parent == grandparent(n)->left) {
rotate_left(n->parent);
n = n->left;
} else if (n == n->parent->left && n->parent == grandparent(n)->right) {
rotate_right(n->parent);
n = n->right;
}
insert_case5(n);
}
删除
如果要删除的节点【A】有2个子节点（2个子树），那么根据二叉树的规则，被删除的节点会被它的左子树中的最大元素【B】、或者在它的右子树中的最小元素【C】所替换。因此实际上删除的节点是它的左子树中的最大元素【B】、或者在它的右子树中的最小元素【C】。而这个元素【B或C】必定最多只有一个子节点（如果这个元素有两个子节点，那么它必定不是最大元素或最小元素）。因此如果需要删除的节点有两个子节点，那么问题可以被转化成删除另一个最多只有一个子节点的问题。
如果要删除的节点一个子节点都没有，我们就把它的其中一个叶子认为是它的子节点，那么它就有一个黑色的子节点（实际为叶子）。
因此，这里只要讨论要删除的节点只有唯一一个子节点，这个子节点要么是实际值，要么是叶子。
而根据二叉查找树的性质，如果要删除的节点只有唯一一个子节点，那么我们首先删掉该节点，然后让其子节点替换掉它自己。这里，我们把这个子节点的新的位置设为N，它的兄弟为S，P为其父亲。SL SR为S的两个子节点。如下图：
情形A：如果删除一个红色节点。
首先根据性质2，它一定有一个黑色的父节点，这里讨论的节点都是有一个子节点的，根据性质5，这里红色节点的子节点应该为【叶子】。此时直接删掉该节点即可，然后用它的子节点【叶子】来顶替它的位置。
如下图：
情形B：如果删除一个黑色节点，且它的子节点是红色。
此时直接删掉该节点，让其子节点顶替自己即可。如下图：
情形C：如果删除一个黑色节点，而它的子节点为黑色时（含有实际值的黑色子节点或者是叶子），情况就比较复杂了。
该情形下如何保证红黑树依然有效需要看S，SL，SR的颜色。
首先使用下述函数找到兄弟节点:
struct node* sibling(struct node *n)
{
if (n == n->parent->left)
return n->parent->right;
else
return n->parent->left;
}
使用下列代码进行上述情形的概要步骤，这里的函数调用【replace_node(n, child)】替换【child】到【n】在树中的位置。
void delete_one_child(struct node *n)
{
/*
* Precondition: n has at most one non-null child.
*/
struct node *child = is_leaf(n->right) ? n->left : n->right;//首先获取它的唯一的一个子节点。
replace_node(n, child);//用该子节点替换掉自己在树中的位置。
if (n->color == BLACK) {
if (child->color == RED)//情形B，自己为黑，子节点为红，将子节点的颜色变黑即可。
child->color = BLACK;
else
delete_case1(child);//情形C，自己和子节点均为黑，需要看情况处理。
}//情形A，自己为红色，直接删掉，什么也不做。
free(n);
}
情形1: N是新的根。在这种情形下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所以性质都保持着。
void delete_case1(struct node *n)
{
if (n->parent != NULL)
delete_case2(n);
}
情形2: S是红色。根据性质4，P，SL，SR均为黑色。在这种情形下我们在N的父亲上做左旋转，把红色兄弟转换成N的祖父，我们接着对调N的父亲和祖父的颜色。完成这两个操作后，尽管所有路径上黑色节点的数目没有改变，但现在N有了一个黑色的兄弟和一个红色的父亲，我们可以接下去按情形4、情形5或情形6。如下图（左旋右旋都有）：
代码实现：
void delete_case2(struct node *n)
{
struct node *s = sibling(n);
if (s->color == RED) {
n->parent->color = RED;
s->color = BLACK;
if (n == n->parent->left)
rotate_left(n->parent);
else
rotate_right(n->parent);
}
delete_case3(n);
}
情形3: P、S、SL、SR都是黑色的。在这种情形下，我们简单的重绘S为红色。结果是通过S的所有路径，它们就是以前不通过N的那些路径，都少了一个黑色节点。因为删除N的初始的父亲使通过N的所有路径少了一个黑色节点，这使事情都平衡了起来。但是，通过P的所有路径现在比不通过P的路径少了一个黑色节点，所以仍然违反性质4。要修正这个问题，我们要从情形1开始，在P上做重新平衡处理。如下图：
代码实现：
void delete_case3(struct node *n)
{
struct node *s = sibling(n);
if ((n->parent->color == BLACK) &&
(s->color == BLACK) &&
(s->left->color == BLACK) &&
(s->right->color == BLACK)) {
s->color = RED;
delete_case1(n->parent);
} else
delete_case4(n);
}
情形4: S、SL、SR都是黑色，P是红色。在这种情形下，我们简单的交换P和S的颜色。这不影响通过S的路径的黑色节点的数目，但是它在通过N的路径上对黑色节点数目增加了一。如下图：
代码如下：
void delete_case4(struct node *n)
{
struct node *s = sibling(n);
if ((n->parent->color == RED) &&
(s->color == BLACK) &&
(s->left->color == BLACK) &&
(s->right->color == BLACK)) {
s->color = RED;
n->parent->color = BLACK;
} else
delete_case5(n);
}
情形5: S是黑色，SL是红色，SR是黑色，P颜色无所谓，而N是P的左子节点。在这种情形下我们在S上做右旋转，这样SL成为S的父节点和N的新兄弟节点。我们接着S和SL的颜色。所有路径仍有同样数目的黑色节点，但是现在N有了一个右儿子是红色的黑色兄弟，所以我们进入了情形6。N和P都不受这个变换的影响。如下图：
代码如下：
oid delete_case5(struct node *n)
{
struct node *s = sibling(n);
if (s->color == BLACK) { /* this if statement is trivial,
due to Case 2 (even though Case two changed the sibling to a sibling's child,
the sibling's child can't be red, since no red parent can have a red child). */
// the following statements just force the red to be on the left of the left of the parent,
// or right of the right, so case six will rotate correctly.
if ((n == n->parent->left) &&
(s->right->color == BLACK) &&
(s->left->color == RED)) { // this last test is trivial too due to cases 2-4.
s->color = RED;
s->left->color = BLACK;
rotate_right(s);
} else if ((n == n->parent->right) &&
(s->left->color == BLACK) &&
(s->right->color == RED)) {// this last test is trivial too due to cases 2-4.
s->color = RED;
s->right->color = BLACK;
rotate_left(s);
}
}
delete_case6(n);
}
情形6: S是黑色，SR是红色，而N是P的左子节点，P颜色无所谓。在这种情形下我们在P上做左旋转，这样S成为P和SR的父节点。我们接着交换R和S的颜色，并使SR为黑色。此时通过N的路径都增加了一个黑色节点，但是通过SL和SR的路径的黑色节点的数目不变。如下图：
代码如下：
void delete_case6(struct node *n)
{
struct node *s = sibling(n);
s->color = n->parent->color;
n->parent->color = BLACK;
if (n == n->parent->left) {
s->right->color = BLACK;
rotate_left(n->parent);
} else {
s->left->color = BLACK;
rotate_right(n->parent);
}
}
发表评论