STL RB Tree(红黑树)分析

当我2014年上半年看内核代码的时候，进程调度用的就是RB  Tree，而现在分析STL源码的时候发现Set和Map也使用了这个数据结构，说明了RBTree的使用时如此的广泛，所以我花了两天时间看了这，分三部分来说明，首先我要说明下红黑树的基本概念，然后说明下STL中的RB Tree的迭代器，最后说下STL中RB Tree容器的实现。

一、红黑树的基本概念

红黑树是平衡二叉搜索树的一种（平衡二叉搜索树中又有AVL Tree），满足二叉搜索树的条件外，还应买足下面的4个条件

1） 每个节点不是红色就是黑色；

2） 根节点是黑色；

3）如果节点是红，那么子节点为黑色；（所以新增节点的父节点为黑色）

4）任一节点到NULL（树尾端）的任何路径，所含的黑节点数必须相同；（所以新增节点为红色）

那么如果按照二叉搜索树的规则插入节点，发现未能符合上面的要求，就得调整颜色并旋转树形。

下面分情况讨论才，插入节点后，发现未能符合要求的几种情况，以及我怎样去调整颜色和旋转树形。

在上图的红黑树种，我们插入四个节点3、8、35、75，插入后首先肯定是红色的，在上图的情况中，这四个插入操作都会违反条件三（红色节点的子节点为黑色），上面的四个点代表了四中情况，而这个图也是很具有代表性的，下面我们就来分情况分析下：

情况一：

插入节点3，如下图所示：

节点3的伯父节点是黑色节点（这里是NULL的话就算作黑色），节点3为外侧插入，这种情况下，需要做一次右旋：

这里的右旋是将爷爷节点下降一层，将父节点上升一层，因为父节点是红色，根据条件三，红色节点的子节点为黑色，所以讲父节点的颜色改为黑色，根据保证条件4，将下降的爷爷节点颜色改为红色，为了满足二叉搜索树的条件，即左子树的值小于/大于右字树的值，所以将父节点的左子树移动给爷爷节点的左子树。

情况二，插入节点8，8的伯父节点（也可以说是叔叔节点）是黑色的（空算作是黑色），插入为内侧插入：

所做的旋转和调色如上图所示，将8上调5下调之后，将8的颜色调为黑色，以满足条件3，将8的左子树移交给5的右子树以满足二叉搜索树的条件，然后再将爷爷节点调整为红色，调整后为上图第二个所示，然后再做一次右旋（是为了减少左右子树的高度差）。

情况三，插入节点75，那么该节点，伯父节点为红色，且插入为外侧插入：

此时爷爷节点85无右旋点，右旋一次以后OK，因为此时曾祖父节点为黑色，所以OK；

情况四，插入节点值为35的节点，和情况三的不同点是调整后，曾祖父节点为红色，那么就得继续往上做同样的旋转和颜色调整，直到不再有父子连续为红色的为止看，如下图所示：

OK，关于如何插入节点已经集中情况已经说完了，那么如何用代码实现则在下面继续说明。

二、红黑树迭代器的实现

这里我先直接将代码贴上来：

[cpp] view plain copy

