Question

Java programming.

Purpose:

• Understanding the rotation operation in a search tree
• Understanding heap & priority queue

Problems:

• Implementation: Rotation (left & right rotations)
  • Use the code template below.
  • Implement the rotateLeft() and rotateRight() functions.
  • How to test your implementation? When a left rotation is applied to the root, apparently the root is changed. One right rotation will restore the tree back to the original

Sample input:

7
30 15 40 5 20 35 45

Sample output:

in-order: 5 15 20 30 35 40 45 
before rotation: 
pre-order: 30 15 5 20 40 35 45 
after rotating left: 
pre-order: 40 30 15 5 20 35 45 
after rotating right: 
pre-order: 30 15 5 20 40 35 45

USE THE BELOW TEMPLATE:

import java.util.*;
	class Node <E> {
	private Node<E> left;
	private Node<E> right;
	private E data;
	Node(E data) {
	this.data = data;
	left = null;
	right = null;
	}
	void setData(E d) {
	data = d;
	}
	E getData() {
	return data;
	}
	void setLeft(Node<E> i) {
	left = i;
	}
	void setRight(Node<E> i) {
	right = i;
	}
	Boolean hasLeft() {
	return left != null;
	}
	Node<E> getLeft() {
	return left;
	}
	Boolean hasRight() {
	return right != null;
	}
	Node<E> getRight() {
	return right;
	}
	}
	class BST <E extends Comparable<?super E>> {
	private Node<E> root;
	BST() {
	root = null;
	}
	Node<E> getRoot() {
	return root;
	}
	void inOrder() {
	System.out.print("in-order: ");
	inOrder(root);
	System.out.println();
	}
	void inOrder(Node<E>root) {
	if(root == null) return;
	inOrder(root.getLeft());
	System.out.print(root.getData() + " ");
	inOrder(root.getRight());
	}
	void preOrder() {
	System.out.print("pre-order: ");
	preOrder(root);
	System.out.println();
	}
	void preOrder(Node<E>root) {
	if(root == null) return;
	System.out.print(root.getData() + " ");
	if(root.hasLeft()) preOrder(root.getLeft());
	if(root.hasRight()) preOrder(root.getRight());
	}
	void insert(E data) {
	root = insert(root, data);
	}
	Node<E> insert(Node<E> root, E data) {
	if (root == null) {
	return new Node<E>(data);
	} else {
	Node<E> cur;
	if (root.getData().compareTo(data) > 0) {
	cur = insert(root.getLeft(), data);
	root.setLeft(cur);
	} else {
	cur = insert(root.getRight(), data);
	root.setRight(cur);
	}
	return root;
	}
	}
	//apply left rotate to the root node
	void rotateLeft() {
	}
	//apply right rotate to the root node
	void rotateRight() {
	}
	}
	public class RotationMain {
	public static void main(String[] argv) {
	int n;
	Scanner in = new Scanner(System.in);
	n = in.nextInt();
	BST<Integer> tree = new BST<Integer>();
	for(int i = 0; i < n; i ++) {
	tree.insert(in.nextInt());
	}
	in.close();
	//if BST is correctly built, items will be displayed in sorted order using
	//in-order traversal
	tree.inOrder();
	System.out.println("before rotation: ");
	tree.preOrder();
	System.out.println("after rotating left: ");
	tree.rotateLeft();
	tree.preOrder();
	System.out.println("after rotating right: ");
	tree.rotateRight();
	tree.preOrder();
	}
	}

Answer 1

For the above code to be updated we need to update the pointers in order to make sure that the tree should rotate left or right.

Following is the updated code in JAVA, It is in bold

import java.util.*;
class Node <E> {
private Node<E> left;
private Node<E> right;
private E data;
Node(E data) {
this.data = data;
left = null;
right = null;
}
void setData(E d) {
data = d;
}
E getData() {
return data;
}
void setLeft(Node<E> i) {
left = i;
}
void setRight(Node<E> i) {
right = i;
}
Boolean hasLeft() {
return left != null;
}
Node<E> getLeft() {
return left;
}
Boolean hasRight() {
return right != null;
}
Node<E> getRight() {
return right;
}
}
class BST <E extends Comparable<?super E>> {
private Node<E> root;
BST() {
root = null;
}
Node<E> getRoot() {
return root;
}
void inOrder() {
System.out.print("in-order: ");
inOrder(root);
System.out.println();
}
void inOrder(Node<E>root) {
if(root == null) return;
inOrder(root.getLeft());
System.out.print(root.getData() + " ");
inOrder(root.getRight());
}
void preOrder() {
System.out.print("pre-order: ");
preOrder(root);
System.out.println();
}
void preOrder(Node<E>root) {
if(root == null) return;
System.out.print(root.getData() + " ");
if(root.hasLeft()) preOrder(root.getLeft());
if(root.hasRight()) preOrder(root.getRight());
}
void insert(E data) {
root = insert(root, data);
}
Node<E> insert(Node<E> root, E data) {
if (root == null) {
return new Node<E>(data);
} else {
Node<E> cur;
if (root.getData().compareTo(data) > 0) {
cur = insert(root.getLeft(), data);
root.setLeft(cur);
} else {
cur = insert(root.getRight(), data);
root.setRight(cur);
}
return root;
}
}
//apply left rotate to the root node
void rotateLeft() {
   Node x = this.getRoot().getLeft();
Node T2 = x.getRight();

// Perform rotation
x.setRight(this.getRoot());
this.getRoot().setLeft(T2);
this.root = x;
}
//apply right rotate to the root node
void rotateRight() {
   Node y = this.getRoot().getRight();
Node T2 = y.getLeft();

// Perform rotation
y.setLeft(this.getRoot());
this.getRoot().setRight(T2);
  
this.root = y;
}
}
public class RotationMain {
public static void main(String[] argv) {
int n;
Scanner in = new Scanner(System.in);
n = in.nextInt();
BST<Integer> tree = new BST<Integer>();
for(int i = 0; i < n; i ++) {
tree.insert(in.nextInt());
}
in.close();
//if BST is correctly built, items will be displayed in sorted order using
//in-order traversal
tree.inOrder();
System.out.println("before rotation: ");
tree.preOrder();
System.out.println("after rotating left: ");
tree.rotateLeft();
tree.preOrder();
System.out.println("after rotating right: ");
tree.rotateRight();
tree.preOrder();
}
}

The following is the output for the same.

That was a nice question to answer
Friend, If you have any doubts in understanding do let me know in the comment section. I will be happy to help you further.
Please like it if you think effort deserves like.
Thanks