Delete node p, and then rebalance the tree.
(Entry<K,V> p)
| 1324 | * Delete node p, and then rebalance the tree. |
| 1325 | */ |
| 1326 | private void deleteEntry(Entry<K,V> p) { |
| 1327 | decrementSize(); |
| 1328 | |
| 1329 | // If strictly internal, first swap position with successor. |
| 1330 | if (p.left != null && p.right != null) { |
| 1331 | Entry<K,V> s = successor(p); |
| 1332 | swapPosition(s, p); |
| 1333 | } |
| 1334 | |
| 1335 | // Start fixup at replacement node, if it exists. |
| 1336 | Entry<K,V> replacement = (p.left != null ? p.left : p.right); |
| 1337 | |
| 1338 | if (replacement != null) { |
| 1339 | // Link replacement to parent |
| 1340 | replacement.parent = p.parent; |
| 1341 | if (p.parent == null) |
| 1342 | root = replacement; |
| 1343 | else if (p == p.parent.left) |
| 1344 | p.parent.left = replacement; |
| 1345 | else |
| 1346 | p.parent.right = replacement; |
| 1347 | |
| 1348 | // Null out links so they are OK to use by fixAfterDeletion. |
| 1349 | p.left = p.right = p.parent = null; |
| 1350 | |
| 1351 | // Fix replacement |
| 1352 | if (p.color == BLACK) |
| 1353 | fixAfterDeletion(replacement); |
| 1354 | } else if (p.parent == null) { // return if we are the only node. |
| 1355 | root = null; |
| 1356 | } else { // No children. Use self as phantom replacement and unlink. |
| 1357 | if (p.color == BLACK) |
| 1358 | fixAfterDeletion(p); |
| 1359 | |
| 1360 | if (p.parent != null) { |
| 1361 | if (p == p.parent.left) |
| 1362 | p.parent.left = null; |
| 1363 | else if (p == p.parent.right) |
| 1364 | p.parent.right = null; |
| 1365 | p.parent = null; |
| 1366 | } |
| 1367 | } |
| 1368 | } // deleteEntry |
| 1369 | |
| 1370 | /** From CLR **/ |
| 1371 | private void fixAfterDeletion(Entry<K,V> x) { |
no test coverage detected