Performance testing of trees
Your report goes in this file. Remove this description and replace it with your report. The report consists of two parts:
- Two tables showing speed comparison between polymorphic tree and Javas’ TreeMap. Use TreeSpeed.java for information on how to obtain time information. Each table should have two columns: data size (number of values used) and the time (in milliseconds). Each table should have at least five entries. The first table will show results for trees created with numbers in a sequence and the second table with trees created with random numbers.
- Two or three lines explaining the table results.
TreeSpeed.java
package performanceReport;
import java.util.Random;
import java.util.TreeMap;
import tree.PolymorphicBST;
/**
* Provides examples on how to get timing information.
* Use this example as a starting point while developing your own
* timing experiments (those associated with the report). Your
* report should be in the file performanceReport.docx.
* @author cmsc132
*
*/
public class TreeSpeed {
public static void main(String[] args) {
timePolymorphicTree();
timeTreeMap();
}
private static void timePolymorphicTree(){
Random r;
long time;
PolymorphicBST<Integer,Integer> myTree;
// Build tree with 5000 random numbers between 1 and 500000
r = new Random(100L);
time = System.currentTimeMillis();
myTree = new PolymorphicBST<Integer,Integer>();
for (int i = 1; i<5000; i++) {
int v = r.nextInt(500000);
myTree.put(v, i);
}
time = System.currentTimeMillis() – time;
System.out.println(“PolymorphicBST Time(msec) = “+time);
// Build tree with 5000 numbers in sequence
time = System.currentTimeMillis();
myTree = new PolymorphicBST<Integer,Integer>();
for (int i = 1; i<5000; i++) {
myTree.put(i, i);
}
time = System.currentTimeMillis() – time;
System.out.println(“PolymorphicBST Time(msec) = “+time);
}
private static void timeTreeMap(){
Random r;
long time;
TreeMap<Integer,Integer> myTree;
// Build tree with 5000 random numbers between 1 and 500000
r = new Random(100L);
time = System.currentTimeMillis();
myTree = new TreeMap<Integer,Integer>();
for (int i = 1; i<5000; i++) {
int v = r.nextInt(500000);
myTree.put(v, i);
}
time = System.currentTimeMillis() – time;
System.out.println(“TreeMap Time(msec) = “+time);
// Build tree with 5000 numbers in sequence
time = System.currentTimeMillis();
myTree = new TreeMap<Integer,Integer>();
for (int i = 1; i<5000; i++) {
myTree.put(i, i);
}
time = System.currentTimeMillis() – time;
System.out.println(“TreeMap Time(msec) = “+time);
}
}
PublicTests.java
package tests;
import static org.junit.Assert.*;
import java.util.NoSuchElementException;
import org.junit.Test;
import tree.PlaceKeysValuesInArrayLists;
import tree.PolymorphicBST;
public class PublicTests {
@Test
public void testBasics() {
PolymorphicBST<Integer,String> ptree = new PolymorphicBST<Integer,String>();
assertEquals(0, ptree.size());
ptree.put(2, “Two”);
ptree.put(1, “One”);
ptree.put(3, “Three”);
ptree.put(1, “OneSecondTime”);
assertEquals(3, ptree.size());
assertEquals(“OneSecondTime”, ptree.get(1));
assertEquals(“Two”, ptree.get(2));
assertEquals(“Three”, ptree.get(3));
assertEquals(null, ptree.get(8));
}
@Test
public void testEmptySearchTree() {
PolymorphicBST<String, Integer> ptree = new PolymorphicBST<String, Integer>();
assertEquals(0, ptree.size());
try {
assertEquals(null, ptree.getMin());
fail(“Should have thrown NoSuchElementException”);
} catch (NoSuchElementException e) {
assert true; // as intended
}
try {
assertEquals(null, ptree.getMax());
fail(“Should have thrown NoSuchElementException”);
} catch (NoSuchElementException e) {
assert true; // as intended
}
assertEquals(null, ptree.get(“a”));
}
@Test
public void testHeightInorderClear() {
PolymorphicBST<Integer,String> ptree = new PolymorphicBST<Integer,String>();
ptree.put(2, “Two”);
ptree.put(1, “One”);
ptree.put(3, “Three”);
ptree.put(4, “Four”);
assertEquals(3, ptree.height());
PlaceKeysValuesInArrayLists<Integer, String> task = new PlaceKeysValuesInArrayLists<Integer, String>();
ptree.inorderTraversal(task);
assertEquals(task.getKeys().toString(), “[1, 2, 3, 4]”);
assertEquals(task.getValues().toString(), “[One, Two, Three, Four]”);
ptree.clear();
assertEquals(0, ptree.size());
}
}
StudentTests.java
package tests;
import junit.framework.TestCase;
public class StudentTests extends TestCase {
}
EmptyTree.java
package tree;
import java.util.Collection;
/**
* This class is used to represent the empty search tree: a search tree that
* contains no entries.
*
* This class is a singleton class: since all empty search trees are the same,
* there is no need for multiple instances of this class. Instead, a single
* instance of the class is created and made available through the static field
* SINGLETON.
*
* The constructor is private, preventing other code from mistakenly creating
* additional instances of the class.
*
*/
public class EmptyTree<K extends Comparable<K>,V> implements Tree<K,V> {
/**
* This static field references the one and only instance of this class.
* We won’t declare generic types for this one, so the same singleton
* can be used for any kind of EmptyTree.
*/
private static EmptyTree SINGLETON = new EmptyTree();
public static <K extends Comparable<K>, V> EmptyTree<K,V> getInstance() {
return SINGLETON;
}
/**
* Constructor is private to enforce it being a singleton
*
*/
private EmptyTree() {
// Nothing to do
}
public V search(K key) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public NonEmptyTree<K, V> insert(K key, V value) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public Tree<K, V> delete(K key) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public K max() throws TreeIsEmptyException {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public K min() throws TreeIsEmptyException {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public int size() {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public void addKeysToCollection(Collection<K> c) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public Tree<K,V> subTree(K fromKey, K toKey) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public int height() {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public void inorderTraversal(TraversalTask<K,V> p) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public void rightRootLeftTraversal(TraversalTask<K,V> p) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
}
NonEmptyTree.java
package tree;
import java.util.Collection;
/**
* This class represents a non-empty search tree. An instance of this class
* should contain:
* <ul>
* <li>A key
* <li>A value (that the key maps to)
* <li>A reference to a left Tree that contains key:value pairs such that the
* keys in the left Tree are less than the key stored in this tree node.
* <li>A reference to a right Tree that contains key:value pairs such that the
* keys in the right Tree are greater than the key stored in this tree node.
* </ul>
*
*/
public class NonEmptyTree<K extends Comparable<K>, V> implements Tree<K, V> {
/* Provide whatever instance variables you need */
/**
* Only constructor we need.
* @param key
* @param value
* @param left
* @param right
*/
public NonEmptyTree(K key, V value, Tree<K,V> left, Tree<K,V> right) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public V search(K key) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public NonEmptyTree<K, V> insert(K key, V value) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public Tree<K, V> delete(K key) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public K max() {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public K min() {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public int size() {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public void addKeysToCollection(Collection<K> c) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public Tree<K,V> subTree(K fromKey, K toKey) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public int height() {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public void inorderTraversal(TraversalTask<K,V> p) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
public void rightRootLeftTraversal(TraversalTask<K,V> p) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
}
PlaceKeysValuesInArrayLists.java
package tree;
import java.util.*;
/**
* This task places key/values in two arrays in the order
* in which the key/values are seen during the traversal. If no keys/values
* are found the ArrayList will be empty (constructor creates two
* empty ArrayLists).
*
* @param <K>
* @param <V>
*/
public class PlaceKeysValuesInArrayLists<K,V> implements TraversalTask<K, V> {
/**
* Creates two ArrayList objects: one for the keys and one for the values.
*/
public PlaceKeysValuesInArrayLists() {
throw new UnsupportedOperationException(“You must implement this method.”);
}
/**
* Adds key/value to the corresponding ArrayLists.
*/
public void performTask(K key, V value) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
/**
* Returns reference to ArrayList holding keys.
* @return ArrayList
*/
public ArrayList<K> getKeys() {
throw new UnsupportedOperationException(“You must implement this method.”);
}
/**
* Returns reference to ArrayList holiding values.
* @return ArrayList
*/
public ArrayList<V> getValues() {
throw new UnsupportedOperationException(“You must implement this method.”);
}
}
PolymorphicBST.java
package tree;
import java.util.NoSuchElementException;
import java.util.Set;
/**
* This class represents the polymorphic tree.
* The implementation uses classes implementing the Tree interface to represent the
* actual search tree. Some methods of this class has been implemented for you.
*
*/
public class PolymorphicBST<K extends Comparable<K>, V> {
Tree<K,V> root = EmptyTree.getInstance();
/**
* Find the value the key is mapped to
*
* @param k –
* Search key
* @return value k is mapped to, or null if there is no mapping for the key
*/
public V get(K k) {
return root.search(k);
}
/**
* Update the mapping for the key
*
* @param k –
* key value
* @param v –
* value the key should be bound to
*/
public void put(K k, V v) {
root = root.insert(k, v);
}
/**
* Return number of keys bound by this map
*
* @return number of keys bound by this map
*/
public int size() {
return root.size();
}
/**
* Remove any existing binding for a key
*
* @param k –
* key to be removed from the map
*/
public void remove(K k) {
root = root.delete(k);
}
/**
* Return a Set of all the keys in the map
*
* @return Set of all the keys in the map
*/
public Set<K> keySet() {
throw new UnsupportedOperationException(“You must implement this method.”);
}
/**
* Return the minimum key value in the map
*
* @return the minimum key value in the map
* @throws NoSuchElementException if the map is empty
*/
public K getMin() {
throw new UnsupportedOperationException(“You must implement this method.”);
}
/**
* Return the maximum key value in the map
*
* @return the maximum key value in the map
* @throws NoSuchElementException if the map is empty
*/
public K getMax() {
throw new UnsupportedOperationException(“You must implement this method.”);
}
/**
* Return a string representation of the tree. You don’t need
* to implement this method.
*/
public String toString() {
return root.toString();
}
/**
* Return subset of TreeMap between the values fromKey-toKey. It will
* include fromKey and toKey if they are found in the original map.
* The values for fromKey and toKey do not actually need to be in the map.
* You can assume than fromKey is less than or equal to toKey.
*
* @return TreeMap consisting of subset of SearchTreeMap
*/
public PolymorphicBST<K, V> subMap(K fromKey, K toKey) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
/**
* Clears the tree by setting the root to EmptyTree
*/
public void clear() {
throw new UnsupportedOperationException(“You must implement this method.”);
}
/**
* Returns height of the tree.
* @return height of the tree.
*/
public int height() {
throw new UnsupportedOperationException(“You must implement this method.”);
}
/**
* Performs an inorder traversal applying the task to eat tree key,value pair.
* @param p
*/
public void inorderTraversal(TraversalTask<K,V> p) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
/**
* Performs the specified task on the tree using a right tree, root, left tree
* traversal.
* @param p object defining task
*/
public void rightRootLeftTraversal(TraversalTask<K,V> p) {
throw new UnsupportedOperationException(“You must implement this method.”);
}
}
TraversalTask.java
package tree;
/**
* When we perform a traversal of a tree, we call the
* performTask method to process each key,value pair in
* the tree. Classes implementing this interface, allow
* us to collect keys, print values, etc.
* @author cmsc132
*
* @param <K>
* @param <V>
*/
public interface TraversalTask<K, V> {
public void performTask(K key, V value);
}
Tree.java
package tree;
import java.util.Collection;
/**
* This interface describes the interface for both empty and non-empty search
* trees.
*/
public interface Tree <K extends Comparable<K>,V >{
/**
* Find the value that this key is bound to in this tree.
*
* @param key —
* Key to search for
* @return — value associated with the key by this Tree, or null if the key
* does not have an association in this tree.
*/
V search(K key);
/**
* Insert/update the Tree with a new key:value pair. If the key already
* exists in the tree, update the value associated with it. If the key
* doesn’t exist, insert the new key value pair.
*
* This method returns a reference to an Tree that represents the updated
* value. In many, but not all cases, the method may just return a
* reference to this. This method is annotated @CheckReturnValue because
* you have to pay attention to the return value; if you simply invoke insert on
* a Tree and ignore the return value, your code is almost certainly wrong.
*
* @param key —
* Key
* @param value —
* Value that the key maps to
* @return — updated tree
*/
NonEmptyTree<K,V> insert(K key, V value);
/**
* Delete any binding the key has in this tree. If the key isn’t bound, this
* is a no-op
*
* This method returns a reference to an Tree that represents the updated
* value. In many, but not all cases, the method may just return a
* reference to this. This method is annotated @CheckReturnValue because
* you have to pay attention to the return value; if you simply invoke delete on
* a Tree and ignore the return value, your code is almost certainly wrong.
*
* @param key —
* Key
* @return — updated tree
*/
Tree<K,V> delete(K key);
/**
* Return the maximum key in the subtree
*
* @return maximum key
* @throws TreeIsEmptyException if the tree is empty
*/
K max() throws TreeIsEmptyException;
/**
* Return the minimum key in the subtree
*
* @return minimum key
* @throws TreeIsEmptyException if the tree is empty
*/
K min() throws TreeIsEmptyException;
/**
* Return number of keys that are bound in this tree.
*
* @return number of keys that are bound in this tree.
*/
int size();
/**
* Add all keys bound in this tree to the collection c.
* The elements can be added in any order.
*/
void addKeysToCollection(Collection<K> c);
/**
* Returns a Tree containing all entries between fromKey and toKey, inclusive.
* It may not modify the original tree (a common mistake while implementing this method).
*
* @param fromKey – Lower bound value for keys in subtree
* @param toKey – Upper bound value for keys in subtree
* @return Tree containing all entries between fromKey and toKey, inclusive
*/
public Tree<K,V> subTree(K fromKey, K toKey);
/**
* Returns the height (maximum level) in the tree. A tree with only one
* entry has a height of 1.
* @return height of the tree.
*/
public int height();
/**
* Performs the specified task on the tree using an inorder traversal.
* @param p object defining task
*/
public void inorderTraversal(TraversalTask<K,V> p);
/**
* Performs the specified task on the tree using a right tree, root, left tree
* traversal.
* @param p object defining task
*/
public void rightRootLeftTraversal(TraversalTask<K,V> p);
}
TreeIsEmptyException.java
package tree;
/**
* This is a checked exception, used internally by SearchTree nodes, to signal that a tree
* has no minimum or maximum element.
*
*/
public class TreeIsEmptyException extends Exception {
}
Solution
Your report goes in this file. Remove this description and replace it with your report. The report consists of two parts:
- Two tables showing speed comparison between polymorphic tree and Javas’ TreeMap. Use TreeSpeed.java for information on how to obtain time information. Each table should have two columns: data size (number of values used) and the time (in milliseconds). Each table should have at least five entries. The first table will show results for trees created with numbers in a sequence and the second table with trees created with random numbers.
- Two or three lines explaining the table results.
Performance Report
Sequential Numbers
| Data Size | Avg. Time in Milliseconds (PolyTree / JavaTree) | |
| Entry 1 | 5000 | 114.6/0.6 |
| Entry 2 | 10000 | 474.2/11.8 |
| Entry 3 | 15000 | 1088.2/6.2 |
| Entry 4 | 20000 | 1971.2/31.4 |
| Entry 5 | 25000 | (StackOverFlow)/10.4 |
Random Numbers
| Data Size | Avg. Time in Milliseconds (PolyTree / JavaTree) | |
| Entry 1 | 5000 | 7.8/10.2 |
| Entry 2 | 10000 | 18/3 |
| Entry 3 | 15000 | 21/11.2 |
| Entry 4 | 20000 | 8/13.6 |
| Entry 5 | 25000 | 26/18.6 |
Explanation
First note that the each entry was collected by taking the average of 5 different runs of the class TreeSpeed.java with the data size indicated.
The very obvious trend is that the all the average run time statistically increased as the data size increased, with some notable outliers.
The performance of the Polymorphic Tree for sequential numbers was substantially worse. With it overflowing the stack at data size 25000. This is possibly due to the fact that all the data was sequentially added to the right side of the tree, starting with 1. Creating a tree with height equaling that of the data size. But on the other hand, Java tree should follow a similar approach as well. More research of the structure of Java tree needs to be done to accurately compare the two trees.
TreeSpeed.java
package performanceReport;
import java.util.Random;
import java.util.TreeMap;
import tree.PolymorphicBST;
/**
* Provides examples on how to get timing information.
* Use this example as a starting point while developing your own
* timing experiments (those associated with the report). Your
* report should be in the file performanceReport.docx.
* @author cmsc132
*
*/
public class TreeSpeed {
public static void main(String[] args) {
timePolymorphicTree();
timeTreeMap();
}
private static void timePolymorphicTree(){
Random r;
long time;
PolymorphicBST<Integer,Integer> myTree;
// Build tree with 5000 random numbers between 1 and 500000
r = new Random(100L);
time = System.currentTimeMillis();
myTree = new PolymorphicBST<Integer,Integer>();
for (int i = 1; i<5000; i++) {
int v = r.nextInt(500000);
myTree.put(v, i);
}
time = System.currentTimeMillis() – time;
System.out.println(“PolymorphicBST Time(msec) = “+time);
// Build tree with 5000 numbers in sequence
time = System.currentTimeMillis();
myTree = new PolymorphicBST<Integer,Integer>();
for (int i = 1; i<5000; i++) {
myTree.put(i, i);
}
time = System.currentTimeMillis() – time;
System.out.println(“PolymorphicBST Time(msec) = “+time);
}
private static void timeTreeMap(){
Random r;
long time;
TreeMap<Integer,Integer> myTree;
// Build tree with 5000 random numbers between 1 and 500000
r = new Random(100L);
time = System.currentTimeMillis();
myTree = new TreeMap<Integer,Integer>();
for (int i = 1; i<5000; i++) {
int v = r.nextInt(500000);
myTree.put(v, i);
}
time = System.currentTimeMillis() – time;
System.out.println(“TreeMap Time(msec) = “+time);
// Build tree with 5000 numbers in sequence
time = System.currentTimeMillis();
myTree = new TreeMap<Integer,Integer>();
for (int i = 1; i<5000; i++) {
myTree.put(i, i);
}
time = System.currentTimeMillis() – time;
System.out.println(“TreeMap Time(msec) = “+time);
}
}
PublicTests.java
package tests;
import static org.junit.Assert.*;
import java.util.NoSuchElementException;
import org.junit.Test;
import tree.PlaceKeysValuesInArrayLists;
import tree.PolymorphicBST;
public class PublicTests {
@Test
public void testBasics() {
PolymorphicBST<Integer,String> ptree = new PolymorphicBST<Integer,String>();
assertEquals(0, ptree.size());
ptree.put(2, “Two”);
ptree.put(1, “One”);
ptree.put(3, “Three”);
ptree.put(1, “OneSecondTime”);
assertEquals(3, ptree.size());
assertEquals(“OneSecondTime”, ptree.get(1));
assertEquals(“Two”, ptree.get(2));
assertEquals(“Three”, ptree.get(3));
assertEquals(null, ptree.get(8));
}
@Test
public void testEmptySearchTree() {
PolymorphicBST<String, Integer> ptree = new PolymorphicBST<String, Integer>();
assertEquals(0, ptree.size());
try {
assertEquals(null, ptree.getMin());
fail(“Should have thrown NoSuchElementException”);
} catch (NoSuchElementException e) {
assert true; // as intended
}
try {
assertEquals(null, ptree.getMax());
fail(“Should have thrown NoSuchElementException”);
} catch (NoSuchElementException e) {
assert true; // as intended
}
assertEquals(null, ptree.get(“a”));
}
@Test
public void testHeightInorderClear() {
PolymorphicBST<Integer,String> ptree = new PolymorphicBST<Integer,String>();
ptree.put(2, “Two”);
ptree.put(1, “One”);
ptree.put(3, “Three”);
ptree.put(4, “Four”);
assertEquals(3, ptree.height());
PlaceKeysValuesInArrayLists<Integer, String> task = new PlaceKeysValuesInArrayLists<Integer, String>();
ptree.inorderTraversal(task);
assertEquals(task.getKeys().toString(), “[1, 2, 3, 4]”);
assertEquals(task.getValues().toString(), “[One, Two, Three, Four]”);
ptree.clear();
assertEquals(0, ptree.size());
}
}
StudentTests.java
package tests;
import org.junit.Test;
import junit.framework.TestCase;
import tree.PlaceKeysValuesInArrayLists;
import tree.PolymorphicBST;
public class StudentTests extends TestCase {
@Test
public void testRightRootLeftTraversalClear() {
PolymorphicBST<Integer,String> ptree = new PolymorphicBST<Integer,String>();
ptree.put(2, “Two”);
ptree.put(1, “One”);
ptree.put(3, “Three”);
ptree.put(4, “Four”);
assertEquals(3, ptree.height());
PlaceKeysValuesInArrayLists<Integer, String> task = new PlaceKeysValuesInArrayLists<Integer, String>();
ptree.rightRootLeftTraversal(task);
assertEquals(task.getKeys().toString(), “[4, 3, 2, 1]”);
assertEquals(task.getValues().toString(), “[Four, Three, Two, One]”);
ptree.clear();
assertEquals(0, ptree.size());
}
}
EmptyTree.java
package tree;
import java.util.Collection;
/**
* This class is used to represent the empty search tree: a search tree that
* contains no entries.
*
* This class is a singleton class: since all empty search trees are the same,
* there is no need for multiple instances of this class. Instead, a single
* instance of the class is created and made available through the static field
* SINGLETON.
*
* The constructor is private, preventing other code from mistakenly creating
* additional instances of the class.
*
*/
public class EmptyTree<K extends Comparable<K>, V> implements Tree<K, V> {
/**
* This static field references the one and only instance of this class. We
* won’t declare generic types for this one, so the same singleton can be used
* for any kind of EmptyTree.
*/
private static EmptyTree SINGLETON = new EmptyTree();
public static <K extends Comparable<K>, V> EmptyTree<K, V> getInstance() {
return SINGLETON;
}
/**
* Constructor is private to enforce it being a singleton
*
*/
private EmptyTree() {
// Nothing to do
}
public V search(K key) {
return null;
// throw new UnsupportedOperationException(“You must implement this method.”);
}
public NonEmptyTree<K, V> insert(K key, V value) {
Tree<K, V> leftTemp = EmptyTree.SINGLETON;
Tree<K, V> rightTemp = EmptyTree.SINGLETON;
return new NonEmptyTree<K, V>(key, value, leftTemp, rightTemp);
// throw new UnsupportedOperationException(“You must implement this method.”);
}
public Tree<K, V> delete(K key) {
return this;
// throw new UnsupportedOperationException(“You must implement this method.”);
}
public K max() throws TreeIsEmptyException {
throw new TreeIsEmptyException();
// throw new UnsupportedOperationException(“You must implement this method.”);
}
public K min() throws TreeIsEmptyException {
throw new TreeIsEmptyException();
// throw new UnsupportedOperationException(“You must implement this method.”);
}
public int size() {
return 0;
// throw new UnsupportedOperationException(“You must implement this method.”);
}
public void addKeysToCollection(Collection<K> c) {
return;
// throw new UnsupportedOperationException(“You must implement this method.”);
}
public Tree<K, V> subTree(K fromKey, K toKey) {
return this;
// throw new UnsupportedOperationException(“You must implement this method.”);
}
public int height() {
return 0;
// throw new UnsupportedOperationException(“You must implement this method.”);
}
public void inorderTraversal(TraversalTask<K, V> p) {
// Nothing to do
// throw new UnsupportedOperationException(“You must implement this method.”);
}
public void rightRootLeftTraversal(TraversalTask<K, V> p) {
// Nothing to do
// throw new UnsupportedOperationException(“You must implement this method.”);
}
}
NonEmptyTree.java
package tree;
import java.util.Collection;
/**
* This class represents a non-empty search tree. An instance of this class
* should contain:
* <ul>
* <li>A key
* <li>A value (that the key maps to)
* <li>A reference to a left Tree that contains key:value pairs such that the
* keys in the left Tree are less than the key stored in this tree node.
* <li>A reference to a right Tree that contains key:value pairs such that the
* keys in the right Tree are greater than the key stored in this tree node.
* </ul>
*
*/
public class NonEmptyTree<K extends Comparable<K>, V> implements Tree<K, V> {
/* Provide whatever instance variables you need */
/**
* Only constructor we need.
*
* @param key
* @param value
* @param left
* @param right
*/
private K key;
private V value;
private Tree<K, V> left;
private Tree<K, V> right;
public NonEmptyTree(K key, V value, Tree<K, V> left, Tree<K, V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
// throw new UnsupportedOperationException(“You must implement this method.”);
}
public V search(K key) {
if (key.compareTo(this.key) == 0) { // you’re already at the destination
return this.value;
} else if (key.compareTo(this.key) < 0) { // the key is less so go to the left
return this.left.search(key);
} else if (key.compareTo(this.key) > 0) { // the key is bigger to go to the right
return this.right.search(key);
}
return null;
// throw new UnsupportedOperationException(“You must implement this method.”);
}
public NonEmptyTree<K, V> insert(K key, V value) {
if (this.key.compareTo(key) == 0) { // make the destination node have this value; “update the value”
this.value = value;
} else if (this.key.compareTo(key) > 0) { // go to the left if you’re not there yet
this.left = this.left.insert(key, value);
} else if (this.key.compareTo(key) < 0) { // go to the right if you’re not there yet
this.right = this.right.insert(key, value);
}
return this;
// throw new UnsupportedOperationException(“You must implement this method.”);
}
public Tree<K, V> delete(K key) {
if (this.key.compareTo(key) > 0) { // if this key is greater than input key
this.left.delete(key);
} else if (this.key.compareTo(key) < 0) { // if this key is less than the input key
this.right.delete(key);
} else { // you’re at the node to delete
try { // try searching the left for a viable node to switch
K max = this.left.max();
this.value = this.search(max);
this.key = max;
this.left = this.left.delete(this.key);
} catch (TreeIsEmptyException e) {
try { // try going to the right for a viable node to switch
K min = this.right.min();
this.value = this.search(min);
this.key = min;
this.right = this.right.delete(this.key);
} catch (TreeIsEmptyException f) { // change the node to the singleton
return EmptyTree.getInstance();
}
}
}
return this;
// throw new UnsupportedOperationException(“You must implement this method.”);
}
public K max() {
// throw new UnsupportedOperationException(“You must implement this method.”);
try {
this.right.max();
} catch (TreeIsEmptyException e) {
return this.key;
}
return this.key;
}
public K min() {
// throw new UnsupportedOperationException(“You must implement this method.”);
try {
this.left.min();
} catch (TreeIsEmptyException e) {
return this.key;
}
return this.key;
}
public int size() {
// throw new UnsupportedOperationException(“You must implement this method.”);
// recurse through the whole tree of both sides and it will add both sides up
return 1 + this.left.size() + this.right.size();
}
public void addKeysToCollection(Collection<K> c) {
// throw new UnsupportedOperationException(“You must implement this method.”);
c.add(this.key);
this.left.addKeysToCollection(c);
this.right.addKeysToCollection(c);
}
public Tree<K, V> subTree(K fromKey, K toKey) {
// throw new UnsupportedOperationException(“You must implement this method.”);
if (this.key.compareTo(fromKey) < 0) {
return this.right.subTree(fromKey, toKey);
} else if (this.key.compareTo(toKey) > 0) {
return this.left.subTree(fromKey, toKey);
} else {
return new NonEmptyTree<K, V>(this.key, this.value, this.left.subTree(fromKey, toKey),
this.right.subTree(fromKey, toKey));
}
}
public int height() {
// throw new UnsupportedOperationException(“You must implement this method.”);
int leftHeight = this.left.height();
int rightHeight = this.right.height();
if (leftHeight < rightHeight) {
return rightHeight + 1;
} else {
return leftHeight + 1;
}
}
public void inorderTraversal(TraversalTask<K, V> p) {
// throw new UnsupportedOperationException(“You must implement this method.”);
this.left.inorderTraversal(p);
p.performTask(this.key, this.value);
this.right.inorderTraversal(p);
}
public void rightRootLeftTraversal(TraversalTask<K, V> p) {
// throw new UnsupportedOperationException(“You must implement this method.”);
this.right.rightRootLeftTraversal(p);
p.performTask(this.key, this.value);
this.left.rightRootLeftTraversal(p);
}
}
PlaceKeysValuesInArrayLists.java
package tree;
import java.util.*;
/**
* This task places key/values in two arrays in the order in which the
* key/values are seen during the traversal. If no keys/values are found the
* ArrayList will be empty (constructor creates two empty ArrayLists).
*
* @param <K>
* @param <V>
*/
public class PlaceKeysValuesInArrayLists<K, V> implements TraversalTask<K, V> {
/**
* Creates two ArrayList objects: one for the keys and one for the values.
*/
private ArrayList<K> keyList;
private ArrayList<V> valueList;
public PlaceKeysValuesInArrayLists() {
// throw new UnsupportedOperationException(“You must implement this method.”);
keyList = new ArrayList<K>();
valueList = new ArrayList<V>();
}
/**
* Adds key/value to the corresponding ArrayLists.
*/
public void performTask(K key, V value) {
// throw new UnsupportedOperationException(“You must implement this method.”);
keyList.add(key);
valueList.add(value);
}
/**
* Returns reference to ArrayList holding keys.
*
* @return ArrayList
*/
public ArrayList<K> getKeys() {
// throw new UnsupportedOperationException(“You must implement this method.”);
return keyList;
}
/**
* Returns reference to ArrayList holiding values.
*
* @return ArrayList
*/
public ArrayList<V> getValues() {
// throw new UnsupportedOperationException(“You must implement this method.”);
return valueList;
}
}
PolymorphicBST.java
package tree;
import java.util.HashSet;
import java.util.NoSuchElementException;
import java.util.Set;
/**
* This class represents the polymorphic tree. The implementation uses classes
* implementing the Tree interface to represent the actual search tree. Some
* methods of this class has been implemented for you.
*
*/
public class PolymorphicBST<K extends Comparable<K>, V> {
Tree<K, V> root = EmptyTree.getInstance();
/**
* Find the value the key is mapped to
*
* @param k
* – Search key
* @return value k is mapped to, or null if there is no mapping for the key
*/
public V get(K k) {
return root.search(k);
}
/**
* Update the mapping for the key
*
* @param k
* – key value
* @param v
* – value the key should be bound to
*/
public void put(K k, V v) {
root = root.insert(k, v);
}
/**
* Return number of keys bound by this map
*
* @return number of keys bound by this map
*/
public int size() {
return root.size();
}
/**
* Remove any existing binding for a key
*
* @param k
* – key to be removed from the map
*/
public void remove(K k) {
root = root.delete(k);
}
/**
* Return a Set of all the keys in the map
*
* @return Set of all the keys in the map
*/
public Set<K> keySet() {
// throw new UnsupportedOperationException(“You must implement this method.”);
Set<K> result = new HashSet<K>();
root.addKeysToCollection(result);
return result;
}
/**
* Return the minimum key value in the map
*
* @return the minimum key value in the map
* @throws NoSuchElementException
* if the map is empty
*/
public K getMin() {
// throw new UnsupportedOperationException(“You must implement this method.”);
try {
return root.min();
} catch (TreeIsEmptyException e) {
throw new NoSuchElementException();
}
}
/**
* Return the maximum key value in the map
*
* @return the maximum key value in the map
* @throws NoSuchElementException
* if the map is empty
*/
public K getMax() {
// throw new UnsupportedOperationException(“You must implement this method.”);
try {
return root.max();
} catch (TreeIsEmptyException e) {
throw new NoSuchElementException();
}
}
/**
* Return a string representation of the tree. You don’t need to implement this
* method.
*/
public String toString() {
return root.toString();
}
/**
* Return subset of TreeMap between the values fromKey-toKey. It will include
* fromKey and toKey if they are found in the original map. The values for
* fromKey and toKey do not actually need to be in the map. You can assume than
* fromKey is less than or equal to toKey.
*
* @return TreeMap consisting of subset of SearchTreeMap
*/
public PolymorphicBST<K, V> subMap(K fromKey, K toKey) {
// throw new UnsupportedOperationException(“You must implement this method.”);
return (PolymorphicBST<K, V>) root.subTree(fromKey, toKey);
}
/**
* Clears the tree by setting the root to EmptyTree
*/
public void clear() {
// throw new UnsupportedOperationException(“You must implement this method.”);
root = EmptyTree.getInstance();
}
/**
* Returns height of the tree.
*
* @return height of the tree.
*/
public int height() {
// throw new UnsupportedOperationException(“You must implement this method.”);
return root.height();
}
/**
* Performs an inorder traversal applying the task to eat tree key,value pair.
*
* @param p
*/
public void inorderTraversal(TraversalTask<K, V> p) {
// throw new UnsupportedOperationException(“You must implement this method.”);
root.inorderTraversal(p);
}
/**
* Performs the specified task on the tree using a right tree, root, left tree
* traversal.
*
* @param p
* object defining task
*/
public void rightRootLeftTraversal(TraversalTask<K, V> p) {
// throw new UnsupportedOperationException(“You must implement this method.”);
root.rightRootLeftTraversal(p);
}
}
TraversalTask.java
package tree;
/**
* When we perform a traversal of a tree, we call the
* performTask method to process each key,value pair in
* the tree. Classes implementing this interface, allow
* us to collect keys, print values, etc.
* @author cmsc132
*
* @param <K>
* @param <V>
*/
public interface TraversalTask<K, V> {
public void performTask(K key, V value);
}
Tree.java
package tree;
import java.util.Collection;
/**
* This interface describes the interface for both empty and non-empty search
* trees.
*/
public interface Tree <K extends Comparable<K>,V >{
/**
* Find the value that this key is bound to in this tree.
*
* @param key —
* Key to search for
* @return — value associated with the key by this Tree, or null if the key
* does not have an association in this tree.
*/
V search(K key);
/**
* Insert/update the Tree with a new key:value pair. If the key already
* exists in the tree, update the value associated with it. If the key
* doesn’t exist, insert the new key value pair.
*
* This method returns a reference to an Tree that represents the updated
* value. In many, but not all cases, the method may just return a
* reference to this. This method is annotated @CheckReturnValue because
* you have to pay attention to the return value; if you simply invoke insert on
* a Tree and ignore the return value, your code is almost certainly wrong.
*
* @param key —
* Key
* @param value —
* Value that the key maps to
* @return — updated tree
*/
NonEmptyTree<K,V> insert(K key, V value);
/**
* Delete any binding the key has in this tree. If the key isn’t bound, this
* is a no-op
*
* This method returns a reference to an Tree that represents the updated
* value. In many, but not all cases, the method may just return a
* reference to this. This method is annotated @CheckReturnValue because
* you have to pay attention to the return value; if you simply invoke delete on
* a Tree and ignore the return value, your code is almost certainly wrong.
*
* @param key —
* Key
* @return — updated tree
*/
Tree<K,V> delete(K key);
/**
* Return the maximum key in the subtree
*
* @return maximum key
* @throws TreeIsEmptyException if the tree is empty
*/
K max() throws TreeIsEmptyException;
/**
* Return the minimum key in the subtree
*
* @return minimum key
* @throws TreeIsEmptyException if the tree is empty
*/
K min() throws TreeIsEmptyException;
/**
* Return number of keys that are bound in this tree.
*
* @return number of keys that are bound in this tree.
*/
int size();
/**
* Add all keys bound in this tree to the collection c.
* The elements can be added in any order.
*/
void addKeysToCollection(Collection<K> c);
/**
* Returns a Tree containing all entries between fromKey and toKey, inclusive.
* It may not modify the original tree (a common mistake while implementing this method).
*
* @param fromKey – Lower bound value for keys in subtree
* @param toKey – Upper bound value for keys in subtree
* @return Tree containing all entries between fromKey and toKey, inclusive
*/
public Tree<K,V> subTree(K fromKey, K toKey);
/**
* Returns the height (maximum level) in the tree. A tree with only one
* entry has a height of 1.
* @return height of the tree.
*/
public int height();
/**
* Performs the specified task on the tree using an inorder traversal.
* @param p object defining task
*/
public void inorderTraversal(TraversalTask<K,V> p);
/**
* Performs the specified task on the tree using a right tree, root, left tree
* traversal.
* @param p object defining task
*/
public void rightRootLeftTraversal(TraversalTask<K,V> p);
}
TreeIsEmptyException.java
package tree;
/**
* This is a checked exception, used internally by SearchTree nodes, to signal that a tree
* has no minimum or maximum element.
*
*/
public class TreeIsEmptyException extends Exception {
}