Question
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
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.
Code: BSTSet.java
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; } } Code: BSTSetTest.java import java.util.Arrays; import java.util.Objects; import org.junit.Test; import static org.junit.Assert.*; public class BSTSetTest { public BSTSetTest() { } @Test public void testSize() { BSTSet t.add(10); assertEquals(1, t.size); t.add(20); assertEquals(2, t.size); } @Test public void testContainsA() { // PART 1 BSTSet assertFalse(true); } @Test public void testContainsB() { // PART 1 BSTSet assertFalse(true); } @Test public void testContainsC() { // PART 1 BSTSet assertFalse(true); } // Feel free to write more contains tests! @Test public void testDeleteMinLeaf() { BSTSet n.add(30); n.add(20); n.add(50); n.deleteMin(n.root.right); Integer[] ex = {30, 20}; assertEquals(BSTSet.bulkInsert(ex).root, n.root); } @Test public void testDeleteMinLeftShallow() { BSTSet n.add(30); n.add(20); n.add(50); n.add(49); n.deleteMin(n.root.right); Integer[] ex = {30, 20, 50}; assertEquals(BSTSet.bulkInsert(ex).root, n.root); } @Test public void testDeleteMinLeftShallow2() { BSTSet n.add(30); n.add(20); n.add(50); n.add(49); n.add(51); n.deleteMin(n.root.right); Integer[] ex = {30, 20, 50, 51}; assertEquals(n.root, BSTSet.bulkInsert(ex).root); } @Test public void testDeleteMinLeftDeep() { BSTSet n.add(30); n.add(20); n.add(50); n.add(40); n.add(60); n.add(35); n.add(45); n.deleteMin(n.root.right); Integer[] ex = {30, 20, 50, 40, 60, 45}; assertEquals(n.root, BSTSet.bulkInsert(ex).root); } @Test public void testRemoveRoot1() { BSTSet t.add(44); assertTrue(t.remove(44)); assertTrue(t.isEmpty()); } @Test public void testRemoveRoot2() { BSTSet t.add(50); assertFalse(t.remove(25)); assertTrue(t.remove(50)); assertTrue(t.isEmpty()); } @Test public void testRemoveRoot3() { BSTSet t.add(50); t.add(25); t.add(75); assertTrue(t.remove(50)); assertTrue(t.root.data==25 || t.root.data==75); t.root.checkIsBST(); } @Test public void testRemoveComplex() { BSTSet t.add(44); t.add(17); t.add(62); t.add(32); t.add(50); t.add(78); t.add(48); t.add(54); t.add(88); assertTrue(t.remove(32)); assertFalse(t.remove(32)); t.root.checkIsBST(); Integer[] ex = {44,17,62,50,78,48,54,88}; assertEquals(BSTSet.bulkInsert(ex).root, t.root); } @Test public void testRemoveComplex2() { BSTSet t.add(100); t.add(50); t.add(200); t.add(30); t.add(75); t.add(150); t.add(250); t.add(60); t.add(125); t.add(175); t.add(300); t.add(160); t.root.checkIsBST(); t.root.printTree(); assertTrue(t.remove(300)); t.root.printTree(); t.root.checkIsBST(); Integer[] ex = {100,50,200,30,75,150,250,60,125,175,160}; assertEquals(BSTSet.bulkInsert(ex).root, t.root); } @Test public void testRemoveComplex3() { BSTSet t.add(100); t.add(50); t.add(200); t.add(30); t.add(75); t.add(150); t.add(250); t.add(60); t.add(125); t.add(175); t.add(300); t.add(160); t.add(155); t.add(165); t.root.checkIsBST(); t.root.printTree(); assertTrue(t.remove(150)); t.root.printTree(); t.root.checkIsBST(); Integer[] ex = {100,50,200,30,75,155,250,60,125,175,300,160,165}; assertEquals(BSTSet.bulkInsert(ex).root, t.root); } @Test public void testInsert() { BSTSet n.add(13); n.add(20); n.add(25); n.add(3); Integer[] ex = {13,20,3,25}; assertEquals(n.root, BSTSet.bulkInsert(ex).root); } private // use a Java SortedSet to check ours java.util.SortedSet exp.addAll(Arrays.asList(input)); java.util.SortedSet expSubset = exp.subSet(fromKey, toKey); // insert into our Set and take subset BSTSet NavigableSet // our Set should contain and not contain all the same elements // as the Java Set for (int i=0; i assertEquals(expSubset.contains(input[i]), subt.contains(input[i])); } } @Test public void testSubSet() { Integer[] input = {100,50,150,25,75,125,175,60,79}; subsetHelper(input, 54, 127); } @Test public void testSubSet2() { Integer[] input = {100,50,150,25,75,125,175,60,79}; subsetHelper(input, 50, 100); } @Test public void testSubSet3() { String[] input = {"kangaroo","bass","leopard","albatross","goat","lemur","mouse","cat","gorilla"}; subsetHelper(input, "kangaroo", "penguin"); } @Test public void testSubSet4() { // PART 2 assertFalse(true); } @Test public void testSubSetOutOfBounds() { // PART 2 assertFalse(true); } @Test public void testGenericity() { AVLTreeSet t.add("Dog"); assertFalse(t.contains("Cat")); assertTrue(t.contains("Dog")); AVLTreeSet s.add(new StringWrapper("Dog")); assertFalse(s.contains(new StringWrapper("Cat"))); assertTrue(s.contains(new StringWrapper("Dog"))); } private class StringWrapper implements Comparable @Override public boolean equals(Object obj) { if (this == obj) { return true; } if (obj == null) { return false; } if (getClass() != obj.getClass()) { return false; } final StringWrapper other = (StringWrapper) obj; if (!Objects.equals(this.s, other.s)) { return false; } return true; } private final String s; public StringWrapper(String s) { this.s = s; } @Override public int compareTo(StringWrapper o) { return this.s.compareTo(o.s); } } }
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