| 252 | } |
| 253 | |
| 254 | void deleteFixUp(RBTreeNode* x) |
| 255 | { |
| 256 | while (x != root && x->color == BLACK) { |
| 257 | if (x->isLeft()) { |
| 258 | auto w = x->brother(); |
| 259 | if (w->color == RED) { |
| 260 | // case 1 |
| 261 | w->color = BLACK; |
| 262 | x->p->color = RED; |
| 263 | leftRotate(x->p); |
| 264 | w = x->p->right; |
| 265 | } |
| 266 | if (w->left->color == BLACK && w->right->color == BLACK) { |
| 267 | // case 2 |
| 268 | w->color = RED; |
| 269 | x = x->p; |
| 270 | } else { |
| 271 | if (w->right->color == BLACK) { |
| 272 | // case 3 |
| 273 | w->left->color = BLACK; |
| 274 | w->color = RED; |
| 275 | rightRotate(w); |
| 276 | w = x->p->right; |
| 277 | } |
| 278 | |
| 279 | // case 4 |
| 280 | w->color = x->p->color; |
| 281 | x->p->color = BLACK; |
| 282 | w->right->color = BLACK; |
| 283 | leftRotate(x->p); |
| 284 | x = root; |
| 285 | } |
| 286 | } else { |
| 287 | auto w = x->p->left; |
| 288 | if (w->color == RED) { |
| 289 | // case 1 |
| 290 | w->color = BLACK; |
| 291 | x->p->color = RED; |
| 292 | rightRotate(x->p); |
| 293 | w = x->p->left; |
| 294 | } |
| 295 | if (w->right->color == BLACK && w->left->color == BLACK) { |
| 296 | // case 2 |
| 297 | w->color = RED; |
| 298 | x = x->p; |
| 299 | } else { |
| 300 | if (w->left->color == BLACK) { |
| 301 | // case 3 |
| 302 | w->right->color = BLACK; |
| 303 | w->color = RED; |
| 304 | leftRotate(w); |
| 305 | w = x->p->left; |
| 306 | } |
| 307 | |
| 308 | // case 4 |
| 309 | w->color = x->p->color; |
| 310 | x->p->color = BLACK; |
| 311 | w->left->color = BLACK; |