Due: Monday 7/7/14 @5:30pm via users.cs.umb.edu:cs210/hw5

Purpose:
Gain experience implementing a right and left rotation on a binary searchtree.

Complete and test the code for your iteratorLevelOrder method from HW5.

Study the right and left rotation algorithms so that you understand the design of the methods that you will need to implement.

Semantics of Right Rotation
A. Make the left child of the root the new root
B. Make former root the right child of the new root
C. Make right child of the former left child of the former root the new left child of the former root

Semantics of Left Rotation
A. Make the right child of the root the new root
B. Make former root the left child of the new root
C. Make left child of the former right child of the former root the new right child of the former root

Semantics of Rightleft Rotation
A. Right rotation around right child of root
B. Left rotation around root

The Rotation class has the main method. Its main method sets up two test case binary trees using the LinkedBinaryTree class and calls the LinkedBinaryTree class methods rotateRight and rotateLeft (that you will write below) to rotate the root of each test case tree. It uses the Iterator object returned by the iteratorLevelOrder method to print the contents of each tree both before and after its rotation.

The following files are here: https://github.com/ieee8023/cs210-summer2014

1. In rotateRight, write code to implement the right rotation algorithm

2. In rotateLeft, write code to implement the left rotation algorithm

3. Write a method visualize() in the LinkedBinaryTree class that shows the trees using the GraphStream library. Hint: First traverse the tree and add all nodes then traverse it again to add the edges. Use the .element field of the object as the name and label of the node.

4. Write a memo.txt describing any problems you had during this assignment and what you learned. Explain when you would want to use the rotateRight or rotateLeft methods and how your code could determine that it needed to do one of these two rotations.

A sample run of the finished program for the right rotation is shown here:

$ java Rotation
Contents of rightTree before right rotation
13
7
15
5
10
null
null
3
null
null
null
null
null
Contents of rightTree after right rotation
7
5
13
3
null
10
15
null
null
null
null
null
null
. . .

Here is a sample visualize method that uses the GraphStream library

   public void visualize(){
		
	   // make a new tree/graph and tell it to show labels
	   	Graph graphStream = new SingleGraph("");
		graphStream.addAttribute("ui.stylesheet", "graph {text-mode: normal;}");
		
		///////////////////////////////////
		// These are sample entries. You will need to 
		// start at the root and add all the nodes and edges
		// in the tree starting with root
		
		// here we create a root node and then color it 
		Node n = graphStream.addNode("a");
		n.addAttribute("ui.label", "a");
		n.addAttribute("ui.style", "fill-color: rgb(0,100,255);");
		
		// here we add nodes and then add a label
		graphStream.addNode("b").addAttribute("ui.label", "b");	
		graphStream.addNode("c").addAttribute("ui.label", "c");
		graphStream.addNode("d").addAttribute("ui.label", "d");
		graphStream.addNode("e").addAttribute("ui.label", "e");
		
		// here the edges are added (some name, source, destination)
		// the name of the edge isn't important just make it unique
		graphStream.addEdge("a-b", "a", "b");
		graphStream.addEdge("a-c", "a", "c");
		graphStream.addEdge("b-d", "b", "d");
		graphStream.addEdge("b-e", "b", "e");
		
		///////////////////////////////////////
		
		
		//show the tree
		graphStream.display(true);
   }

Grading (total 10 points):

Turn in the following files: BinaryTreeADT.java, BinaryTreeNode.java, LinkedBinaryTree.java, Rotation.java, memo.txt

3 points: rotateRight working

3 points: rotateLeft working

2 points: Visualize using GraphStream

2 points: memo.txt, easy to grade.