You will write code that implements and exercises a basic Tree Map.
The TreeMap is a MAP ADT built on a Binary Search Tree (BST).
There are plenty of implementations of "tree"
stuff out there. Please do not copy those.
You may read them for ideas and understanding,
but I want you to
write your own code and follow the structure I outline below.
The learning in this activity comes
from actually powering through all the reasoning needed to
get the pointers (object references) and recursive calls hooked up correctly.
In our program, we will have one object (class) as "the TreeMap". We will call the various MAP interface functions such as put, get, hasKey. on that object. There is a field in the TreeMap object that is a link to the root data cell. If the field is null, then there are no nodes in the tree, and its size is 0.
You must write recursive methods yourself to get this assignment correct. The methods that must be recursive are noted in the interface notes following. The BST implementation examples in your text are good patterns to follow in structuring your solution. Note that many are recursive methods.
Keep in mind that many of your methods in TreeMap are similar to BST operations, but are not directly the same... due to the extra MAP behavior and structure mixed in.
To be as abstract as we can, your code templates below contains two top level interfaces: Map, and TreeMap. The Map interface contains operations that are common to a Map implementation whether it is done via BST or Hash table (or LIST... or any other method). These methods are the put, get, remove, hasKey, and size operations. The put and remove operations are basic data add and delete functions; get is finding data in the structure, specifically giving a key and retrieving the associated value; hasKey tells if a key is already mapped to some value in the Map; size tells how many (key,value) pairs are in the Map. These functions are defined without reference to BST (or any other implementation structure).
We ultimately are implementing a MAP behavior and we are using a BST to provide it. A MAP stores (key,value) pairs, and any specific key can be in the MAP at most once. Said another way, the keys in a MAP must be unique.
To implement a MAP we can use any data organization that allows us to keep track of a collection of (key,value) pairs, to add them and remove them, and to check the uniqueness of any key we try to add. A LIST would do, and would give us O(N) worst case behavior when adding a new pair (since the LIST would be searched to ensure the new key was not already there).
A BST is another option... and we will use a BST in this assignment. Using a BST to implement a MAP allows us to store and retrieve (key,value) pairs in O(log N) average time, so we expect greatly improved execution times than with a LIST. We will see later that a Hash table can also serve as the implementation vehicle and give us O(1) expected times; this speed comes at a cost in other areas... specifically you cannot do one of the things a TreeMap allows -- getting keys out in sorted order. In the Java collections library, you will find both TreeMap and HashMap as implementations of MAP.
In this assignment, the basic idea is to build a BST using the keys (strings here) as data elements for determining cell placement in the tree. Comparing string for "greater than" and "lesser than" will mean using alphabetic order (or dictionary order). The tree cells will also contain a field for the Value object of a (key,value) pair. When you put a (key,value) pair into the MAP, you first add a cell to the BST using the key, and once it is added you put the value object into the tree cell containing the key. See the interface behavior for details. Note that sometimes put does not make a new cell, but alters one already in the tree; this is part of why we said the TreeMap code is not directly BST code.
The TreeMap interface extends the Map interface and adds a few operations that are possible because the implementation method will be a BST. These include minKey, maxKey, and getKeys (in sorted order). Note that these are possible with a Hash implementation, but they are not efficient. With a BST we can get this information with O(log N) algorithms (as we studied in class).
Hand in your code as per the instructions under Assignment 2 in Sakai. There will be zipping and naming instructions there.
For uniformity, and to aid timely grading, you must write your program with these specific structures.
package assignment2_f20;
/* Behavior: A Map will provide this collection of operations:
put:
in: a string (the key) and a Value object (associated with the key)
return: a Value object, or null
effect:
if key is NOT in the structure
add a new cell to the structure and put the key into it, the value into it
and return null
if key IS in the structure
do not add a new cell
instead, replace the Value object in the existing cell
with the new Value object
return the old Value object (the one being replaced)
get:
in: a string (the key)
return: a Value object, or null
effect:
if key is NOT in the structure
return null (this includes when the structure is empty, size 0)
if key IS in the structure
return the Value object from the cell containing the key
remove:
in: a string (the key of the pair to be removed)
return: nothing in all cases (return void)
effect:
if the key IS in the structure
take the whole cell out of the structure... the (key,value) pair will not be in the
structure after
if the key is NOT in the structure
make no changes to the state of the structure
hasKey:
in: a string (the key)
return: boolean
effect:
if key IS in the structure (meaning there is a (key,value) pair for the key),
return true
if key is NOT in the structure, return false
in both cases, no change to the structure tate
size:
in: nothing
return: int, the number of (key,value) pairs stored in the map structure
effect: no change to state of tree nodes
*/
// ADT operations
public interface Map {
public Value put ( String k, Value v ); // recursive
public Value get (String k); // recursive
public void remove (String k); // recursive
public boolean hasKey(String k); // recursive
public int size();
}
package assignment2_f20;
/* Behavior: A TreeMap will provide Map operations, and also these:
minKey:
in: none
return: string, the key from the tree that is smallest
effect: no tree state change
if tree size if 0, return null
maxKey:
in: none
return: string, the key from the tree that is largest
effect: no tree state change
if tree size if 0, return null
getKeys
in: nothing
return: an array of strings, containing just the keys from the tree cells
effect: the array of strings is produced in alphabetic order, small to large
note, this means do an in-order traversal to get the keys out of the BST sorted
*/
// ADT operations
public interface TreeMap extends Map {
public String maxKey(); // recursive
public String minKey(); // recursive
public String[] getKeys();
public int height(); // recursive, given as an example
// leave this in... for grader use
// also specific to tree structure
public TMCell getRoot();
}
//-------------------------------------------------------------------
// put this Interface and Implementation into your code as is
// the grader may need these methods to examine the structure
// that your code creates
//-------------------------------------------------------------------
// you may add methods and structure as you need to
// for example, you may want a toString to help with your debugging
// but to not remove what we have given here
//-------------------------------------------------------------------
package assignment2_f20;
public interface TMCell { // these will be used by the grader to
// examine your data structure contents
public void setKey(String newKey);
public String getKey();
public void setValue(Value newValue);
public Value getValue();
public void setLeft(TMCell newLeft);
public TMCell getLeft();
public void setRight(TMCell newRight);
public TMCell getRight();
}
public class TMCell_imp implements TMCell {
public String key;
public Value val;
public TMCell LC;
public TMCell RC;
TMCell_imp(String k, Value v) { key=k; val=v; LC=RC=null; }
@Override
public void setKey(String newKey) { key = newKey; }
@Override
public String getKey() { return key; }
@Override
public void setValue(Value newValue) { val = newValue; }
@Override
public Value getValue() { return val; }
@Override
public void setLeft(TMCell newLeft) { LC = newLeft; }
@Override
public TMCell getLeft() { return LC; }
@Override
public void setRight(TMCell newRight) { RC = newRight; }
@Override
public TMCell getRight() { return RC; }
}
//-------------------------------------------------------------------
// put this Interface and Implementation into your code as is
// the grader may need these methods to examine the structure
// that your code creates
//-------------------------------------------------------------------
// you may add methods and structure as you need to
// for example, you may want a toString to help with your debugging
// but to not remove what we have given here
//-------------------------------------------------------------------
package assignment2_f20;
public interface Value {
public void setIdNum(int n);
public int getIdNum();
public void setScore(double s);
public double getScore();
public void setAge(int n);
public int getAge();
}
public class Value_imp implements Value {
int idNum;
double score;
int age;
public Value_imp(int n, double s, int a) {
this.idNum=n; this.score=s; this.age=a;
}
@Override
public void setIdNum (int n) { this.idNum = n; }
@Override
public int getIdNum() { return idNum; }
@Override
public void setScore (double s) { this.score = s; }
@Override
public double getScore() { return score; }
@Override
public void setAge (int n) { this.age = n; }
@Override
public int getAge() { return age; }
}
package assignment2_f20;
//--------------------------------------------------------------
public class TreeMap_imp implements TreeMap {
TMCell root;
// add fields as you need to in order to provide the required behavior
// also you may add private methods to assist you as needed
// in implementing
//-------------------------------------------------------------
TreeMap_imp () {
root = null;
// for added fields you can add appropriate initialization code here
}
//-------------------------------------------------------------
// dont change, we need this for grading
@Override
public TMCell getRoot() { return this.root; }
//-------------------------------------------------------------
// "height" is a complete implementation
// of the public interface method height
// it is here to illustrate fr you how the textbook sets up
// the method implementation as recursion
// you may include this in your project directly
public int height() { // public interface method signature
// this method is the public interface method
// it is not recursive, but it calls a recursive
// private method and passes it access to the tree cells
return height_r(this.getRoot());
}
private int height_r(TMCell c) {
// inner method with different signature
// this helper method uses recursion to traverse
// and process the recursive structure of the tree of cells
if (c==null) return -1;
int lht = height_r(c.getLeft());
int rht = height_r(c.getRight());
return Math.max(lht,rht) + 1;
}
//-------------------------------------------------------------
// here down... you fill in the implementations for
// the other interface methods
//-------------------------------------------------------------
//
// remember to implement the required recursion as noted
// in the interface definition
//
//-------------------------------------------------------------
}
package assignment2_f20;
public class TreeMap_Playground {
/*
* you will test your own TreeMap implementation in here
*
* we will replace this with our own when grading, and will
* do what you should do in here... create TreeMap objects,
* put data into them, take data out, look for values stored
* in it, checking size, and looking at the TMCells to see if they
* are all linked up correctly as a BST
*
*/
public static void main(String[] args) {
// you should test your TreeMap implementation in here
// sample tests are shown
// it is up to you to test it thoroughly and make sure
// the methods behave as requested above in the interface
// do not simple depend on the oracle test we will give
// use the oracle tests as a way of checking AFTER you have done
// your own testing
// one thing you might find useful for debugging is a print tree method
// feel free to use the one we have here ... basic and quick, or write one
// you like better, one that shows you the tree structure more clearly
// the one we have here only shows keys, you may wish to add
// value fields to the printing
TreeMap tm = new TreeMap_imp();
Value v1 = new Value_imp(12345, 87.3, 21);
Value v2 = new Value_imp(23456, 75.54, 25);
Value v3 = new Value_imp(34567, 99.013, 19);
Value v4 = new Value_imp(45678, 55.70, 35);
tm.put("kappa", v1); tm.put("beta",v2);
tm.put("sigma",v3); tm.put("alpha",v4);
System.out.println(tm.get("sigma")); // assumes a toString for a Value onject
System.out.println(tm.hasKey("gamma"));
prTree(tm.getRoot(),0);
// etc...
}
public static void prTree (TMCell c, int off) {
if (c==null) return;
prTree(c.getRight(), off+2);
for (int i=0; i<off; i++) System.out.print(" ");
System.out.println(c.getKey());
prTree(c.getLeft(), off+2);
}
}
package assignment2_f20;
import gradingTools.comp410f20.assignment2.testcases.Assignment2Suite;
public class RunTests {
public static void main(String[] args){ //runs Assignment 2 oracle tests
Assignment2Suite.main(args);
}
}
Remember that just because the Oracle gives you 100%, you are not guaranteed any specific grade on the assignment. Testing your programs thoroughly is your responsibility; try to think of all the many edge cases and extremes for the data values possible. Think of degenerate structures, small structures, large ones... The main goal of the Oracle is to provide some direction. However, it is not the end-all be-all determiner of correctness. Please do not use this tool as a crutch.
TIPS: