| 223 | } |
| 224 | |
| 225 | static void rebalanceRemove(Tree *t, Node *parent, Node *n) |
| 226 | { |
| 227 | Node *tmp; |
| 228 | while ((n == nullptr || RB_COLOR(n) == RB_BLACK) && n != t->root) |
| 229 | { |
| 230 | if (RB_LEFT(parent) == n) |
| 231 | { |
| 232 | tmp = RB_RIGHT(parent); |
| 233 | if (RB_COLOR(tmp) == RB_RED) |
| 234 | { |
| 235 | RB_COLOR(tmp) = RB_BLACK; |
| 236 | RB_COLOR(parent) = RB_RED; |
| 237 | rotateLeft(t, parent); |
| 238 | tmp = RB_RIGHT(parent); |
| 239 | } |
| 240 | if ((RB_LEFT(tmp) == nullptr || |
| 241 | RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) && |
| 242 | (RB_RIGHT(tmp) == nullptr || |
| 243 | RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) |
| 244 | { |
| 245 | RB_COLOR(tmp) = RB_RED; |
| 246 | n = parent; |
| 247 | parent = RB_PARENT(n); |
| 248 | } |
| 249 | else |
| 250 | { |
| 251 | if (RB_RIGHT(tmp) == nullptr || |
| 252 | RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK) |
| 253 | { |
| 254 | Node *oleft; |
| 255 | if ((oleft = RB_LEFT(tmp)) != nullptr) |
| 256 | RB_COLOR(oleft) = RB_BLACK; |
| 257 | RB_COLOR(tmp) = RB_RED; |
| 258 | rotateRight(t, tmp); |
| 259 | tmp = RB_RIGHT(parent); |
| 260 | } |
| 261 | RB_COLOR(tmp) = RB_COLOR(parent); |
| 262 | RB_COLOR(parent) = RB_BLACK; |
| 263 | if (RB_RIGHT(tmp)) |
| 264 | RB_COLOR(RB_RIGHT(tmp)) = RB_BLACK; |
| 265 | rotateLeft(t, parent); |
| 266 | n = t->root; |
| 267 | break; |
| 268 | } |
| 269 | } |
| 270 | else |
| 271 | { |
| 272 | tmp = RB_LEFT(parent); |
| 273 | if (RB_COLOR(tmp) == RB_RED) |
| 274 | { |
| 275 | RB_COLOR(tmp) = RB_BLACK; |
| 276 | RB_COLOR(parent) = RB_RED; |
| 277 | rotateRight(t, parent); |
| 278 | tmp = RB_LEFT(parent); |
| 279 | } |
| 280 | if ((RB_LEFT(tmp) == nullptr || |
| 281 | RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) && |
| 282 | (RB_RIGHT(tmp) == nullptr || |
no test coverage detected