00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
#include <bits/stl_tree.h>
00059
00060
namespace std
00061 {
00062 _Rb_tree_node_base*
00063 _Rb_tree_increment(_Rb_tree_node_base* __x)
00064 {
00065
if (__x->_M_right != 0)
00066 {
00067 __x = __x->_M_right;
00068
while (__x->_M_left != 0)
00069 __x = __x->_M_left;
00070 }
00071
else
00072 {
00073 _Rb_tree_node_base* __y = __x->_M_parent;
00074
while (__x == __y->_M_right)
00075 {
00076 __x = __y;
00077 __y = __y->_M_parent;
00078 }
00079
if (__x->_M_right != __y)
00080 __x = __y;
00081 }
00082
return __x;
00083 }
00084
00085
const _Rb_tree_node_base*
00086 _Rb_tree_increment(
const _Rb_tree_node_base* __x)
00087 {
00088
return _Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));
00089 }
00090
00091 _Rb_tree_node_base*
00092 _Rb_tree_decrement(_Rb_tree_node_base* __x)
00093 {
00094
if (__x->_M_color == _S_red
00095 && __x->_M_parent->_M_parent == __x)
00096 __x = __x->_M_right;
00097
else if (__x->_M_left != 0)
00098 {
00099 _Rb_tree_node_base* __y = __x->_M_left;
00100
while (__y->_M_right != 0)
00101 __y = __y->_M_right;
00102 __x = __y;
00103 }
00104
else
00105 {
00106 _Rb_tree_node_base* __y = __x->_M_parent;
00107
while (__x == __y->_M_left)
00108 {
00109 __x = __y;
00110 __y = __y->_M_parent;
00111 }
00112 __x = __y;
00113 }
00114
return __x;
00115 }
00116
00117
const _Rb_tree_node_base*
00118 _Rb_tree_decrement(
const _Rb_tree_node_base* __x)
00119 {
00120
return _Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x));
00121 }
00122
00123
void
00124 _Rb_tree_rotate_left(_Rb_tree_node_base*
const __x,
00125 _Rb_tree_node_base*& __root)
00126 {
00127 _Rb_tree_node_base*
const __y = __x->_M_right;
00128
00129 __x->_M_right = __y->_M_left;
00130
if (__y->_M_left !=0)
00131 __y->_M_left->_M_parent = __x;
00132 __y->_M_parent = __x->_M_parent;
00133
00134
if (__x == __root)
00135 __root = __y;
00136
else if (__x == __x->_M_parent->_M_left)
00137 __x->_M_parent->_M_left = __y;
00138
else
00139 __x->_M_parent->_M_right = __y;
00140 __y->_M_left = __x;
00141 __x->_M_parent = __y;
00142 }
00143
00144
void
00145 _Rb_tree_rotate_right(_Rb_tree_node_base*
const __x,
00146 _Rb_tree_node_base*& __root)
00147 {
00148 _Rb_tree_node_base*
const __y = __x->_M_left;
00149
00150 __x->_M_left = __y->_M_right;
00151
if (__y->_M_right != 0)
00152 __y->_M_right->_M_parent = __x;
00153 __y->_M_parent = __x->_M_parent;
00154
00155
if (__x == __root)
00156 __root = __y;
00157
else if (__x == __x->_M_parent->_M_right)
00158 __x->_M_parent->_M_right = __y;
00159
else
00160 __x->_M_parent->_M_left = __y;
00161 __y->_M_right = __x;
00162 __x->_M_parent = __y;
00163 }
00164
00165
void
00166 _Rb_tree_insert_and_rebalance(
const bool __insert_left,
00167 _Rb_tree_node_base* __x,
00168 _Rb_tree_node_base* __p,
00169 _Rb_tree_node_base& __header)
00170 {
00171 _Rb_tree_node_base *& __root = __header._M_parent;
00172
00173
00174 __x->_M_parent = __p;
00175 __x->_M_left = 0;
00176 __x->_M_right = 0;
00177 __x->_M_color = _S_red;
00178
00179
00180
00181
00182
00183
if (__insert_left)
00184 {
00185 __p->_M_left = __x;
00186
00187
if (__p == &__header)
00188 {
00189 __header._M_parent = __x;
00190 __header._M_right = __x;
00191 }
00192
else if (__p == __header._M_left)
00193 __header._M_left = __x;
00194 }
00195
else
00196 {
00197 __p->_M_right = __x;
00198
00199
if (__p == __header._M_right)
00200 __header._M_right = __x;
00201 }
00202
00203
while (__x != __root
00204 && __x->_M_parent->_M_color == _S_red)
00205 {
00206 _Rb_tree_node_base*
const __xpp = __x->_M_parent->_M_parent;
00207
00208
if (__x->_M_parent == __xpp->_M_left)
00209 {
00210 _Rb_tree_node_base*
const __y = __xpp->_M_right;
00211
if (__y && __y->_M_color == _S_red)
00212 {
00213 __x->_M_parent->_M_color = _S_black;
00214 __y->_M_color = _S_black;
00215 __xpp->_M_color = _S_red;
00216 __x = __xpp;
00217 }
00218
else
00219 {
00220
if (__x == __x->_M_parent->_M_right)
00221 {
00222 __x = __x->_M_parent;
00223 _Rb_tree_rotate_left(__x, __root);
00224 }
00225 __x->_M_parent->_M_color = _S_black;
00226 __xpp->_M_color = _S_red;
00227 _Rb_tree_rotate_right(__xpp, __root);
00228 }
00229 }
00230
else
00231 {
00232 _Rb_tree_node_base*
const __y = __xpp->_M_left;
00233
if (__y && __y->_M_color == _S_red)
00234 {
00235 __x->_M_parent->_M_color = _S_black;
00236 __y->_M_color = _S_black;
00237 __xpp->_M_color = _S_red;
00238 __x = __xpp;
00239 }
00240
else
00241 {
00242
if (__x == __x->_M_parent->_M_left)
00243 {
00244 __x = __x->_M_parent;
00245 _Rb_tree_rotate_right(__x, __root);
00246 }
00247 __x->_M_parent->_M_color = _S_black;
00248 __xpp->_M_color = _S_red;
00249 _Rb_tree_rotate_left(__xpp, __root);
00250 }
00251 }
00252 }
00253 __root->_M_color = _S_black;
00254 }
00255
00256 _Rb_tree_node_base*
00257 _Rb_tree_rebalance_for_erase(_Rb_tree_node_base*
const __z,
00258 _Rb_tree_node_base& __header)
00259 {
00260 _Rb_tree_node_base *& __root = __header._M_parent;
00261 _Rb_tree_node_base *& __leftmost = __header._M_left;
00262 _Rb_tree_node_base *& __rightmost = __header._M_right;
00263 _Rb_tree_node_base* __y = __z;
00264 _Rb_tree_node_base* __x = 0;
00265 _Rb_tree_node_base* __x_parent = 0;
00266
00267
if (__y->_M_left == 0)
00268 __x = __y->_M_right;
00269
else
00270
if (__y->_M_right == 0)
00271 __x = __y->_M_left;
00272
else
00273 {
00274
00275 __y = __y->_M_right;
00276
while (__y->_M_left != 0)
00277 __y = __y->_M_left;
00278 __x = __y->_M_right;
00279 }
00280
if (__y != __z)
00281 {
00282
00283 __z->_M_left->_M_parent = __y;
00284 __y->_M_left = __z->_M_left;
00285
if (__y != __z->_M_right)
00286 {
00287 __x_parent = __y->_M_parent;
00288
if (__x) __x->_M_parent = __y->_M_parent;
00289 __y->_M_parent->_M_left = __x;
00290 __y->_M_right = __z->_M_right;
00291 __z->_M_right->_M_parent = __y;
00292 }
00293
else
00294 __x_parent = __y;
00295
if (__root == __z)
00296 __root = __y;
00297
else if (__z->_M_parent->_M_left == __z)
00298 __z->_M_parent->_M_left = __y;
00299
else
00300 __z->_M_parent->_M_right = __y;
00301 __y->_M_parent = __z->_M_parent;
00302
std::swap(__y->_M_color, __z->_M_color);
00303 __y = __z;
00304
00305 }
00306
else
00307 {
00308 __x_parent = __y->_M_parent;
00309
if (__x)
00310 __x->_M_parent = __y->_M_parent;
00311
if (__root == __z)
00312 __root = __x;
00313
else
00314
if (__z->_M_parent->_M_left == __z)
00315 __z->_M_parent->_M_left = __x;
00316
else
00317 __z->_M_parent->_M_right = __x;
00318
if (__leftmost == __z)
00319
if (__z->_M_right == 0)
00320 __leftmost = __z->_M_parent;
00321
00322
else
00323 __leftmost = _Rb_tree_node_base::_S_minimum(__x);
00324
if (__rightmost == __z)
00325
if (__z->_M_left == 0)
00326 __rightmost = __z->_M_parent;
00327
00328
else
00329 __rightmost = _Rb_tree_node_base::_S_maximum(__x);
00330 }
00331
if (__y->_M_color != _S_red)
00332 {
00333
while (__x != __root && (__x == 0 || __x->_M_color == _S_black))
00334
if (__x == __x_parent->_M_left)
00335 {
00336 _Rb_tree_node_base* __w = __x_parent->_M_right;
00337
if (__w->_M_color == _S_red)
00338 {
00339 __w->_M_color = _S_black;
00340 __x_parent->_M_color = _S_red;
00341 _Rb_tree_rotate_left(__x_parent, __root);
00342 __w = __x_parent->_M_right;
00343 }
00344
if ((__w->_M_left == 0 ||
00345 __w->_M_left->_M_color == _S_black) &&
00346 (__w->_M_right == 0 ||
00347 __w->_M_right->_M_color == _S_black))
00348 {
00349 __w->_M_color = _S_red;
00350 __x = __x_parent;
00351 __x_parent = __x_parent->_M_parent;
00352 }
00353
else
00354 {
00355
if (__w->_M_right == 0
00356 || __w->_M_right->_M_color == _S_black)
00357 {
00358 __w->_M_left->_M_color = _S_black;
00359 __w->_M_color = _S_red;
00360 _Rb_tree_rotate_right(__w, __root);
00361 __w = __x_parent->_M_right;
00362 }
00363 __w->_M_color = __x_parent->_M_color;
00364 __x_parent->_M_color = _S_black;
00365
if (__w->_M_right)
00366 __w->_M_right->_M_color = _S_black;
00367 _Rb_tree_rotate_left(__x_parent, __root);
00368
break;
00369 }
00370 }
00371
else
00372 {
00373
00374 _Rb_tree_node_base* __w = __x_parent->_M_left;
00375
if (__w->_M_color == _S_red)
00376 {
00377 __w->_M_color = _S_black;
00378 __x_parent->_M_color = _S_red;
00379 _Rb_tree_rotate_right(__x_parent, __root);
00380 __w = __x_parent->_M_left;
00381 }
00382
if ((__w->_M_right == 0 ||
00383 __w->_M_right->_M_color == _S_black) &&
00384 (__w->_M_left == 0 ||
00385 __w->_M_left->_M_color == _S_black))
00386 {
00387 __w->_M_color = _S_red;
00388 __x = __x_parent;
00389 __x_parent = __x_parent->_M_parent;
00390 }
00391
else
00392 {
00393
if (__w->_M_left == 0 || __w->_M_left->_M_color == _S_black)
00394 {
00395 __w->_M_right->_M_color = _S_black;
00396 __w->_M_color = _S_red;
00397 _Rb_tree_rotate_left(__w, __root);
00398 __w = __x_parent->_M_left;
00399 }
00400 __w->_M_color = __x_parent->_M_color;
00401 __x_parent->_M_color = _S_black;
00402
if (__w->_M_left)
00403 __w->_M_left->_M_color = _S_black;
00404 _Rb_tree_rotate_right(__x_parent, __root);
00405
break;
00406 }
00407 }
00408
if (__x) __x->_M_color = _S_black;
00409 }
00410
return __y;
00411 }
00412
00413
unsigned int
00414 _Rb_tree_black_count(
const _Rb_tree_node_base* __node,
00415
const _Rb_tree_node_base* __root)
00416 {
00417
if (__node == 0)
00418
return 0;
00419
unsigned int __sum = 0;
00420
do
00421 {
00422
if (__node->_M_color == _S_black)
00423 ++__sum;
00424
if (__node == __root)
00425
break;
00426 __node = __node->_M_parent;
00427 }
00428
while (1);
00429
return __sum;
00430 }
00431 }