Part 4: Balanced tree

The BSTSet does not keep the tree balanced, and we know that an unbalanced tree can make contains/add/remove operations take O(N) in the worst case instead of O(log N). To improve your Set

implementation, you will complete a second class that uses a balanced binary search tree, AVLTreeSet. Notice that this class extends BSTSet, borrowing most of the functionality.

We've provided implementations of add and remove that call a balancing method to fix the balance property after an insertion or removal. Your job will be to complete the balancing functionality by implementing two methods

AVLTreeSet.rotateLeft

AVLTreeSet.rotateRight

See the comments above these methods to see a detailed description of what each method should do. Notice that the AVLTreeSet.balance method uses rotateLeft and rotateRight in combination to do the double rotation cases, so you don't have to directly implement double rotations.

Tips:

as in the remove implementation, you should use the updateParent method to change what node is at the top of the subtree. It will greatly simplify your code.

Note that the rotation changes the height of the tree, so make sure to call updateHeight at the end. (Do not call updateHeightWholeTree)

All of the tests in AVLTreeSetTest.java should pass when the rotate methods work.

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);

}

}

}