On AVLTree.java, implement:

? rotateLeft ? rotateLeftRight ? getHeightDifference ? Should return the difference in height between the subtrees of the incoming node. A positive # if the left subtree is taller, negative # otherwise.

package TreePackage; public class AVLTree> extends BinarySearchTree implements SearchTreeInterface { public AVLTree() { super(); } public AVLTree(T rootEntry) { super(rootEntry); } // Other methods in SearchTreeInterface are inherited from BinarySearchTree // Corrects an imbalance at the node closest to a structural change in the left subtree of the node's left child // nodeN is a node, closest to the newly added leaf, at which an imbalance occurs and that has a left child private BinaryNode rotateRight(BinaryNode nodeN) { BinaryNode nodeC = nodeN.getLeftChild(); nodeN.setLeftChild(nodeC.getRightChild()); nodeC.setRightChild(nodeN); return nodeC; } private BinaryNode rotateLeft(BinaryNode nodeN) { // TODO  return nodeN; } private BinaryNode rotateRightLeft(BinaryNode nodeN) { BinaryNode nodeC = nodeN.getRightChild(); nodeN.setRightChild(rotateRight(nodeC)); return rotateLeft(nodeN); } private BinaryNode rotateLeftRight(BinaryNode nodeN) { // TODO  return nodeN; } public T add(T newEntry) { T result = null; if(isEmpty()) setRootNode(new BinaryNode<>(newEntry)); else { BinaryNode rootNode = getRootNode(); result = addEntry(rootNode, newEntry); setRootNode(rebalance(rootNode)); } return result; } private T addEntry(BinaryNode rootNode, T newEntry) { T result = null; int comparison = newEntry.compareTo(rootNode.getData()); if (comparison == 0) { result = rootNode.getData(); rootNode.setData(newEntry); } else if (comparison < 0) { if (rootNode.hasLeftChild()) { BinaryNode leftChild = rootNode.getLeftChild(); result = addEntry(leftChild, newEntry); rootNode.setLeftChild(rebalance(leftChild)); } else rootNode.setLeftChild(new BinaryNode<>(newEntry)); } else { if(rootNode.hasRightChild()) { BinaryNode rightChild = rootNode.getRightChild(); result = addEntry(rightChild, newEntry); rootNode.setRightChild(rebalance(rightChild)); } else rootNode.setRightChild(new BinaryNode<>(newEntry)); } return result; } private BinaryNode rebalance(BinaryNode nodeN) { int heightDifference = getHeightDifference(nodeN); if (heightDifference > 1) { // left subtree is taller by more than 1, so addition was in left subtree if (getHeightDifference(nodeN.getLeftChild()) > 0) { // addition was in left subtree of left child nodeN = rotateRight(nodeN); } else { // addition was in right subtree of left child nodeN = rotateLeftRight(nodeN); } } else if (heightDifference < -1) { // right subtree is taller by more than 1, so addition was in right subtree if (getHeightDifference(nodeN.getRightChild()) < 0) { // addition was in right subtree of right child nodeN = rotateLeft(nodeN); } else { // addition was in left subtree of right child nodeN = rotateRightLeft(nodeN); } } return nodeN; } private int getHeightDifference(BinaryNode nodeN) { // TODO  return 1; } } 

package TreePackage; public class BinarySearchTree> extends BinaryTree implements SearchTreeInterface { public BinarySearchTree() { super(); } public BinarySearchTree(T rootEntry) { super(); setRootNode(new BinaryNode<>(rootEntry)); } @Override public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree) { throw new UnsupportedOperationException(); } @Override public T getEntry(T anEntry) { return findEntry(getRootNode(), anEntry); } private T findEntry(BinaryNode rootNode, T anEntry) { T result = null; if(rootNode != null) { T rootEntry = rootNode.getData(); if(anEntry.equals(rootEntry)) { result = rootEntry; } else if(anEntry.compareTo(rootEntry) < 0) { result = findEntry(rootNode.getLeftChild(), anEntry); } else { result = findEntry(rootNode.getRightChild(), anEntry); } } return result; } @Override public T add(T anEntry) { T result = null; if(isEmpty()) setRootNode(new BinaryNode<>(anEntry)); else result = addIterative(getRootNode(), anEntry); return result; } private T addIterative(BinaryNode rootNode, T anEntry) { // TODO  return null; } @Override public T remove(T anEntry) { ReturnObject oldEntry = new ReturnObject(null); BinaryNode newRoot = removeEntry(getRootNode(), anEntry, oldEntry); setRootNode(newRoot); return oldEntry.getData(); } private BinaryNode removeEntry(BinaryNode rootNode, T anEntry, ReturnObject oldEntry) { if (rootNode != null) { T rootData = rootNode.getData(); int comparison = anEntry.compareTo(rootData); if (comparison == 0) // anEntry is in the root entry of this subtree { oldEntry.setData(rootData); rootNode = removeFromRoot(rootNode); } else if (comparison < 0) // anEntry < root entry { BinaryNode leftChild = rootNode.getLeftChild(); BinaryNode subTreeRoot = removeEntry(leftChild, anEntry, oldEntry); rootNode.setLeftChild(subTreeRoot); } else { BinaryNode rightChild = rootNode.getRightChild(); BinaryNode subTreeRoot = removeEntry(rightChild, anEntry, oldEntry); rootNode.setRightChild(subTreeRoot); } } return rootNode; } private BinaryNode removeFromRoot(BinaryNode rootNode) { // Case 1: rootNode has two children if (rootNode.hasLeftChild() && rootNode.hasRightChild()) { // find node with largest entry in left subtree BinaryNode leftSubtreeRoot = rootNode.getLeftChild(); BinaryNode largestNode = findLargest(leftSubtreeRoot); // replace entry in root with largest from left subtree rootNode.setData(largestNode.getData()); // remove node with largest entry in left subtree rootNode.setLeftChild(removeLargest(leftSubtreeRoot)); } // Case 2: rootNode has at most one child else if (rootNode.hasRightChild()) rootNode = rootNode.getRightChild(); else rootNode = rootNode.getLeftChild(); return rootNode; } // Finds the node containing the largest entry in a given tree // rootNode is the root node of the tree // Returns the node containing the largest entry in the tree. private BinaryNode findLargest(BinaryNode rootNode) { if (rootNode.hasRightChild()) rootNode = findLargest(rootNode.getRightChild()); return rootNode; } // Removes the node containing the largest entry in a given tree // rootNode is the root node of the tree // Returns the root node of the revised tree. private BinaryNode removeLargest(BinaryNode rootNode) { if (rootNode.hasRightChild()) { BinaryNode rightChild = rootNode.getRightChild(); rightChild = removeLargest(rightChild); rootNode.setRightChild(rightChild); } else rootNode = rootNode.getLeftChild(); return rootNode; } public T getMax() { return null; } public T getMin() { return null; } private class ReturnObject { private T data; public ReturnObject(T newData) { data = newData; } public void setData(T newData) { data = newData; } public T getData() { return data; } } private T addEntry(BinaryNode rootNode, T anEntry) { T result = null; int comparison = anEntry.compareTo(rootNode.getData()); if(comparison == 0) { result = rootNode.getData(); rootNode.setData(anEntry); } else if(comparison < 0) { if(rootNode.hasLeftChild()) result = addEntry(rootNode.getLeftChild(), anEntry); else rootNode.setLeftChild(new BinaryNode<>(anEntry)); } else { if(rootNode.hasRightChild()) result = addEntry(rootNode.getRightChild(), anEntry); else rootNode.setRightChild(new BinaryNode<>(anEntry)); } return result; } @Override public boolean contains(T anEntry) { return getEntry(anEntry) != null; } } 

public interface SearchTreeInterface> extends TreeInterface { /** Searches for a specific entry in this tree.  * @param anEntry An object to be found  * @return True if the object was found in the tree */  boolean contains(T anEntry); /** Retrieves a specific entry in this tree  * @param anEntry an object to be found  * @return Either that object that was found in the tree or null if no such object exists */  T getEntry(T anEntry); /** Adds a new entry to this tree, if it does not match an existing object in the tree.  * Otherwise, replaces the existing object with the new entry  * @param anEntry An object to be added to the tree  * @return Either null if anyEntry was not in the tree but has been added, or the existing  * entry that matched the parameter anEntry and has been replaced in the tree */  T add(T anEntry); /** Removes a specific entry from this tree  * @param anEntry An object to be removed  * @return Either the object that was removed from the tree or null if no such object exists  */  T remove(T anEntry); /** Creates an iterator that traverses all entries in this tree.  * @return An iterator that provides sequential and ordered access to the entries in this tree  */  public Iterator getInorderIterator(); public T getMin(); public T getMax(); } 

package TreePackage; class BinaryNode { private T data; private BinaryNode leftChild; private BinaryNode rightChild; public BinaryNode() { this(null); } public BinaryNode(T dataPortion) { this(dataPortion, null, null); } public BinaryNode(T dataPortion, BinaryNode newLeftChild, BinaryNode newRightChild) { data = dataPortion; leftChild = newLeftChild; rightChild = newRightChild; } public T getData() { return data; } public void setData(T newData) { data = newData; } public BinaryNode getLeftChild() { return leftChild; } public void setLeftChild(BinaryNode newLeftChild) { leftChild = newLeftChild; } public boolean hasLeftChild() { return leftChild != null; } public BinaryNode getRightChild() { return rightChild; } public void setRightChild(BinaryNode newRightChild) { rightChild = newRightChild; } public boolean hasRightChild() { return rightChild != null; } public boolean isLeaf() { return (leftChild == null) && (rightChild == null); } /** counts the nodes in the subtree rooted at this node  * @return The number of nodes in the subtree rooted at this node  */  public int getNumberOfNodes() { int leftNumber = 0; int rightNumber = 0; if (leftChild != null) { leftNumber = leftChild.getNumberOfNodes(); } if (rightChild != null) { rightNumber = rightChild.getNumberOfNodes(); } return 1 + leftNumber + rightNumber; } /** Computes the height of the subtree rooted at this node  * @return The height of the subtree rooted at this node  */  public int getHeight() { return getHeight(this); } private int getHeight(BinaryNode node) { int height = 0; if(node != null) { height = 1 + Math.max(getHeight(node.getLeftChild()), getHeight(node.getRightChild())); } return height; } /** Copies the subtree rooted at this node  * @return The root of a copy of the subtree rooted at this node.  */  public BinaryNode copy() { BinaryNode newRoot = new BinaryNode<>(data); if(leftChild != null) { newRoot.setLeftChild(leftChild.copy()); } if(rightChild != null) { newRoot.setRightChild(rightChild.copy()); } return newRoot; } } 

package TreePackage; import java.util.Collection; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Queue; import java.util.function.Predicate; import QueuePackage.LinkedQueue; import QueuePackage.QueueInterface; import StackPackage.*; public class BinaryTree implements BinaryTreeInterface { protected BinaryNode root; public BinaryTree() { root = null; } public BinaryTree(T rootData) { root = new BinaryNode<>(rootData); } public BinaryTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { initializeTree(rootData, leftTree, rightTree); } protected void setRootNode(BinaryNode rootNode) { root = rootNode; } @Override public T getRootData() { if(!isEmpty()) { return root.getData(); } return null; } @Override public int getHeight() { return root.getHeight(); } @Override public int getNumberOfNodes() { return root.getNumberOfNodes(); } @Override public Iterator getPostorderIterator() { return null; } @Override public void clear() { root = null; } @Override public Iterator getInorderIterator() { return new InOrderIterator(); } @Override public Iterator getLevelOrderIterator() { return new LevelOrderIterator(); } @Override public Iterator getPreorderIterator() { return null; } @Override public void setTree(T rootData) { setTree(rootData, null, null); } @Override public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree) { initializeTree(rootData, (BinaryTree) leftTree, (BinaryTree) rightTree); } private void initializeTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { root = new BinaryNode<>(rootData); if((leftTree != null) && !leftTree.isEmpty()) root.setLeftChild(leftTree.root); if((rightTree != null) && !rightTree.isEmpty()) { if (rightTree != leftTree) { root.setRightChild(rightTree.root); } else root.setRightChild(rightTree.root.copy()); } if((leftTree != null) && (leftTree != this)) { leftTree.clear(); } if((rightTree != null) && (rightTree != this)) { rightTree.clear(); } } @Override public boolean isEmpty() { return root == null; } // traversal that doesn't use an iterator (for demonstration purposes only) public void iterativeInorderTraverse() { StackInterface> nodeStack = new ArrayStack<>(); BinaryNode currentNode = root; while (!nodeStack.isEmpty() || (currentNode != null)) { while (currentNode != null) { nodeStack.push(currentNode); currentNode = currentNode.getLeftChild(); } if (!nodeStack.isEmpty()) { BinaryNode nextNode = nodeStack.pop(); System.out.println(nextNode.getData()); currentNode = nextNode.getRightChild(); } } } BinaryNode getRootNode() { return root; } private class LevelOrderIterator implements Iterator { private Queue> queue; private QueueInterface> nodeQueue; public LevelOrderIterator() { nodeQueue = new LinkedQueue<>(); if(root != null) { nodeQueue.enqueue(root); } } @Override public boolean hasNext() { return !nodeQueue.isEmpty(); } @Override public T next() { BinaryNode nextNode; if(hasNext()) { nextNode = nodeQueue.dequeue(); BinaryNode leftChild = nextNode.getLeftChild(); BinaryNode rightChild = nextNode.getRightChild(); if(leftChild != null) { nodeQueue.enqueue(leftChild); } if(rightChild != null) { nodeQueue.enqueue(rightChild); } } else { throw new NoSuchElementException(); } return nextNode.getData(); } } private class InOrderIterator implements Iterator { private StackInterface> nodeStack; private BinaryNode currentNode; public InOrderIterator() { nodeStack = new ArrayStack<>(); currentNode = root; } @Override public boolean hasNext() { return !nodeStack.isEmpty() || (currentNode != null); } @Override public T next() { BinaryNode nextNode = null; // find leftmost node with no left child while(currentNode != null) { nodeStack.push(currentNode); currentNode = currentNode.getLeftChild(); } if(!nodeStack.isEmpty()) { nextNode = nodeStack.pop(); currentNode = nextNode.getRightChild(); } else throw new NoSuchElementException(); return nextNode.getData(); } } }