| 292 | } |
| 293 | |
| 294 | void deleteFixUp(RBTreeNode* x) |
| 295 | { |
| 296 | while (x != root && x->color == BLACK) { |
| 297 | if (x->isLeft()) { |
| 298 | auto w = x->brother(); |
| 299 | if (w->color == RED) { |
| 300 | // printf("delete left case 1\n"); |
| 301 | w->color = BLACK; |
| 302 | x->p->color = RED; |
| 303 | leftRotate(x->p); |
| 304 | w = x->p->right; |
| 305 | } |
| 306 | if (w->left->color == BLACK && w->right->color == BLACK) { |
| 307 | // printf("delete left case 2\n"); |
| 308 | w->color = RED; |
| 309 | x = x->p; |
| 310 | } else { |
| 311 | if (w->right->color == BLACK) { |
| 312 | // printf("delete left case 3\n"); |
| 313 | w->left->color = BLACK; |
| 314 | w->color = RED; |
| 315 | rightRotate(w); |
| 316 | w = x->p->right; |
| 317 | } |
| 318 | |
| 319 | // printf("delete left case 4\n"); |
| 320 | w->color = x->p->color; |
| 321 | x->p->color = BLACK; |
| 322 | w->right->color = BLACK; |
| 323 | leftRotate(x->p); |
| 324 | x = root; |
| 325 | } |
| 326 | } else { |
| 327 | auto w = x->p->left; |
| 328 | if (w->color == RED) { |
| 329 | // printf("delete right case 1\n"); |
| 330 | w->color = BLACK; |
| 331 | x->p->color = RED; |
| 332 | rightRotate(x->p); |
| 333 | w = x->p->left; |
| 334 | } |
| 335 | if (w->right->color == BLACK && w->left->color == BLACK) { |
| 336 | // printf("delete right case 2\n"); |
| 337 | w->color = RED; |
| 338 | x = x->p; |
| 339 | } else { |
| 340 | if (w->left->color == BLACK) { |
| 341 | // printf("delete right case 3\n"); |
| 342 | w->right->color = BLACK; |
| 343 | w->color = RED; |
| 344 | leftRotate(w); |
| 345 | w = x->p->left; |
| 346 | } |
| 347 | |
| 348 | // printf("delete right case 4\n"); |
| 349 | w->color = x->p->color; |
| 350 | x->p->color = BLACK; |
| 351 | w->left->color = BLACK; |