From CLR
(Entry<K,V> x)
| 1278 | |
| 1279 | /** From CLR **/ |
| 1280 | private void fixAfterInsertion(Entry<K,V> x) { |
| 1281 | x.color = RED; |
| 1282 | |
| 1283 | while (x != null && x != root && x.parent.color == RED) { |
| 1284 | if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { |
| 1285 | Entry<K,V> y = rightOf(parentOf(parentOf(x))); |
| 1286 | if (colorOf(y) == RED) { |
| 1287 | setColor(parentOf(x), BLACK); |
| 1288 | setColor(y, BLACK); |
| 1289 | setColor(parentOf(parentOf(x)), RED); |
| 1290 | x = parentOf(parentOf(x)); |
| 1291 | } else { |
| 1292 | if (x == rightOf(parentOf(x))) { |
| 1293 | x = parentOf(x); |
| 1294 | rotateLeft(x); |
| 1295 | } |
| 1296 | setColor(parentOf(x), BLACK); |
| 1297 | setColor(parentOf(parentOf(x)), RED); |
| 1298 | if (parentOf(parentOf(x)) != null) |
| 1299 | rotateRight(parentOf(parentOf(x))); |
| 1300 | } |
| 1301 | } else { |
| 1302 | Entry<K,V> y = leftOf(parentOf(parentOf(x))); |
| 1303 | if (colorOf(y) == RED) { |
| 1304 | setColor(parentOf(x), BLACK); |
| 1305 | setColor(y, BLACK); |
| 1306 | setColor(parentOf(parentOf(x)), RED); |
| 1307 | x = parentOf(parentOf(x)); |
| 1308 | } else { |
| 1309 | if (x == leftOf(parentOf(x))) { |
| 1310 | x = parentOf(x); |
| 1311 | rotateRight(x); |
| 1312 | } |
| 1313 | setColor(parentOf(x), BLACK); |
| 1314 | setColor(parentOf(parentOf(x)), RED); |
| 1315 | if (parentOf(parentOf(x)) != null) |
| 1316 | rotateLeft(parentOf(parentOf(x))); |
| 1317 | } |
| 1318 | } |
| 1319 | } |
| 1320 | root.color = BLACK; |
| 1321 | } // fixAfterInsertion |
| 1322 | |
| 1323 | /** |
| 1324 | * Delete node p, and then rebalance the tree. |
no test coverage detected