Question
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)
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
// 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