Swap the linkages of two nodes in a tree.
(Entry<K,V> x, Entry<K,V> y)
| 1433 | * Swap the linkages of two nodes in a tree. |
| 1434 | */ |
| 1435 | private void swapPosition(Entry<K,V> x, Entry<K,V> y) { |
| 1436 | // Save initial values. |
| 1437 | Entry<K,V> px = x.parent, lx = x.left, rx = x.right; |
| 1438 | Entry<K,V> py = y.parent, ly = y.left, ry = y.right; |
| 1439 | boolean xWasLeftChild = px != null && x == px.left; |
| 1440 | boolean yWasLeftChild = py != null && y == py.left; |
| 1441 | |
| 1442 | // Swap, handling special cases of one being the other's parent. |
| 1443 | if (x == py) { // x was y's parent |
| 1444 | x.parent = y; |
| 1445 | |
| 1446 | if (yWasLeftChild) { |
| 1447 | y.left = x; |
| 1448 | y.right = rx; |
| 1449 | } else { |
| 1450 | y.right = x; |
| 1451 | y.left = lx; |
| 1452 | } |
| 1453 | } else { |
| 1454 | x.parent = py; |
| 1455 | |
| 1456 | if (py != null) { |
| 1457 | if (yWasLeftChild) |
| 1458 | py.left = x; |
| 1459 | else |
| 1460 | py.right = x; |
| 1461 | } |
| 1462 | y.left = lx; |
| 1463 | y.right = rx; |
| 1464 | } |
| 1465 | |
| 1466 | if (y == px) { // y was x's parent |
| 1467 | y.parent = x; |
| 1468 | if (xWasLeftChild) { |
| 1469 | x.left = y; |
| 1470 | x.right = ry; |
| 1471 | } else { |
| 1472 | x.right = y; |
| 1473 | x.left = ly; |
| 1474 | } |
| 1475 | } else { |
| 1476 | y.parent = px; |
| 1477 | if (px != null) { |
| 1478 | if (xWasLeftChild) |
| 1479 | px.left = y; |
| 1480 | else |
| 1481 | px.right = y; |
| 1482 | } |
| 1483 | x.left = ly; |
| 1484 | x.right = ry; |
| 1485 | } |
| 1486 | |
| 1487 | // Fix children's parent pointers |
| 1488 | if (x.left != null) |
| 1489 | x.left.parent = x; |
| 1490 | |
| 1491 | if (x.right != null) |
| 1492 | x.right.parent = x; |