1 //RB_Tree.hpp
2 //The code of red black trees
3 //2011/12/31 by Adoo
4 // The foundation :http://www.roading.org/?p=691
5
6 #ifndef RB_TREES_HPP
7 #define RB_TREES_HPP
8 #include<iterator>
9 #include<iomanip>
10 #include<deque>
11 enum RB_Color{
12 red,
13 black
14 };
15 template<typename Type>
16 class RB_Tree{
17 private:
18 struct rb_node;
19 class node_iterator;
20 public:
21 typedef node_iterator iterator;
22 typedef const node_iterator const_iterator;
23
24 RB_Tree(){
25 _nil->_color=black;
26 _root=_nil;
27 };
28 ~RB_Tree()
29 {
30 for(iterator iter=begin(); iter !=end();)
31 {
32 eraser(iter++);
33 }
34 _root=_nil;
35 }
36 iterator begin(){
37 return sub_min(_root);
38 }
39 iterator end(){
40 return iterator(_nil);
41 }
42 static iterator sub_min(iterator iter){
43 rb_node *min=iter.pointer();
44 while(min->_left !=_nil)
45 {
46 min=min->_left;
47 }
48 return min;
49 }
50 iterator insert(Type value){
51 rb_node *y=_nil;
52 rb_node *z=new rb_node; //create a node by the value
53 //needn't set the z's color ,because red is rb_node's default color
54 z->_value=value;
55 z->_left=_nil;
56 z->_right=_nil;
57
58 rb_node* x=_root; //x iterator from _root
59 while(x !=_nil )
60 {
61 y=x;
62 if(x->_value< z->_value)
63 x=x->_right;
64 else
65 x=x->_left;
66 }
67 z->_parent=y;
68 if(y==_nil) //determine z should be y's left or right
69 _root=z;
70 else
71 if(y->_value < z->_value)
72 y->_right=z;
73 else
74 y->_left=z;
75
76 rb_insert_fixup(z); //restore the red black properties
77 return z;
78 }
79 iterator eraser(iterator iter){
80 rb_node* z=iter.pointer();
81 rb_node* y=z;
82 RB_Color y_color=y->_color;
83 rb_node *x=NULL;
84
85 if(z->_left==_nil ){ //case1: z's left child is nil
86 x=z->_right;
87 transplant(z, z->_right);
88 }
89 else{
90 if(z->_right==_nil){// case2: z's right child is nil
91 x=z->_left;
92 transplant(z, z->_left);
93 }
94 else{//case3: both children of z are not nil
95 y=sub_min(z->_right).pointer();
96 y_color=y->_color;
97 x=y->_right;
98 if(y->_parent==z)
99 x->_parent=y;
100 else{
101 transplant(y, y->_right);
102 //link z's right subtree into y, only y isn't z's child;
103 y->_right=z->_right;
104 y->_right->_parent=y;
105 }
106 transplant(z, y);
107 //link z's subtree into y.
108 y->_left=z->_left;
109 y->_left->_parent=y;
110 y->_color=z->_color;
111 }
112 }
113 iterator result = ++iterator(z);
114 delete z;
115 if(y_color==black)
116 eraser_fixup(x);
117 return result;
118 };
119
120 private:
121 void transplant(rb_node *u, rb_node *v){
122 if(u->_parent == _nil)
123 {
124 _root=v;
125 }
126 else
127 if(u== u->_parent->_left)
128 u->_parent->_left=v;
129 else
130 u->_parent->_right=v;
131 v->_parent=u->_parent;
132 };
133 void left_rotate(rb_node *x){
134 rb_node* y=x->_right; //set y
135 x->_right=y->_left; //turn y's left subtree into x's right subtree
136 if(y->_left !=_nil)
137 y->_left->_parent=x;
138 y->_parent=x->_parent; //link y to x's parent
139 if(x->_parent != _nil )
140 {
141 if(x->_parent->_left==x)
142 x->_parent->_left=y;
143 else
144 x->_parent->_right=y;
145 }
146 else
147 _root=y;
148 y->_left=x; //put x on y's left
149 x->_parent=y;
150 }
151 void right_rotate(rb_node *x)
152 {
153 rb_node* y=x->_left; //set y;
154 x->_left=y->_right; //turn y's right subtree into x's left subtree
155 if(y->_right != _nil)
156 y->_right->_parent=x;
157 y->_parent=x->_parent; //link y to x's parent
158 if(x->_parent != _nil)
159 {
160 if(x==x->_parent->_left)
161 x->_parent->_left=y;
162 else
163 x->_parent->_right=y;
164 }
165 else
166 _root=y;
167 y->_right=x; //put x on y's right;
168 x->_parent=y;
169 }
170 void rb_insert_fixup(rb_node* z){
171 while(z->_parent->_color==red){
172 if(z->_parent==z->_parent->_parent->_left){
173 rb_node* y=z->_parent->_parent->_right;
174 if(y->_color==red){
175 z->_parent->_color=black;
176 y->_color=black;
177 z->_parent->_parent->_color=red;
178 z=z->_parent->_parent;
179 }
180 else{
181 if(z==z->_parent->_right){
182 z=z->_parent;
183 left_rotate(z);
184 }
185 z->_parent->_color=black;
186 z->_parent->_parent->_color=red;
187 right_rotate(z->_parent->_parent);
188 }
189 }
190 else{
191 rb_node* y=z->_parent->_parent->_left;
192 if(y->_color==red){
193 z->_parent->_color=black;
194 y->_color=black;
195 z->_parent->_parent->_color=red;
196 z=z->_parent->_parent;
197 }
198 else{
199 if(z==z->_parent->_left){
200 z=z->_parent;
201 right_rotate(z);
202 }
203 z->_parent->_color=black;
204 z->_parent->_parent->_color=red;
205 left_rotate(z->_parent->_parent);
206 }
207 }
208 }
209 _root->_color=black;
210 };;
211 void eraser_fixup(rb_node* x){
212 while(x != _root && x->_color ==black){
213 if(x==x->_parent->_left){
214 rb_node* w=x->_parent->_right;
215 if(w->_color == red){ //case 1: x's sbling w is red.
216 x->_parent->_color=red;
217 w->_color=black;
218 left_rotate(x->_parent); //convert case 1 to case 2.
219 }
220 else{//case 2 : x's sbling w is black.
221 if(w->_left->_color == black && w->_right->_color == black){
222 //case 2.1 : both children of w are black
223 w->_color=red;
224 x=x->_parent;
225 }
226 else{
227 if(w->_left->_color==red && w->_right->_color==black){
228 //case 2.2: w's left child is red and w's right child is black.
229 //we convert this case to case 2.3.
230 w->_left->_color=black;
231 w->_color=red;
232 right_rotate(w);
233 w=x->_parent->_right;
234 }
235 //case 2.3: w's right child is red;
236 w->_color=x->_parent->_color;
237 w->_parent->_color=black;
238 w->_right->_color= black;
239 left_rotate(x->_parent);
240 x=_root; //terminate the loop;
241 }
242 }
243 }
244 else{
245 rb_node* w=x->_parent->_right;
246 if(w->_color == red){
247 x->_parent->_color=red;
248 w->_color=black;
249 left_rotate(x->_parent);
250 }
251 else{
252 if(w->_right->_color == black && w->_left->_color == black){
253 w->_color=red;
254 x=x->_parent;
255 }
256 else{
257 if(w->_right->_color==red && w->_left->_color == black){
258 w->_right->_color=black;
259 w->_color=red;
260 left_rotate(w);
261 w=x->_parent->_left;
262 }
263 w->_color=x->_parent->_color;
264 w->_parent->_color=black;
265 w->_left->_color= black;
266 right_rotate(x->_parent);
267 x=_root; //terminate the loop;
268 }
269 }
270 }
271 }
272 x->_color=black;
273 };
274
275 private:
276 rb_node* _root;
277 public:
278 static rb_node* _nil;
279 };
280
281 template<typename Type>
282 struct RB_Tree<Type>::rb_node
283 {
284 Type _value;
285 rb_node *_left;
286 rb_node *_right;
287 rb_node *_parent;
288 RB_Color _color;
289 rb_node()
290 :_value(Type()),_left(NULL),_right(NULL),_parent(NULL),_color(red)
291 {};
292 };
293
294 template<typename Type>
295 class RB_Tree<Type>::node_iterator:
296 public std::iterator<std::bidirectional_iterator_tag ,rb_node>
297 {
298 public:
299 node_iterator(rb_node* n): _node(n){};
300
301 Type& operator* () const{
302 return _node->_value;
303 };
304
305 rb_node* operator ->()const
306 {
307 return _node;
308 };
309
310 node_iterator operator++ ()
311 {
312 if(_node==RB_Tree<Type>::_nil)
313 return _node;
314 if(_node->_right!=RB_Tree<Type>::_nil)
315 {
316 *this=RB_Tree<Type>::sub_min(_node->_right);
317 }
318 else
319 {
320 rb_node *parent=_node->_parent;
321 while(parent !=RB_Tree<Type>::_nil&& _node==parent->_right)
322 {
323 _node=parent;
324 parent=parent->_parent;
325 }
326 _node=parent;
327 }
328 return *this;
329 }
330
331 node_iterator operator++(int){
332 node_iterator ret(*this);
333 ++*this;
334 return ret;
335 }
336
337 bool operator ==( node_iterator r_iter)
338 {
339 return _node == r_iter._node;
340 };
341
342 bool operator !=( node_iterator r_iter){
343 return _node != r_iter._node;
344 }
345
346 rb_node* pointer()
347 {
348 return _node;
349 }
350 private:
351 rb_node* _node;
352 };
353 #endif
354 //各种
转载自：http://www.roading.org/algorithm/introductiontoalgorithm/c%E5%AE%9E%E7%8E%B0%E7%BA%A2%E9%BB%91%E6%A0%91%EF%BC%8C%E4%BB%BFstl%E5%B0%81%E8%A3%85.html