1. typedef bool __rb_tree_color_type;  
2. typedef __rb_tree_color_type __rb_tree_red   = false;  
3. typedef __rb_tree_color_type __rb_tree_black = true;  
4.   
5. struct __rb_tree_node_base  
6. {  
7.     typedef __rb_tree_color_type    color_type;  
8.     typedef __rb_tree_node_base*    base_ptr;  
9.   
10.     color_type color;  
11.     base_ptr parent;  
12.     base_ptr left;  
13.     base_ptr right;  
14.   
15.     static base_ptr minimum (base_ptr x) {  
16.         while(x->left != 0)  
17.             x = x->left;  
18.         return x;  
19.     }  
20.   
21.     static base_ptr maximum(base_ptr x) {  
22.         while (x->right != 0)  
23.             x = x->right;  
24.         return x;  
25.     }  
26. };  
27.   
28. template <class Value>  
29. struct __rb_tree_node: public __rb_tree_node_base   
30. {  
31.     typedef __rb_tree_node<Value>*    link_type;  
32.     Value value_field;  
33. };  
34.   
35. struct  __rb_tree_base_iterator  
36. {  
37.     typedef __rb_tree_node_base::base_ptr           base_ptr;  
38.     typedef bidirectional_iterator_tag      iterator_category;  
39.     typedef ptrdiff_t               difference_type;  
40.   
41.     base_ptr    node;  
42.   
43.     void increment() {  
44.         if (node->right != 0) {  
45.             node = node->right;  
46.             while (node->left != 0)  
47.                 node = node->left;  
48.         }  
49.         else {  
50.             base_ptr y = node->parent;  
51.              while ( node == y->right) {  
52.                 node = y;  
53.                 y = y->parent;  
54.             }  
55.             if (node->right != y)  
56.                 node = y;  
57.         }  
58.     }  
59.   
60.     void decrement() {  
61.         if( node->color == __rb_tree_red && node->parent->parent == node) {  
62.             node = node->left;  
63.         }  
64.         else if (node->left != 0) {  
65.             node = node->left;  
66.             while ( node->right != 0) {  
67.                 node = node->right;  
68.             }  
69.         }  
70.         else {  
71.             base_ptr y = node->parent;  
72.             while (node == y->left) {  
73.                 node = y;  
74.                 y = y->parent;  
75.             }  
76.             node = y;  
77.         }  
78.     }  
79.   
80. };  
81.   
82. template <class Value , class Ref , class Ptr>  
83. struct  __rb_tree_iterator: public __rb_tree_base_iterator  
84. {  
85.     typedef Value   value_type;  
86.     typedef Ref     referece;  
87.     typedef Ptr     pointer;  
88.   
89.     typedef __rb_tree_iterator<Value , Value & , Value *> iterator;  
90.     typedef __rb_tree_iterator<Value , const Value &  , const Value*> const_iterator;  
91.     typedef __rb_tree_iterator<Value , Ref , Ptr>  self;  
92.     typedef __rb_tree_node<Value>* link_type;  
93.   
94.     __rb_tree_iterator() {}  
95.     __rb_tree_iterator(link_type x) { node_offset = x ;}  
96.     __rb_tree_iterator(const iterator &it) { node = it.node; }  
97.   
98.     referece operator*()  const { return link_type(node)->value_field ;}  
99.     referece operator->() const { return &(operator*());}  
100.   
101.     self& operator++() {  
102.         increment();  
103.         return *this;  
104.     }  
105.   
106.     self operator++(int) {  
107.         self tmp = *this;  
108.         increment();  
109.         return tmp;  
110.     }  
111.   
112.     self& operator--() {  
113.         decrement();  
114.         return *this;  
115.     }  
116.   
117.     self operator--() {  
118.         self tmp = *this;  
119.         decrement();  
120.         return tmp;  
121.     }  
122.   
123. };  

这里我要分析下函数increment()，decrement()和increment是类似的，所以这里我只说下increment

[cpp] view plain copy

1. void increment() {  
2.     if (node->right != 0) {  
3.         node = node->right;  
4.         while (node->left != 0)  
5.             node = node->left;  
6.     }  
7.     else {  
8.         base_ptr y = node->parent;  
9.         while ( node == y->right) {  
10.             node = y;  
11.             y = y->parent;  
12.         }  
13.         if (node->right != y)  
14.             node = y;  
15.     }  
16. }  

这里increment是为了将node指向下一个大于它的node，node的右子树节点的值是都大于node的，而右子树中最小的节点是右子树最左下的节点；

右子树为空的话，那么只能上溯，如果node是node->parent的右孩子的话，那么node是大于node->parent的值的，相反，是node->parent的左孩子的话，是小于parent的，那么下一个大于node的是node所处的左子树的父节点。

（最后一个判断是为了处理RB-Tree根节点和header之间的特殊关系）

