STL的红与黑--rb_tree
红黑树，作为一种广泛使用的数据结构，我想大家应该都不会陌生。
谈到红黑树的用途，最广为人知的应该就是红黑树在C++ STL中的应用了，在set, multiset, map, multimap等中，都应用了红黑树。但是，rb_tree本身并不开放给外界使用。
今天，我将介绍，STL源码中，红黑树的具体实现（因为篇幅所限，这里不包括删除操作）。
因为文章的主要目的是分析STL中的源码，所以对于红黑树的具体实现并不展开，这类文章，大家可以到网上查找。这里推荐wiki上的一篇。
首先，我还是简要的介绍一下红黑树的构造、维护思想。
红黑树：
红黑树是二叉查找树（BST），同时也是一种平衡二叉查找树。
虽然它的平衡不如AVL树，但是，它和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。
它可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为根据属性5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。
红黑树操作：恢复红黑树的属性需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n) 次。
插入节点：在讨论红黑树的插入操作之前必须要明白，任何一个即将插入的新结点的初始颜色都为红色。这一点很容易理解，因为插入黑点会增加某条路径上黑结点的数目，从而导致整棵树黑高度的不平衡。但如果新结点父结点为红色时（如图2所示），将会违返红黑树性质：一条路径上不能出现相邻的两个红色结点。这时就需要通过一系列操作来使红黑树保持平衡。
删除节点：
1、删除操作中真正被删除的必定是只有一个红色孩子或没有孩子的结点。
2、如果真正的删除点是一个红色结点，那么它必定是一个叶子结点。
STL源码实现：
一、下面代码定义了红黑树的节点信息：
typedef bool __rb_tree_color_type;// 节点颜色const __rb_tree_color_type __rb_tree_red = false; // 红色为 0const __rb_tree_color_type __rb_tree_black = true; // 黑色为 1struct __rb_tree_node_base{typedef __rb_tree_color_type color_type;typedef __rb_tree_node_base* base_ptr;color_type color; // 色，非即黑。base_ptr parent; // RB 的多操作，必知道父。base_ptr left; // 指向左。base_ptr right; // 指向右。static base_ptr minimum(base_ptr x){while (x->left != 0) x = x->left;// 一直向左走，就找到最小值，return x;// 是二元搜的特性。}static base_ptr maximum(base_ptr x){while (x->right != 0) x = x->right; // 一直向右走，就找到最大值，return x;// 是二元搜的特性。}};template <class Value>struct __rb_tree_node : public __rb_tree_node_base{typedef __rb_tree_node<Value>* link_type;Value value_field;// 值};
由上面的定义可以看出来，每个结点维护了三个指针和两个信息：父结点parent，左子结点left，右子结点right，同时还有一个颜色标记color，再就是结点的值value_field。同时可以求得当以某个结点为根的最小与最大结点。
二、红黑树的迭代器定义：
迭代器是STL里面非常重要的一部分，这里就不细说了。我们直接来看看__rb_tree_iterator提供了哪些功能。因为，__rb_tree_iterator继承自__rb_tree_base_iterator，
所以我们先来看__rb_tree_base_iterator这个结构。
truct __rb_tree_base_iterator{typedef __rb_tree_node_base::base_ptr base_ptr;typedef bidirectional_iterator_tag iterator_category;typedef ptrdiff_t difference_type;base_ptr node;// 它用来与容器之间产生一个连结关系（make a reference）// 以下其可作於 operator++ ，因再他呼叫此函式了。void increment(){if (node->right != 0) {// 如果有右子。(1)node = node->right;// 就向右走while (node->left != 0)// 然後一直往左子走到底node = node->left;// 即是解答}else {// 有右子。(2)base_ptr y = node->parent;// 找出父while (node == y->right) {// 如果行本身是右子，node = y;// 就一直上溯，直到「不右子」止。y = y->parent;}if (node->right != y)// 「若此的右子不等於此的父」。node = y;// (3) 此的父即解答。// 否此的node 解答。(4)}// 注意，以上判「若此的右子不等於此的父」，是了付一// 特殊情：我欲找根的下一，而恰巧根右子。// 然，以上特殊作法必配合 RB-tree 根特殊之header 之的// 特殊。}// 以下其可作於 operator-- ，因再他呼叫此函式了。void decrement(){if (node->color == __rb_tree_red &&// 如果是，且node->parent->parent == node)// 父的父等於自己，node = node->right;// (1) 右子即解答。// 以上情生於nodeheader（亦即 node end() ）。// 注意，header 之右子即 mostright，指向整棵的 max 。else if (node->left != 0) {// 如果有左子。(2)base_ptr y = node->left;// 令y指向左子while (y->right != 0)// y有右子y = y->right;// 一直往右子走到底node = y;// 最後即答案}else {// 既非根，亦左子。base_ptr y = node->parent;// (3) 找出父while (node == y->left) {// 行身左子node = y;// 一直交替往上走，直到行y = y->parent;// 不左子}node = y;// 此之父即答案}}};
可以看到__rb_tree_base_iterator里面只有两个函数：increment()和decrement()。
这两个函数也是很好理解：
increment()：找到比当前节点大的最小的那个节点。用于__rb_tree_iterator中重载++操作符的调用。
decrement()：找到比当前节点小的最大的那个节点。用于__rb_tree_iterator中重载--操作符的调用。
再来看看__rb_tree_iterator提供了哪些功能：
template <class Value, class Ref, class Ptr>struct __rb_tree_iterator : public __rb_tree_base_iterator{typedef Value value_type;typedef Ref reference;typedef Ptr pointer;typedef __rb_tree_iterator<Value, Value&, Value*> iterator;typedef __rb_tree_iterator<Value, const Value&, const Value*> const_iterator;typedef __rb_tree_iterator<Value, Ref, Ptr> self;typedef __rb_tree_node<Value>* link_type;__rb_tree_iterator() {}__rb_tree_iterator(link_type x) { node = x; }__rb_tree_iterator(const iterator& it) { node = it.node; }reference operator*() const { return link_type(node)->value_field; }#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator->() const { return &(operator*()); }#endif /* __SGI_STL_NO_ARROW_OPERATOR */self& operator++() { increment(); return *this; }//++操作符self operator++(int) {self tmp = *this;increment();return tmp;} self& operator--() { decrement(); return *this; }//--操作符self operator--(int) {self tmp = *this;decrement();return tmp;}};inline bool operator==(const __rb_tree_base_iterator& x, const __rb_tree_base_iterator& y) {return x.node == y.node;// 迭代器相等，意指其所指的相等。}inline bool operator!=(const __rb_tree_base_iterator& x, const __rb_tree_base_iterator& y) {return x.node != y.node;// 迭代器不等，意指其所指的不等。}
上述代码等价于下面代码，结构功能一目了然:
struct __rb_tree_iterator{typedef __rb_tree_node<T>* link_type;operator*();operator->();operator++();operator++(int);operator--();operator--(int);}
三、RB_tree的数据结构：
下面是rb_tree的定义，你可以看到里面有专属的空间配置器，因为红黑树是动态增长的，所以每次增加或删除结点时都要进行配置，它有一个专用的空间配置器，用来每次申请一个结点的内存或归还一个结点的内存。还有各种类别定义，用来维护整棵RB_tree的三笔数据（其中有个仿函数，functor，用来变现节点的大小比较方式），以及一些member functions的定义或声明。
1、专属的空间配置器rb_tree_node_allocator，每次配置一个节点，它使用的是simple_alloc<>。
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>class rb_tree {protected: typedef void* void_pointer; typedef __rb_tree_node_base* base_ptr; typedef __rb_tree_node<Value> rb_tree_node; typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator; typedef __rb_tree_color_type color_type;...}；
2、一些与节点相关的函数：如get_node(),put_node(),create_node(),clone_node(),destroy_node()。
public: // 注意，有定 iterator（喔，不，定在後面） typedef Key key_type; typedef Value value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; typedef rb_tree_node* link_type; typedef size_t size_type; typedef ptrdiff_t difference_type;protected: link_type get_node() { return rb_tree_node_allocator::allocate(); } void put_node(link_type p) { rb_tree_node_allocator::deallocate(p); } link_type create_node(const value_type& x) { link_type tmp = get_node();// 配置空 __STL_TRY { construct(&tmp->value_field, x);// 建容 } __STL_UNWIND(put_node(tmp)); return tmp; } link_type clone_node(link_type x) {// 一（的值和色） link_type tmp = create_node(x->value_field); tmp->color = x->color; tmp->left = 0; tmp->right = 0; return tmp; } void destroy_node(link_type p) { destroy(&p->value_field);// 解容 put_node(p);// }
3、rb_tree的构造函数
1、以现有的RB_tree复制一个新的RB_tree
2、创造一个空的RB_tree
void init() { header = get_node();// 生一空，令 header 指向它 color(header) = __rb_tree_red; // 令 header 色，用分 header // 和 root（在 iterator.operator++ 中） root() = 0; leftmost() = header;// 令 header 的左子自己。 rightmost() = header;// 令 header 的右子自己。 }public: // allocation/deallocation rb_tree(const Compare& comp = Compare()) : node_count(0), key_compare(comp) { init(); } // 以另一 rb_tree 物件 x 初值 rb_tree(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x) : node_count(0), key_compare(x.key_compare) { header = get_node();// 生一空，令 header 指向它 color(header) = __rb_tree_red;// 令 header 色 if (x.root() == 0) {// 如果 x 是空白 root() = 0; leftmost() = header; // 令 header 的左子自己。 rightmost() = header; // 令 header 的右子自己。 } else {// x 不是一空白 __STL_TRY { root() = __copy(x.root(), header);// ??? } __STL_UNWIND(put_node(header)); leftmost() = minimum(root());// 令 header 的左子最小 rightmost() = maximum(root());// 令 header 的右子最大 } node_count = x.node_count; } ~rb_tree() { clear(); put_node(header); } rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& operator=(const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x);
4、rb_tree的元素操作
1）插入元素的插入操作 insert_equal()，插入的值可以是重复的。
// 安插新值；值允重。// 注意，回值是一 RB-tree 迭代器，指向新增template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iteratorrb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_equal(const Value& v){ link_type y = header; link_type x = root();// 根始 while (x != 0) {// 根始，往下找的安插 y = x; x = key_compare(KeyOfValue()(v), key(x)) ? left(x) : right(x); // 以上，遇「大」往左，遇「小於或等於」往右 } return __insert(x, y, v);}
2）插入元素的插入操作 insert_unique()，插入的值不能重复的。
// 安插新值；值不允重，若重安插效。// 注意，回值是pair，第一元素是 RB-tree 迭代器，指向新增，// 第二元素表示安插成功否。template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>pair<typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator, bool>rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(const Value& v){ link_type y = header; link_type x = root();// 根始 bool comp = true; while (x != 0) { // 根始，往下找的安插 y = x; comp = key_compare(KeyOfValue()(v), key(x)); // v 值小於目前之值？ x = comp ? left(x) : right(x);// 遇「大」往左，遇「小於或等於」往右 } // while 圈之後，y 所指即安插之父（此的它必） iterator j = iterator(y); // 令迭代器j指向安插之父 y if (comp)// 如果 while 圈 comp 真（表示遇「大」，安插於左） if (j == begin()) // 如果安插之父最左 return pair<iterator,bool>(__insert(x, y, v), true); // 以上，x 安插，y 安插之父，v 新值。 else// 否（安插之父不最左） --j;// 整 j，回... if (key_compare(key(j.node), KeyOfValue()(v))) // 小於新值（表示遇「小」，安插於右） return pair<iterator,bool>(__insert(x, y, v), true); // 行至此，表示新值一定中值重，那就不插入新值。 return pair<iterator,bool>(j, false);}
3）真正的插入操作执行程序 __insert()
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iteratorrb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__insert(base_ptr x_, base_ptr y_, const Value& v) {// x_ 新值安插，y_ 安插之父，v 新值。 link_type x = (link_type) x_; link_type y = (link_type) y_; link_type z; // key_compare 是值大小比。是 function object。 if (y == header || x != 0 || key_compare(KeyOfValue()(v), key(y))) { z = create_node(v); // 生一新 left(y) = z; // 使得 y 即 header，leftmost() = z if (y == header) { root() = z; rightmost() = z; } else if (y == leftmost())// 如果y最左 leftmost() = z; // leftmost()，使它永指向最左 } else { z = create_node(v);// 生一新 right(y) = z;// 令新成安插之父 y 的右子 if (y == rightmost()) rightmost() = z; // rightmost()，使它永指向最右 } parent(z) = y;// 定新的父 left(z) = 0;// 定新的左子 right(z) = 0; // 定新的右子 // 新的色在 __rb_tree_rebalance() 定（整） __rb_tree_rebalance(z, header->parent);// 一新增，二 root ++node_count;// 累加 return iterator(z);// 回一迭代器，指向新增}
4）调整RB_tree （旋转及改变颜色）
任何插入操作，于节点插入完毕后，都要做一次调整操作，将树的状态调整到符合RB_tree的要求。
__rb_tree_rebalance()是具备如此能力的一个全局函数：
inline void __rb_tree_rebalance(__rb_tree_node_base* x, __rb_tree_node_base*& root){ x->color = __rb_tree_red;// 新必 while (x != root && x->parent->color == __rb_tree_red) { // 父 if (x->parent == x->parent->parent->left) { // 父祖父之左子 __rb_tree_node_base* y = x->parent->parent->right;// 令y 伯父 if (y && y->color == __rb_tree_red) { // 伯父存在，且 x->parent->color = __rb_tree_black; // 更改父黑 y->color = __rb_tree_black;// 更改伯父黑 x->parent->parent->color = __rb_tree_red; // 更改祖父 x = x->parent->parent; } else {// 伯父，或伯父黑 if (x == x->parent->right) { // 如果新父之右子 x = x->parent; __rb_tree_rotate_left(x, root); // 第一左旋 } x->parent->color = __rb_tree_black;// 改色 x->parent->parent->color = __rb_tree_red; __rb_tree_rotate_right(x->parent->parent, root); // 第一右旋 } } else {// 父祖父之右子 __rb_tree_node_base* y = x->parent->parent->left; // 令y 伯父 if (y && y->color == __rb_tree_red) {// 有伯父，且 x->parent->color = __rb_tree_black;// 更改父黑 y->color = __rb_tree_black; // 更改伯父黑 x->parent->parent->color = __rb_tree_red; // 更改祖父 x = x->parent->parent;// 往上查... } else {// 伯父，或伯父黑 if (x == x->parent->left) {// 如果新父之左子 x = x->parent; __rb_tree_rotate_right(x, root); // 第一右旋 } x->parent->color = __rb_tree_black;// 改色 x->parent->parent->color = __rb_tree_red; __rb_tree_rotate_left(x->parent->parent, root); // 第一左旋 } } }// while 束 root->color = __rb_tree_black;// 根永黑}
上述的调整函数需要左旋和右旋：
__rb_tree_rotate_left（）：左旋
// 以下都是全域函式：__rb_tree_rotate_left(), __rb_tree_rotate_right(),// __rb_tree_rebalance(), __rb_tree_rebalance_for_erase()// 新必。如果安插之父亦，就反黑，此必// 做形旋（及色改，在程式它）。inline void __rb_tree_rotate_left(__rb_tree_node_base* x, __rb_tree_node_base*& root){ // x 旋 __rb_tree_node_base* y = x->right;// 令y 旋的右子 x->right = y->left; if (y->left !=0) y->left->parent = x;// 忘了回定父 y->parent = x->parent; // 令 y 完全替 x 的地位（必 x 其父的完全接收） if (x == root)// x 根 root = y; else if (x == x->parent->left)// x 其父的左子 x->parent->left = y; else// x 其父的右子 x->parent->right = y; y->left = x; x->parent = y;}
__rb_tree_rotate_right（）：右旋
// 新必。如果安插之父亦，就反黑，此必// 做形旋（及色改，在程式它）。inline void __rb_tree_rotate_right(__rb_tree_node_base* x, __rb_tree_node_base*& root){ // x 旋 __rb_tree_node_base* y = x->left;// y 旋的左子 x->left = y->right; if (y->right != 0) y->right->parent = x; // 忘了回定父 y->parent = x->parent; // 令 y 完全替 x 的地位（必 x 其父的完全接收） if (x == root)// x 根 root = y; else if (x == x->parent->right)// x 其父的右子 x->parent->right = y; else// x 其父的左子 x->parent->left = y; y->right = x; x->parent = y;}
---------------------by----zerocool-----------2012年10月14日3:43:06