This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Rotates the subtree so that its root's right child is the new root. | |
| */ | |
| private void rotateLeft(Node<K, V> root) { | |
| final Node<K, V> left = root.left; | |
| final Node<K, V> pivot = root.right; | |
| final Node<K, V> pivotLeft = pivot.left; | |
| final Node<K, V> pivotRight = pivot.right; | |
| // move the pivot's left child to the root's right | |
| root.right = pivotLeft; | |
| if (pivotLeft != null) { | |
| pivotLeft.parent = root; | |
| } | |
| replaceInParent(root, pivot); | |
| // move the root to the pivot's left | |
| pivot.left = root; | |
| root.parent = pivot; | |
| // fix heights | |
| root.height = Math.max(left != null ? left.height : 0, | |
| pivotLeft != null ? pivotLeft.height : 0) + 1; | |
| pivot.height = Math.max(root.height, | |
| pivotRight != null ? pivotRight.height : 0) + 1; | |
| } |