三、红黑树的实现

实现代码比较长，代码逻辑并不难，对照上面的例子分析代码，并不难，这里我只说下函数insert_unique，虽然逻辑也不难；

数据成员header的parent是root，left是leftmost，right是rightmost，这是实现上的技巧

[cpp] view plain copy

1. template <class Key , class Value , class KeyOfValue , class Compare , class Alloc = alloc>  
2. class rb_tree  
3. {  
4. protected:  
5.     typedef void*   void_pointer;  
6.     typedef __rb_tree_node_base     *base_ptr;  
7.     typedef __rb_tree_node<Value> rb_tree_node;  
8.     typedef simple_alloc<rb_tree_node , Alloc>    rb_tree_node_allocator;  
9.     typedef __rb_tree_color_type color_type;  
10.   
11. public:  
12.     typedef Key     key_type;  
13.     typedef Value   value_type;  
14.     typedef const value_type*   const_iterator;  
15.     typedef value_type&         reference;  
16.     typedef const value_type&   const_reference;  
17.     typedef rb_tree_node*       link_type;  
18.     typedef size_t              size_type;  
19.     typedef ptrdiff_t           difference_type;  
20.   
21. public:  
22.     link_type get_node() {  
23.         return rb_tree_node::allocate();  
24.     }  
25.   
26.     void put_node(link_type p) {  
27.         rb_tree_node::deallocate();  
28.     }  
29.   
30.     link_type create_node(const value_type& x) {  
31.         link_type tmp = get_node();  
32.         construct(&tmp->value_field , x)  
33.         return tmp;  
34.     }  
35.   
36.     link_type clone_node(link_type x) {  
37.         link_type tmp = create_node(x->value_field);  
38.         tmp->color = x->color;  
39.         tmp->left    = 0;  
40.         tmp->right   = 0;  
41.         return tmp;  
42.     }  
43.   
44.     void destroy_node(link_type p) {  
45.         destroy(&p->value_field);  
46.         put_node(p);  
47.     }  
48.   
49. protected:  
50.     size_type   node_count;  
51.     link_type   header;  
52.     Compare     key_compare;  
53.   
54.     link_type&  root() const { return (link_type&) header->parent; }  
55.     link_type&  leftmost() const { return (link_type&) header->left; }  
56.     link_type&  rightmost() const { return (link_type&) header->right;}  
57.   
58.     static  link_type&  left(link_type x)       {   return (link_type&) x->left;     }  
59.     static  link_type&  right(link_type x)      {   return (link_type&) x->right;    }  
60.     static  link_type&  parent(link_type x)     {   return (link_type&) x->parent;   }  
61.     static  reference   value(link_type x)      {   return  x->value_field;  }  
62.     static  const Key&  key(link_type x)        {   return  KeyOfValue() (value(x));    }  
63.     static  color_type& color(link_type x)      {   return  (color_type&) (x->color);    }  
64.       
65.     static  link_type&  left(base_ptr x)        {   return (link_type&) x->left;     }  
66.     static  link_type&  right(base_ptr x)       {   return (link_type&) x->right;    }  
67.     static  link_type&  parent(base_ptr x)      {   return (link_type&) x->parent;   }  
68.     static  reference   value(base_ptr x)       {   return  x->value_field;          }  
69.     static  const Key&  key(base_ptr x)         {   return  KeyOfValue() (value(x));    }  
70.     static  color_type& color(base_ptr x)       {   return  (color_type&) (x->color);    }  
71.   
72.     static  link_type minimum(link_type x) {  
73.         return (link_type) __rb_tree_node_base::minimum(x);  
74.     }  
75.   
76.     static  link_type maximum(link_type x) {  
77.         return (link_type) __rb_tree_node_base::maximum(x);  
78.     }  
79.   
80. public:  
81.     typedef __rb_tree_iterator<value_type , reference , pointer>  iterator;  
82.   
83. private:  
84.     iterator    __insert(base_ptr x , base_ptr y, const value_type& v);  
85.     link_type   __copy(link_type x  , link_type p);  
86.     void        __erase(link_type   x);  
87.     void init() {  
88.         header = get_node();  
89.         color(header) = __rb_tree_red;  
90.   
91.         root() = 0;  
92.         leftmost()  = header;  
93.         rightmost() = header;  
94.     }  
95.   
96. public:  
97.     rb_tree(const Compare& comp = Compare()): node_count(0) , key_compare(comp) {  
98.         init();  
99.     }  
100.   
101.     ~rb_tree() {  
102.         clear();  
103.         put_node(header);  
104.     }  
105.   
106.     rb_tree<Key , Value , KeyOfValue , Compare , Alloc>&  operator= (const rb_tree<Key , Value , KeyOfValue , Compare , Alloc>& x);  
107.   
108.     Compare     key_comp() const    {   return  key_compare; }  
109.     iterator    begin()             {   return  leftmost();  }  
110.     iterator    end()               {   return  header; }  
111.     bool        empty()             {   return  node_count == 0; }  
112.     size_type   size()  const       {   return  node_count; }  
113.     size_type   max_size()  const   {   return  size_type(-1);  }  
114.   
115. public:  
116.     pair<iterator , bool> inset_unique(const value_type& x);  
117.     iterator insert_equal(const value_type& x);  
118. };  
119.   
120.   
121.   
122. template <class Key , class Value , class KeyOfValue , class Compare , class Alloc = alloc>  
123. typename rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::iterator  
124. rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::insert_equal(const Value& x)  
125. {  
126.     link_type y = header;  
127.     link_type x = root();  
128.     while ( x != 0 ) {  
129.         y = x;  
130.         x = key_compare(KeyOfValue()(v) , key(x)) ? left(x) : right(x);  
131.     }   
132.     return __insert(x , y ,v);  
133. }  
134.   
135. template <class Key , class Value , class KeyOfValue , class Compare , class Alloc = alloc>  
136.   
137.   
138. template <class Key , class Value , class KeyOfValue , class Compare , class Alloc = alloc>  
139. typename rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::iterator  
140. rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::__insert(base_ptr x_ , base_ptr y_ , const Value& v)  
141. {  
142.     link_type   x = (link_type) x_;  
143.     link_type   y = (link_type) y_;  
144.     link_type   z;  
145.   
146.     if ( y == header || x != 0 || key_compare(KeyOfValue()(v) , key(v))) {  
147.         z = create_node(v);  
148.         left(y) = z;  
149.         if ( y == header) {  
150.             root() = z;  
151.             rightmost() = z;  
152.         }  
153.         else if (y == leftmost())  
154.             leftmost = z;  
155.     }  
156.     else {  
157.         z = create_node(v);  
158.         right(y) = z;  
159.         if ( y == rightmost() )  
160.             rightmost() = z;  
161.     }  
162.     parent(z)   = y;  
163.     left(z)     = 0;  
164.     right(z)    = 0;  
165.   
166.     __rb_tree_rebalance(z , header->parent);  
167.     ++node_count;  
168.     return iterator(z);  
169. }  
170.   
171. inline void __rb_tree_rebalance( __rb_tree_node_base* x  , __rb_tree_node_base* &root)  
172. {  
173.     x->color = __rb_tree_red;  
174.     while ( x != root && x->parent->color == __rb_tree_red ) {  
175.         if ( x->parent == x->parent->parent->left) {  
176.             __rb_tree_node_base* y = x->parent->parent->right;  
177.             if ( y && y->color == __rb_tree_red ) {  
178.                 x->parent->color = __rb_tree_black;  
179.                 y->color = __rb_tree_black;  
180.                 x->parent->parent->color = __rb_tree_red;  
181.                 x = x->parent->parent;  
182.             }  
183.             else {  
184.                 if ( x == x->parent->right) {  
185.                     x = x->parent;  
186.                     __rb_tree_rotate_left (x , root);  
187.                 }  
188.                 x->parent->color = __rb_tree_black;  
189.                 x->parent->parent->color = __rb_tree_red;  
190.                 __rb_tree_rotate_right (x->parent->parent , root);  
191.             }  
192.         }  
193.         else {  
194.             __rb_tree_node_base* y = x->parent->parent->right;  
195.             if ( y && y->color == __rb_tree_red) {  
196.                 x->parent->color = __rb_tree_black;  
197.                 y->color = __rb_tree_black;  
198.                 x->parent->parent->color = __rb_tree_red;  
199.             }  
200.             else {  
201.                 if (x == x->parent->left ) {  
202.                     x = x->parent;  
203.                     __rb_tree_rotate_right(x , root);  
204.                 }  
205.                 x->parent->color = __rb_tree_black;  
206.                 x->parent->parent->color = __rb_tree_red;  
207.                 __rb_tree_rotate_left(x->parent->parent , root);  
208.             }  
209.         }  
210.     }  
211.   
212.     root->color = __rb_tree_black;  
213. }  
214.   
215. inline void __rb_tree_rotate_left(__rb_tree_node_base* x , __rb_tree_node_base* &root)  
216. {  
217.     __rb_tree_node_base* y = x->right;  
218.     x->right = y->left;  
219.     if (y->left != 0)   
220.         y->left->parent = x;  
221.   
222.     if (x == root)   
223.         root = y;  
224.     else if ( x == x->parent->left )  
225.         x->parent->left = y;  
226.     else  
227.         x->parent->right = y;  
228.     y->left = x;  
229.     x->parent = y;  
230. }  
231.   
232. inline void __rb_tree_rotate_rigth(__rb_tree_node_base* x , __rb_tree_node_base* &root)  
233. {  
234.     __rb_tree_node_base* y = x->left;  
235.     x->left = y->right;  
236.     if (y->right != 0)   
237.         y->right->parent = x;  
238.   
239.     if (x == root)   
240.         root = y;  
241.     else if ( x == x->parent->left )  
242.         x->parent->left = y;  
243.     else  
244.         x->parent->right = y;  
245.     y->right = x;  
246.     x->parent = y;  
247. }  

