CIS 256 (JAVA)

Familiarize yourself with the fields and methods of the BinaryTree and BinaryTreeNode classes. BinaryTree is an implementation of the Dictionary interface (which you also used in Homework 6) as a binary search tree. Note that BinaryTree uses Comparable objects as keys (since it is an ordered dictionary), whereas in the Dictionary abstract class, keys are declared as plain Objects. Thus you will occasionally need to cast Objects to Comparables.

Part I: Finding an Element in a Binary Search Tree (2 points) -------------------------------------------------------------- Complete the implementation of the find() method in dict/BinaryTree.java by filling in the body of findHelper(). find() takes a key as its single parameter, and returns an element associated with that key, or null if there is none. (If there are several elements associated with a key, it doesn't matter which one is returned.) findHelper() helps by recursively finding and returning a node that contains the key (or null if no such node exists).

Take a look at insertHelper() for inspiration. find() should run in O(d) time on a tree with depth d.

Part II: Removing an Element with a Given Key (2 points) --------------------------------------------------------- Fill in the body of remove() method in BinaryTree.java. remove() takes a key as its single parameter, and removes one item having that key if the tree contains one. (If there are several elements associated with a key, it doesn't matter which one is removed and returned.) remove() returns the same value that find() returns, but should not call find(). However, remove() SHOULD use the findHelper() method you wrote for Part I.

remove() should run in O(d) time if the depth of the tree is d.

Check-off --------- Show your TA or Lab Assistant the code you have written, and run the test program. You'll receive points for each part that runs correctly.

2 points: If find() works correctly. 1 point: If remove() works for nodes that have no child or one child. 1 point: If remove() works for nodes that have two children.

------------------------------------------------------------------

BinaryTree.java

/* BinaryTree.java */

package dict;

/** * BinaryTree implements a Dictionary as a binary tree (unbalanced). Multiple * entries with the same key are permitted. * * DO NOT CHANGE ANY PROTOTYPES IN THIS FILE. * * @author Jonathan Shewchuk **/ public class BinaryTree implements Dictionary {

/** * size is the number of items stored in the dictionary. * root is the BinaryTreeNode that serves as root of the tree. * If there are no items, size is zero and root is null. **/ protected int size; protected BinaryTreeNode root;

/** * Construct an empty binary tree. **/ public BinaryTree() { makeEmpty(); }

/** * makeEmpty() removes all the entries from the dictionary. */ public void makeEmpty() { size = 0; root = null; }

/** * size() returns the number of entries stored in the dictionary. * * @return the number of entries stored in the dictionary. **/ public int size() { return size; }

/** * isEmpty() tests if the dictionary is empty. * * @return true if the dictionary has no entries; false otherwise. **/ public boolean isEmpty() { return size == 0; }

/** * insert() constructs and inserts a new Entry object, consisting of * a (key, value) pair, into the dictionary, and returns a reference to the * new Entry. Multiple entries with the same key (or even the same key and * value) can coexist in the dictionary. * * @param key the key by which the entry can be retrieved. Must be of * a class that implements java.lang.Comparable. * @param value an arbitrary object associated with the key. * @return an Entry object referencing the key and value. **/ public Entry insert(Object key, Object value) { Entry entry = new Entry(key, value); if (root == null) { root = new BinaryTreeNode(entry); } else { insertHelper(entry, (Comparable) key, root); }

size++; return entry; }

/** * insertHelper() recursively does the work of inserting a new Entry object * into the dictionary. * * @param entry the Entry object to insert into the tree. * @param key the key by which the entry can be retrieved. * @param node the root of a subtree in which the new entry will be * inserted. **/ private void insertHelper(Entry entry, Comparable key, BinaryTreeNode node) { if (key.compareTo(node.entry.key()) <= 0) { if (node.leftChild == null) { node.leftChild = new BinaryTreeNode(entry, node); } else { insertHelper(entry, key, node.leftChild); } } else { if (node.rightChild == null) { node.rightChild = new BinaryTreeNode(entry, node); } else { insertHelper(entry, key, node.rightChild); } } }

/** * find() searches for an entry with the specified key. If such an entry is * found, it returns the Entry object; otherwise, it returns null. If more * than one entry has the key, one of them is chosen arbitrarily and * returned. * * @param key the search key. Must be of a class that implements * java.lang.Comparable. * @return an Entry referencing the key and an associated value, or null if * no entry contains the specified key. **/ public Entry find(Object key) { BinaryTreeNode node = findHelper((Comparable) key, root); if (node == null) { return null; } else { return node.entry; } }

/** * Search for a node with the specified key, starting from "node". If * a matching key is found (meaning that key1.compareTo(key2) == 0), return * a node containing that key. Otherwise, return null. * * Be sure this method returns null if node == null. **/

private BinaryTreeNode findHelper(Comparable key, BinaryTreeNode node) { // Replace the following line with your solution. return null; }

/** * remove() searches for an entry with the specified key. If such an entry * is found, it removes the Entry object from the Dictionary and returns it; * otherwise, it returns null. If more than one entry has the key, one of * them is chosen arbitrarily, removed, and returned. * * @param key the search key. Must be of a class that implements * java.lang.Comparable. * @return an Entry referencing the key and an associated value, or null if * no entry contains the specified key. **/ public Entry remove(Object key) { // Replace the following line with your solution. return null; }

/** * Convert the tree into a string. **/

public String toString() { if (root == null) { return ""; } else { return root.toString(); } }

/* Tests the binary search tree. */ public static void main(String[] args) { BinaryTree tree = new BinaryTree();

System.out.println("Inserting 1A, 6V, 3K, 2Z, 5L, 9L:"); tree.insert(new Integer(1), "A"); tree.insert(new Integer(6), "V"); tree.insert(new Integer(3), "K"); tree.insert(new Integer(2), "Z"); tree.insert(new Integer(5), "L"); tree.insert(new Integer(9), "L"); System.out.println("The tree is: " + tree); System.out.println("Size: " + tree.size());

System.out.println(" Testing find() ..."); tree.testFind(1, "A"); tree.testFind(9, "L"); tree.testFind(5, "L"); tree.testFind(4, null); tree.testFind(6, "V"); tree.testFind(3, "K");

System.out.println(" Testing remove() (for nodes with < 2 children) ..."); tree.testRemove(5, "1A(((2Z)3K)6V(9L))"); tree.testRemove(3, "1A((2Z)6V(9L))"); tree.testRemove(1, "(2Z)6V(9L)"); tree.insert(new Integer(7), "S"); tree.insert(new Integer(8), "X"); tree.insert(new Integer(10), "B"); System.out.println("After inserting 7S, 8X, 10B: " + tree); System.out.println("Size: " + tree.size()); if (tree.size() != 6) { System.out.println(" SHOULD BE 6."); }

System.out.println(" Testing remove() (for nodes with 2 children) ..."); tree.testRemove(6, "(2Z)7S((8X)9L(10B))"); tree.testRemove(9, "(2Z)7S((8X)10B)"); System.out.println("Size: " + tree.size()); if (tree.size() != 4) { System.out.println(" SHOULD BE 4."); } }

private void testRemove(int n, String shouldBe) { Integer key = new Integer(n); System.out.print("After remove(" + n + "): "); remove(key); System.out.println(this); if (!toString().equals(shouldBe)) { System.out.println(" SHOULD BE " + shouldBe); } }

private void testFind(int n, Object truth) { Integer key = new Integer(n); Entry entry = find(key); System.out.println("Calling find() on " + n); if (entry == null) { System.out.println(" returned null."); if (truth != null) { System.out.println(" SHOULD BE " + truth + "."); } } else { System.out.println(" returned " + entry.value() + "."); if (!entry.value().equals(truth)) { if (truth == null) { System.out.println(" SHOULD BE null."); } else { System.out.println(" SHOULD BE " + truth + "."); } } } } }

------------------------------------------------------------------------------------------------------------------

/* BinaryTreeNode.java */

package dict;

/** * BinaryTreeNode represents a node in a binary tree. * * DO NOT CHANGE THIS FILE. **/ class BinaryTreeNode {

/** * entry is a (key, value) pair stored in this node. * parent is the parent of this node. * leftChild and rightChild are the children of this node. **/ Entry entry; BinaryTreeNode parent; BinaryTreeNode leftChild, rightChild;

/** * Construct a BinaryTreeNode with a specified entry; parent and children * are null. **/ BinaryTreeNode(Entry entry) { this(entry, null, null, null); }

/** * Construct a BinaryTreeNode with a specified entry and parent; children * are null. **/ BinaryTreeNode(Entry entry, BinaryTreeNode parent) { this(entry, parent, null, null); }

/** * Construct a BinaryTreeNode, specifying all four fields. **/ BinaryTreeNode(Entry entry, BinaryTreeNode parent, BinaryTreeNode left, BinaryTreeNode right) { this.entry = entry; this.parent = parent; leftChild = left; rightChild = right; }

/** * Express a BinaryTreeNode as a String. * * @return a String representing the BinaryTreeNode. **/ public String toString() { String s = "";

if (leftChild != null) { s = "(" + leftChild.toString() + ")"; } s = s + entry.key().toString() + entry.value(); if (rightChild != null) { s = s + "(" + rightChild.toString() + ")"; } return s; } }

------------------------------------------------------------------------------------------------------------

/* Dictionary.java */

package dict;

/** * An interface for (unordered) dictionary ADTs. * * DO NOT CHANGE THIS FILE. **/

public interface Dictionary {

/** * Returns the number of entries stored in the dictionary. Entries with * the same key (or even the same key and value) each still count as * a separate entry. * @return number of entries in the dictionary. **/

public int size();

/** * Tests if the dictionary is empty. * * @return true if the dictionary has no entries; false otherwise. **/

public boolean isEmpty();

/** * Create a new Entry object referencing the input key and associated value, * and insert the entry into the dictionary. Return a reference to the new * entry. Multiple entries with the same key (or even the same key and * value) can coexist in the dictionary. * * @param key the key by which the entry can be retrieved. * @param value an arbitrary object. * @return an entry containing the key and value. **/

public Entry insert(Object key, Object value);

/** * Search for an entry with the specified key. If such an entry is found, * return it; otherwise return null. If several entries have the specified * key, choose one arbitrarily and return it. * * @param key the search key. * @return an entry containing the key and an associated value, or null if * no entry contains the specified key. **/

public Entry find(Object key);

/** * Remove an entry with the specified key. If such an entry is found, * remove it from the table and return it; otherwise return null. * If several entries have the specified key, choose one arbitrarily, then * remove and return it. * * @param key the search key. * @return an entry containing the key and an associated value, or null if * no entry contains the specified key. */

public Entry remove(Object key);

/** * Remove all entries from the dictionary. */

public void makeEmpty();

}

----------------------------------------------------------------------------

/* Dictionary.java */

package dict;

/** * An interface for (unordered) dictionary ADTs. * * DO NOT CHANGE THIS FILE. **/

public interface Dictionary {

/** * Returns the number of entries stored in the dictionary. Entries with * the same key (or even the same key and value) each still count as * a separate entry. * @return number of entries in the dictionary. **/

public int size();

/** * Tests if the dictionary is empty. * * @return true if the dictionary has no entries; false otherwise. **/

public boolean isEmpty();

/** * Create a new Entry object referencing the input key and associated value, * and insert the entry into the dictionary. Return a reference to the new * entry. Multiple entries with the same key (or even the same key and * value) can coexist in the dictionary. * * @param key the key by which the entry can be retrieved. * @param value an arbitrary object. * @return an entry containing the key and value. **/

public Entry insert(Object key, Object value);

/** * Search for an entry with the specified key. If such an entry is found, * return it; otherwise return null. If several entries have the specified * key, choose one arbitrarily and return it. * * @param key the search key. * @return an entry containing the key and an associated value, or null if * no entry contains the specified key. **/

public Entry find(Object key);

/** * Remove an entry with the specified key. If such an entry is found, * remove it from the table and return it; otherwise return null. * If several entries have the specified key, choose one arbitrarily, then * remove and return it. * * @param key the search key. * @return an entry containing the key and an associated value, or null if * no entry contains the specified key. */

public Entry remove(Object key);

/** * Remove all entries from the dictionary. */

public void makeEmpty();

}

------------------------------------------------------------------------------------------------------

/* Entry.java */

package dict;

/** * A class for dictionary entries, which are (key, value) pairs. * * DO NOT CHANGE THIS FILE. It is part of the interface of the Dictionary * ADT. **/

public class Entry {

protected Object key; protected Object value;

protected Entry() { }

protected Entry(Object k, Object v) { key = k; value = v; }

public Object key() { return key; }

public Object value() { return value; } }