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> implements NavigableSet {

// the root of the tree

protected TreeNode root;

// 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 bulkInsert(E[] data) {

BSTSet b = new BSTSet<>();

for (int i=0; i

b.insert(b.root, data[i]);

}

return b;

}

private void insert(TreeNode current, T data) {

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 subSet(T fromKey, T toKey) {

// 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 deleteMin(TreeNode n) {

TreeNode parentOfN = null; // you'll need this variable

// 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 oldChild, TreeNode newChild) {

TreeNode parent = getParent(oldChild);

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 getParent(TreeNode child) {

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 getParentHelper(TreeNode current, TreeNode child) {

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 = new Stack<>();

globalStack.push(root);

int emptyLeaf = 32;

boolean isRowEmpty = false;

System.out.println("****..................................................................................................................................****");

while (isRowEmpty == false) {

Stack localStack = new 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 = new LinkedList<>();

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 = new BSTSet<>();

t.add(10);

assertEquals(1, t.size);

t.add(20);

assertEquals(2, t.size);

}

@Test

public void testContainsA() {

// PART 1

BSTSet t = new BSTSet<>();

assertFalse(true);

}

@Test

public void testContainsB() {

// PART 1

BSTSet t = new BSTSet<>();

assertFalse(true);

}

@Test

public void testContainsC() {

// PART 1

BSTSet t = new BSTSet<>();

assertFalse(true);

}

// Feel free to write more contains tests!

@Test

public void testDeleteMinLeaf() {

BSTSet n = new 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 = new 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 = new 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 = new 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 = new BSTSet<>();

t.add(44);

assertTrue(t.remove(44));

assertTrue(t.isEmpty());

}

@Test

public void testRemoveRoot2() {

BSTSet t = new BSTSet<>();

t.add(50);

assertFalse(t.remove(25));

assertTrue(t.remove(50));

assertTrue(t.isEmpty());

}

@Test

public void testRemoveRoot3() {

BSTSet t = new 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 = new 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 = new 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 = new 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 = new 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 > void subsetHelper(T[] input, T fromKey, T toKey){

// use a Java SortedSet to check ours

java.util.SortedSet exp = new java.util.TreeSet();

exp.addAll(Arrays.asList(input));

java.util.SortedSet expSubset = exp.subSet(fromKey, toKey);

// insert into our Set and take subset

BSTSet t = BSTSet.bulkInsert(input);

NavigableSet subt = t.subSet(fromKey, toKey);

// 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 = new AVLTreeSet<>();

t.add("Dog");

assertFalse(t.contains("Cat"));

assertTrue(t.contains("Dog"));

AVLTreeSet s = new 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);

}

}

}