Part 1: Contains method The Set.contains method returns true if and only if the
ID: 3710843 • Letter: P
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 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.
Code BSTSet.java:
import java.util.*;
public class BSTSet<T extends Comparable<T>> implements NavigableSet<T> {
// the root of the tree
protected TreeNode<T> 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 <E extends Comparable<E>> BSTSet<E> bulkInsert(E[] data) {
BSTSet<E> b = new BSTSet<>();
for (int i=0; i<data.length; i++) {
b.insert(b.root, data[i]);
}
return b;
}
private void insert(TreeNode<T> 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<T> 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<T> deleteMin(TreeNode<T> n) {
TreeNode<T> 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<T> oldChild, TreeNode newChild) {
TreeNode<T> 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<T> getParent(TreeNode<T> 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<T> getParentHelper(TreeNode<T> current, TreeNode<T> 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<TreeNode> globalStack = new Stack<>();
globalStack.push(root);
int emptyLeaf = 32;
boolean isRowEmpty = false;
System.out.println("****..................................................................................................................................****");
while (isRowEmpty == false) {
Stack<TreeNode> 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<TreeNode> 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<Integer> t = new BSTSet<>();
t.add(10);
assertEquals(1, t.size);
t.add(20);
assertEquals(2, t.size);
}
@Test
public void testContainsA() {
// PART 1
BSTSet<Integer> t = new BSTSet<>();
assertFalse(true);
}
@Test
public void testContainsB() {
// PART 1
BSTSet<Integer> t = new BSTSet<>();
assertFalse(true);
}
@Test
public void testContainsC() {
// PART 1
BSTSet<String> t = new BSTSet<>();
assertFalse(true);
}
// Feel free to write more contains tests!
@Test
public void testDeleteMinLeaf() {
BSTSet<Integer> 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<Integer> 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<Integer> 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<Integer> 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<Integer> t = new BSTSet<>();
t.add(44);
assertTrue(t.remove(44));
assertTrue(t.isEmpty());
}
@Test
public void testRemoveRoot2() {
BSTSet<Integer> t = new BSTSet<>();
t.add(50);
assertFalse(t.remove(25));
assertTrue(t.remove(50));
assertTrue(t.isEmpty());
}
@Test
public void testRemoveRoot3() {
BSTSet<Integer> 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<Integer> 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<Integer> 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<Integer> 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<Integer> 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 <T extends Comparable<T>> void subsetHelper(T[] input, T fromKey, T toKey){
// use a Java SortedSet to check ours
java.util.SortedSet<T> 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> t = BSTSet.bulkInsert(input);
NavigableSet<T> 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<input.length; 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<String> t = new AVLTreeSet<>();
t.add("Dog");
assertFalse(t.contains("Cat"));
assertTrue(t.contains("Dog"));
AVLTreeSet<StringWrapper> 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<StringWrapper> {
@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);
}
}
}
Explanation / Answer
a)The Three Test Cases for the "Contains()" method should be as follows:
@Test
public void testContainsA() {
BSTSet<Integer> t = new BSTSet<>();
t.add(10);
t.add(20);
t.add(3);
t.add(45);
t.addd(29);
t.add(5);
t.add(1);
assertFalse(t.contains(2));
assertTrue(t.contains(10));
}
@Test
public void testContainsB() {
BSTSet<Integer> t = new BSTSet<>();
t.add(10);
t.add(20);
t.add(3);
t.add(45);
t.addd(29);
t.add(5);
t.add(1);
assertFalse(t.contains(100));
assertTrue(t.contains(45));
}
@Test
public void testContainsC() {
BSTSet<Integer> t = new BSTSet<>();
t.add(10);
t.add(20);
t.add(3);
t.add(45);
t.addd(29);
t.add(5);
t.add(1);
assertFalse(t.contains(-12));
assertTrue(t.contains(1))
}
-------------------------------------------------------------------------------------------------------------------------------------------------------
b) To implement the contains function, we will have to use search in the binary search tree if the element is present. To perform this search we will make use of the structure of the Binary Search Tree.
The Implementation of the Contains function will be as follows.
@Override
public boolean contains(T e) {
TreeNode<T> temp = this.root;
while(temp!=null){
if(temp.data.compareTo(e)==0){
return true;
}
else if(temp.data.compareTo(e)>0){
temp = temp.left;
}
else{
temp = temp.right;
}
}
return false;
}
--------------------------------------------------------------------------------------------------------------------------------------------------