The aim is to implement a right tree rotation in Java.
Modify Snippet 3.15 to make the method perform a right tree rotation instead of a left tree rotation. The following code shows the required modification:
public void rightRotate(BinaryTreeNode<K, V> nodeX,
BinaryTreeNode<K, V> parent) {
BinaryTreeNode<K, V> nodeY = nodeX.getLeft().get();
nodeX.setLeft(nodeY.getRight().orElse(null));
if (parent == null)
this.root = nodeY;
else if (parent.getRight().filter(n -> n == nodeX).isPresent())
parent.setRight(nodeY);
else
parent.setLeft(nodeY);
nodeY.setRight(nodeX);
}
Snippet 3.16: Java implementation of the right tree rotation. Source class name: SimpleBinaryTree
The right rotation is an exact mirror image of the left rotation. It's enough to change all the left references with right references and vice versa.
In this section, we saw how we can improve the performance of binary search trees by using tree rotations to balance the data structure. This enables the tree to remain of a shorter height with a runtime complexity of O(log n).