至于函数insert_unique，是保证插入的键值不允许重复

[cpp] view plain copy

1. typename rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::iterator  
2. rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::insert_unique(const Value& x)  
3. {  
4.     link_type   y = header;  
5.     link_type   x = root();  
6.     bool    comp = true;  
7.   
8.     while ( x != 0 ) {  //从根节点开始 往下寻找适当的插入点  
9.         y = x ;  
10.         comp = key_compare(KeyOfValue()(v) , key(x));   
11.         x = comp ? left(x) : right(x); //遇大则往左，小于等于则往右  
12.     }  
13.        //离开之后， y即为插入点之父节点，此时它必为叶节点  
14.   
15.         iterator j = iterator(y);  
16.     if (comp) { //如果离开while循环的时候，comp是真，说明是插入点是y的左孩子  
17.         if (j == begin()) { //插入点父节点是最左节点，此时，不会有重复键值  
18.             return pair<iterator , bool> (__insert(x , y ,v) , true);  
19.         }  
20.         else  
21.             -- j;  
22.     }  
23.   
24.     if ( key_compare (key(j.node) , KeyOfValue()(v)))   
25.         return  pair<iterator , bool> (__insert(x , y ,v) , true);  
26.   
27.     return (pair<iterator,bool> , false);  
28. }  

插入点父节点不是最左边的节点的话，--j，是将j指向比父节点小的上一个节点，和v的键值比较，不相等说明是没有重复，因为插入点是左孩子，必然是小于父节点的，那么和比父节点小点的节点比较（v肯定是大于等于该值的），如果不是等于，则插入；

另外如果插入点是父节点y的右孩子的话，右孩子是大于等于y的，那么和y比较大小，如果不等于则插入。

这里呢，我只备注了下我看代码的时候让我迷惑的那些代码，如果哪有说的不对的地方，欢迎指正，谢谢 O(∩_∩)O哈哈~