Question
package CSC301SP18Homework; // change the package if you want import stdlib.StdOut; /** * Version 1.0 * * This homework is worth 24 points; it has
package CSC301SP18Homework; // change the package if you want
import stdlib.StdOut;
/**
* Version 1.0
*
* This homework is worth 24 points; it has two credit level options.
* Option 1: complete ToDos 0-4 20/24 points
* Option 2: complete ToDos 0-5 24/24 points
*
* effectively, option 1 has a maximum grade of B.
* To get a 100% score on the assignment you must complete option 2
*
* You must not change the declaration of any method.
* You must not change the Node class declaration
* You may not add instance variables
* You may not use any other java classes/algorithms without permission
*
* You may create helper functions for Todo's 3, 4, and 5
*
*/
/**
* The B(inary)S(earch)T(ree) class represents a symbol table of
* generic key-value pairs. It supports put, get, and delete methods.
* The book's recursive versions of get and put have been renamed
* rGet and rPut
* to facilitate testing of your non-recursive versions
*
*/
public class BST301
private Node root; // root of BST
static boolean verbose = false; // set to false to mute "correct" test output messages
private class Node {
private Key key; // key
private Value val; // associated data
private Node left, right; // left and right subtrees
public Node(Key key, Value val) {
this.key = key;
this.val = val;
}
/**
* Appends the preorder string representation of the sub-tree to the given StringBuilder.
*/
public void buildString(StringBuilder s) {
s.append(left == null ? '[' : '(');
s.append(key + "," + val);
s.append(right == null ? ']' : ')');
if (left != null) left.buildString(s);
if (right != null) right.buildString(s);
}
}
/**
* Returns the preorder string representation of the BST.
*/
public String toString() {
StringBuilder s = new StringBuilder();
root.buildString(s);
return s.toString();
}
/**
* Initializes an empty symbol table.
*/
public BST301() {
}
/** size
*
* return the size of the tree
*/
public int size() {
return -1; // ToDo 0
}
/** get
*
* Returns the value associated with the given key.
* Returns null if the key is not in the table
*
* ToDo 1 write a non-recursive implementation of get
*
*/
public Value get(Key key) {
return null; //Todo 1
}
/** put
* Inserts the specified key-value pair into the symbol table, overwriting the old
* value with the new value if the symbol table already contains the specified key.
*
* ToDo 2 write a non-recursive implementation of put
*/
public void put(Key key, Value val) {
return; // ToDo 2
}
/** numLeaves
*
* Returns the number of leaf nodes in the tree
* A leaf is a node with 0 children
*
* ToDo 3
*/
public int numLeaves() {
return -1; // ToDo 3
}
/** lengthOfShortestPathToNull
*
* Returns the length of the shortest path (in edges) from root to a node with a null left or right subtree
*
* ToDo 4
*/
public int lengthOfShortestPathToNull() {
return -1; // ToDo 4
}
/**
*
* delete
*
* deletes the key (&value) from the table if the key is present
* using the the *dual* of the Hibbard approach from the text. That is,
* for the two-child scenario, delete the node by replacing it
* with it's predecessor (instead of its successor)
*
* The functions: max, deleteMax have been provided for you
*
* ToDo 5: implement a version of delete meeting the above spec
*
* if you complete this toDo, comment out or delete the print statement, otherwise leave it in.
*
*/
public void delete(Key key) {
StdOut.println(" delete not implemented ");
return; // ToDo 5
}
/** max
*
* return the node in the subtree x with the maximum key ( right most node)
*/
private Node max(Node x) {
if ( x.right == null) return x;
return max(x.right);
}
/** deleteMax
*
* return the subtree x with the node with maximum key deleted
*/
private Node deleteMax(Node x) {
if ( x.right == null) return x.left;
x.right = deleteMax(x.right);
return x;
}
/*****************************************************
*
* Utility functions
*/
public Value rGet(Key key) {
return rGet(root, key);
}
private Value rGet(Node x, Key key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) return rGet(x.left, key);
else if (cmp > 0) return rGet(x.right, key);
else return x.val;
}
public void rPut(Key key, Value val) {
if (key == null) throw new NullPointerException("first argument to put() is null");
root = rPut(root, key, val);
}
private Node rPut(Node x, Key key, Value val) {
if (x == null) return new Node(key, val);
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = rPut(x.left, key, val);
else if (cmp > 0) x.right = rPut(x.right, key, val);
else x.val = val;
return x;
}
/* main calls all the testing functions */
public static void main(String[] args)
{
// comment in/out calls to focus on a given ToDo method
sizeTests();
numLeavesTests();
lenShortestPathToNullTests();
getTests();
putTests();
deleteTests();
}
/* sizeTests
*
* parameters to sizeTest
* 1: String of keys to add to symbol table in order left-to-right
* 2: expected tree size
*/
public static void sizeTests() {
sizeTest("", 0); // test size on an empty symbol table
sizeTest("a",1); // test size on a symbol table of size 1
sizeTest("aaaaaa", 1); // test size on a symbol table of size 1
sizeTest("ababcd", 4); // test size on a symbol table of size > 1
sizeTest("abcde", 5); // test size on a symbol table of size > 1
StdOut.println("----------- size tests completed");
}
/* numLeavesTests
*
parameters to testNumLeaves
* 1: String of keys to add to symbol table in order left-to-right
* 2: expected result
*/
public static void numLeavesTests() {
testNumLeaves("",0);
testNumLeaves("HCADMLZ",4); // leaves are ADLZ
testNumLeaves("ABCDEFG",1); // leaves: G
testNumLeaves("GFEDCBA",1); // leaves: A
testNumLeaves("MABC",1); // leaves: C
testNumLeaves("MGLJK",1); // leaves: F
testNumLeaves("CBADE",2); // leaves: A, E
StdOut.println("----------- numLeaves tests completed");
}
/* lenShortestPathToNullTests
*
parameters to testLengthOfShortestPathToNull
* 1: String of keys to add to symbol table in order left-to-right
* 2: expected result
*/
public static void lenShortestPathToNullTests() {
testLengthOfShortestPathToNull("C",0);
testLengthOfShortestPathToNull("CA",0);
testLengthOfShortestPathToNull("CAD",1); // complete BT with 3 nodes
testLengthOfShortestPathToNull("HCADMLZ",2); // complete BT with 7 nodes
testLengthOfShortestPathToNull("HCADMJZGL",2); // complete BT(7) w/ two extra nodes
StdOut.println("----------- lenShortestPathToNull tests completed");
}
/* getTests
*
parameters to testGet
* 1: String of keys to add to symbol table in order left-to-right
* 2: String of vals corresponding to above keys
* 3: key to 'get'
* 4: expected value "" means null is expected
*/
public static void getTests() {
testGet("C","3","C","3"); // ST (C,3), get C. result 3
testGet("C","3","D",""); // ST (C,3), get D. result null
testGet("CBADE","32145","C","3"); // C in table
testGet("CBADE","32145","A","1"); // A in table
testGet("CBADE","32145","E","5"); // E in table
testGet("HCADMLZ","1245367","A","4"); // A in table
testGet("HCADMLZ","1245367","D","5"); // D in table
testGet("HCADMLZ","1245367","Z","7"); // A in table
testGet("HCADMLZ","1245367","B",""); // B not in table
testGet("HCADMLZ","1245367","Y",""); // Y not in table
testGet("ABCDEFG","1234567","A","1"); // A in table
testGet("MGLJK","12345","G","2"); // G in table
testGet("MGLJK","12345","Z",""); // Z not in table
StdOut.println("----------- get tests completed");
}
/* putTests
*
parameters to testPut
* 1: String of keys to add to a symbol table in order left-to-right
* 2: String of vals corresponding to above keys
* 3,4: key,value to 'put'
* 5,6: String of keys,values expected in resulting table in order left-to-right
*/
public static void putTests() {
testPut("CA","31","C","3","CA","31"); // put existing key-val pair, no change
testPut("HCADMJZGL","123456789","L","9","HCADMJZGL","123456789"); // put existing key-val pair, no change
testPut("HCADMJZGL","123456789","L","0","HCADMJZGL","123456780"); // update value in Leaf
testPut("HCADMJZGL","123456789","C","0","HCADMJZGL","103456789"); // update value in middle
testPut("HCADMJZGL","123456789","B","0","HCABDMJZGL","1230456789"); // Add new kv in middle
testPut("ABCEFG","123567","D","4","ABCEDFG","1235467"); // straight line right, add new kv in middle
StdOut.println("----------- put tests completed");
}
/* deleteTests
*
parameters to testDelete
* 1: String of keys to add to a symbol table in order left-to-right
* 2: String of vals corresponding to above keys
* 3: key to be deleted
* 4,5: String of keys,values expected in resulting table in order left-to-right
*/
public static void deleteTests() {
testDelete("CA","31","C","A","1");
testDelete("CAD","314","D","CA","31");
testDelete("ABCDEFG","1234567","G","ABCDEF","123456"); // straight line right
testDelete("ABCDEFG","1234567","D","ABCEFG","123567"); // straight line right
testDelete("GFEDCBA","7654321","A","GFEDCB","765432"); // straight line left
testDelete("GFEDCBA","7654321","D","GFECBA","765321"); // straight line left
testDelete("HCADMJZ","1234567", "H", "DCAMJZ","423567"); // delete root
testDelete("HCADMJZGL","123456789", "M", "HCADLJZG","12349678"); // delete M
testDelete("MJALBCD","1234567","J", "MDALBC","173456"); // delete J
StdOut.println("----------- delete tests completed");
}
/* from
* builds a BST using the author's version of put
*/
public static BST301
if ( keys.length() != vals.length())
throw new IllegalArgumentException("array sizes do not match");
BST301
for (int i=0; i < keys.length(); i++) {
abst.rPut(keys.substring(i, i+1),vals.substring(i,i+1));
}
return abst;
}
/******************************************* testing functions *******************************/
// test size function.
// param keys: all substrings of length 1 are added to the ST
// param expected: the correct value of the ST for the input:vals
public static void sizeTest( String keys, int expected ) {
// create and populate the table from the input string keys
BST301
// do the test
int actual = aTree.size();
//report result
if ( actual == expected) { // test passes
if (verbose)
StdOut.format("sizeTest: Correct String [ %s ] Answer: %d ", keys, actual);
}
else
StdOut.format("sizeTest: *Error* String [ %s ] expected: %d actual: %d ", keys, expected, actual);
}
public static void testNumLeaves( String keys, int expected ) {
// create and populate the table from the input string
BST301
// do the test
int actual = aTree.numLeaves();
if ( actual == expected) {// test passes
if (verbose)
StdOut.format("testNumLeaves: Correct Keys: [ %s ] actual: %d ", keys, actual);
}
else
StdOut.format("testNumLeaves: *Error* Keys: [ %s ] expected: %d actual: %d ", keys, expected, actual);
}
public static void testLengthOfShortestPathToNull( String keys, int expected ) {
// create and populate the table from the input string
BST301
// do the test
int actual = aTree.lengthOfShortestPathToNull();
if ( actual == expected) {// test passes
if (verbose)
StdOut.format("test lenShortestPathToNull: Correct Keys: [ %s ] actual: %d ", keys, actual);
}else
StdOut.format("test lenShortestPathToNull: *Error* Keys: [ %s ] expected: %d actual: %d ", keys, expected, actual);
}
public static void testGet( String keys, String vals, String key, String expected ) {
// create and populate the table from the input string
BST301
// do the test
String actual = aTree.get(key);
if ( (expected.equals("") && actual == null) || (expected.equals(actual))) { // test passes
if ( verbose)
StdOut.format("testGet: Correct Keys:[ %s ] Vals:[%s] Get:%s actual: %s ",
keys, vals, key, actual);
}
else
StdOut.format("testGet: *Error* Keys:[ %s ] Vals:[%s] Get:%s expected: %s actual: %s ",
keys, vals, key, expected, actual);
}
// keys, vals are the data for the starting ST
// pKey, pVal is the key-value pair to insert
// exKeys, exVals are the data for the expected ST after the put
// this does not test for inserting a null value
public static void testPut( String keys, String vals, String pKey,
String pVal,String exKeys, String exVals ) {
// create and populate the table from the input string
BST301
BST301
// do the test
testTree.put(pKey,pVal);
String actual = testTree.toString();
String expected = expectedTree.toString();
if ( actual.equals(expected) ) { // test passes
if (verbose)
StdOut.format("testPut: Correct Keys:[%s] Vals:[%s] Put:(%s,%s) Result: %s ",
keys, vals, pKey, pVal, actual);
} else
StdOut.format("testPut: *Error* Keys:[%s] Vals:[%s] Put:(%s,%s) Result: %s ",
keys, vals, pKey, pVal, actual);
}
public static void testDelete( String keys, String vals, String key, String exKeys, String exVals ) {
// create and populate the table from the input string
BST301
BST301
// do the test
testTree.delete(key);
String actual = testTree.toString();
String expected = expectedTree.toString();
if ( actual.equals(expected) ) { // test passes
if (verbose)
StdOut.format("testDelete: Correct Keys:[ %s ] Vals:[%s] Delete:%s Result: %s ",
keys, vals, key, actual);
}else
StdOut.format("testDelete: *Error* Keys:[ %s ] Vals:[%s] Delete:%s Result: %s ",
keys, vals, key, actual);
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
Database 101
Authors: Guy Kawasaki
1st Edition
0938151525, 978-0938151524
