Question: //Part 1: Contains method The Set.contains method returns true if and only if the element exists in the Set. a) The BSTSetTest.java file has test
//Part 1: Contains method The Set.contains method returns true if and only if the element exists in the Set. a) The BSTSetTest.java file has test cases for BSTSet. Devise three different tests for the contains method (put them in testContainsA,B, and C) so that you are confident that contains() works. Your tests for this part should be "black box", that is, they don't depend on the implementation: they only call public methods of BSTSet (in this case, the constructor, add(), and contains()). Your 3 tests need to be different: that is, your add methods should be such that they cause different underlying tree structures and there should be cases where contains() returns each true and false. b) Implement the BSTSet.contains method. Part 2: A method for NavigableSet Take a look at the NavigableSet interface. It adds a new method subSet to the methods already provided by Set. The subSet method requires that keys stored in the NavigableSet have a total order. 6 3 2 4 Therefore, you'll see that the generic type is constrained to be a Comparable. The Comparable interface provides the compareTo method. public interface NavigableSet> extends Set Read the Java 8 API on Comparable https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html to see what compareTo does. a) BSTSet implements the NavigableSet interface, so you need to provide an implementation of subSet. NavigableSet subSet(T fromKey, T toKey) that returns a new NavigableSet that contains all elements ?, such that ??????? ? ? < ?????. Your method must be efficient. That is, your algorithm should find fromKey quickly and once it finds toKey (or larger key) it should not look at any other nodes. For a balanced tree, your implementation should be faster than linear in N, where N is the size of the original Set, assuming that S << N, where S is the size of the subset. An implementation that visits entire subtrees that are not in range [start, end) is probably O(N). An example of an O(N) algorithm would be: 1) perform an inorder traversal of the whole tree, inserting nodes into a List, then 2) iterate over the list to remove the elements not between start and end. The following tests in BSTSetTest.java are relevant to this method: testSubSet1,2,3. b) You must write at least two more tests. testSubSet4: It must test a different tree structure and range than the other 3 tests. testSubSetOutOfBounds: Test a situation where the original Set has elements but the subset is the empty Set. Tips The subMap method in Goodrich chapter 11.3 is a similar method to subSet. You'll probably need one or more private helper methods and/or inner classes. There are three basic approaches we can think of: o Build a whole List of keys that are in-range using recursion then add the elements to a new BSTSet. o Same as above but skip the List; add directly to the BSTSet as you find them o Define an inner class that implements Iterator. It keeps a frontier (e.g., a Stack) to do the traversal. Advance the traversal after each call to next(). HINT: a preorder traversal requires seeing each node twice (once before visiting left and once after) so may want to mark nodes as "visited" or not. Call this iterator's next() in a loop, adding elements to a new BSTSet. Part 3: remove elements from an unbalanced BST The Set.remove method removes the element if it exists in the Set and returns true if the element was found. Part 3a: deleteMin The BSTSet.remove method will depend on the BSTSet.deleteMin method. This method takes a TreeNode n and removes the minimum element in the subtree rooted at n. Tips: The two if-statement lines of deleteMin are "pre conditions". Leave them there! They will help with debugging To perform the deletion you should use the method updateParent. It will greatly simplify your implementation because it works whether you are changing the left or right child. We've provided tests in BSTSetTest (called testDeleteMin*) to help you ensure deleteMin is correct before proceeding to the remove method. Part 3b: remove Implement the BSTSet.remove method. Recall that there are four cases for removal in a BST: a) removed node is a leaf b) removed node has only a left child c) removed node has only a right child d) removed node has two children Case d is the tricky one. Use the following algorithm, adapted from your textbook: 1) use deleteMin to delete the smallest element in right subtree 2) use the data of the node returned by deleteMin to overwrite the data in the "removed" node. Take the time with some examples on paper (the remove test cases in BSTSetTest.java are one good source of examples) to convince yourself why the above algorithm works. There are several tests called testRemove* in BSTSetTest to help you debug.//
import java.util.*;
public class BSTSet
// the root of the tree
protected TreeNode
// number of TreeNodes in the tree
public int size;
public BSTSet() {
root = null;
size = 0;
}
/*
Insert the element d into the Binary Search Tree
*/
@Override
public void add(T e) {
insert(root, e);
}
/* Creates a BST from the given array. To get the BST that you
expect, the order of the data should be breadth-first order of the resulting tree
e.g. The tree
100
50 200
60 110 203
would be achieved by passing in
{100,50,200,60,110,203}
*/
protected static
BSTSet
for (int i=0; i b.insert(b.root, data[i]); } return b; } private void insert(TreeNode if (root == null) { root = new TreeNode<>(data); size++; return; } else { if (current.data.compareTo(data) == 0) { return; //the same object is alread stored in the tree, so exit without inserting a a duplicate } if (current.data.compareTo(data) > 0 && current.left != null) { insert(current.left, data); } else if (current.data.compareTo(data) < 0 && current.right != null) { insert(current.right, data); } else if (current.data.compareTo(data) > 0 && current.left == null) { current.left = new TreeNode<>(data); size++; } else { current.right = new TreeNode<>(data); size++; } } } @Override public boolean contains(T e) { // PART 1 return false; } @Override public NavigableSet // PART 2 return null; } /* remove the minimum TreeNode from the tree rooted at n. Return the removed TreeNode. Make sure that the parent of n is updated if n is the node removed. */ protected TreeNode TreeNode // do not remove these two lines. They are intended to help you debug by // checking pre-conditions on deleteMin if (parentOfN == null) throw new IllegalArgumentException("deleteMin should not be called on a null parent"); if (parentOfN.isLeaf()) throw new IllegalArgumentException("deleteMin should not be called with a parent that is a leaf"); // PART 3 return null; } @Override public boolean remove(T e) { // PART 3 return false; } /* Takes the existing child of the parent to replace with the new child null is a valid argument for newChild but not oldChild example: BEFORE parent \ oldChild AFTER parent \ newChild example: BEFORE parent / oldChild AFTER parent / newChild */ protected void updateParent(TreeNode TreeNode if (parent == null) { root = newChild; return; } if (oldChild.data.compareTo(parent.data) > 0) parent.right = newChild; else if (oldChild.data.compareTo(parent.data) < 0) { parent.left = newChild; } else { throw new IllegalStateException("duplicate elements in tree"); } } protected TreeNode if (child == null) throw new IllegalArgumentException("child should not be null"); // put the special case for child is root here so that // we can use the == case to check for errors in the helper method if (child.data.compareTo(root.data) == 0) return null; return getParentHelper(root, child); } private TreeNode if (child.data.compareTo(current.data) < 0) { if (child.data.compareTo(current.left.data) == 0) { // found the child, so current is its parent return current; } else { return getParentHelper(current.left, child); } } else if (child.data.compareTo(current.data) > 0) { if (child.data.compareTo(current.right.data) == 0) { // found the child, so current is its parent return current; } else { return getParentHelper(current.right, child); } } else { throw new IllegalArgumentException("child is not in the tree"); } } protected static int getHeight(TreeNode current) { if (current == null) { return 0; } return current.height; } public void updateHeightWholeTree() { updateHeightWholeTreeHelper(root); } private void updateHeightWholeTreeHelper(TreeNode current) { if (current==null) return; if (current.left!=null) updateHeightWholeTreeHelper(current.left); if (current.right!=null) updateHeightWholeTreeHelper(current.right); current.height = Math.max(getHeight(current.right), getHeight(current.left)) + 1; } /* Update the height attribute of all TreeNodes on the path to the data */ public void updateHeight(T data) { if (root != null) { updateHeightHelper(root, data); } } private void updateHeightHelper(TreeNode current, T data) { if (current.data.compareTo(data) != 0) { if (current.data.compareTo(data) > 0 && current.left != null) { updateHeightHelper(current.left, data); } else if (current.data.compareTo(data) < 0 && current.right != null) { updateHeightHelper(current.right, data); } } if (getHeight(current.right) == 0 && getHeight(current.left) == 0) { current.height = 1; } else { current.height = Math.max(getHeight(current.right), getHeight(current.left)) + 1; } } protected static boolean isBalanced(TreeNode current) { return ((Math.abs(getHeight(current.right) - getHeight(current.left)) < 2)); } //////////////// Dont edit after here ////////////////////// public boolean isEmpty() { return (root == null); } public void inorder() { inorder(root); } private void inorder(TreeNode current) { if (current == null) { return; } inorder(current.left); System.out.println(" " + current.data); inorder(current.right); } public void displayTree() { Stack globalStack.push(root); int emptyLeaf = 32; boolean isRowEmpty = false; System.out.println("****..................................................................................................................................****"); while (isRowEmpty == false) { Stack isRowEmpty = true; for (int j = 0; j < emptyLeaf; j++) { System.out.print(" "); } while (globalStack.isEmpty() == false) { TreeNode temp = globalStack.pop(); if (temp != null) { System.out.print(temp.data); localStack.push(temp.left); localStack.push(temp.right); if (temp.left != null || temp.right != null) { isRowEmpty = false; } } else { System.out.print("--"); localStack.push(null); localStack.push(null); } for (int j = 0; j < emptyLeaf * 2 - 2; j++) { System.out.print(" "); } } System.out.println(); emptyLeaf /= 2; while (localStack.isEmpty() == false) { globalStack.push(localStack.pop()); } } System.out.println("****..................................................................................................................................****"); } public Object[] toArray() { Object[] r = new Object[size]; if (root == null) { return r; } // traverse the tree to visit all nodes, // adding them to r List frontier.add(root); int soFar = 0; while (frontier.size() > 0) { TreeNode v = (TreeNode) frontier.get(0); r[soFar] = v.data; soFar++; if (v.left != null) { frontier.add(v.left); } if (v.right != null) { frontier.add(v.right); } frontier.remove(0); } return r; } }
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help