You are required to implement an AVL tree. An AVL is a special type of binary search tree that follows all the same rules: each node has 0-2 children, all data in the left subtree is less than the nodes data, and all data in the right subtree is greater than the nodes data. The AVL differs from the BST with its own self-balancing rotations, which you must implement. All methods in the AVL tree that are not O(1) must be implemented recursively. Good recursion with simple, focused states is strongly encouraged for this assignment in particular. Your AVL tree will implement the AVL interface provided. It will have two constructors: a no-argument constructor (which should initialize an empty tree), and a constructor that takes in data to be added to the tree, and initializes the tree with this data.

Each node has two additional instance variables, height and balanceFactor. The height variable should represent the height of the node (recall that a nodes height is max(child nodes heights)+1. The balance factor of a node should be equal to its left childs height minus its right childs height. The tree should rotate appropriately to make sure its always balanced. Keep in mind that you will have to update these instance variables; they are not updated automatically.

You may not use these in your code at any time:

break may only be used in switch-case statements continue package System.arraycopy() clone() assert() Arrays class Array class Collections class Collection.toArray() Reflection APIs Inner or nested classes Lambda Expressions Method References

------------

import java.util.Collection;

public class AVL> implements AVLInterface { // DO NOT ADD OR MODIFY INSTANCE VARIABLES. private AVLNode root; private int size;

/** * A no argument constructor that should initialize an empty AVL tree. * DO NOT IMPLEMENT THIS CONSTRUCTOR! */ public AVL() { }

/** * Initializes the AVL tree with the data in the Collection. The data * should be added in the same order it is in the Collection. * * @param data the data to add to the tree * @throws IllegalArgumentException if data or any element in data is null */ public AVL(Collection data) {

}

@Override public void add(T data) {

}

@Override public T remove(T data) {

}

@Override public T get(T data) {

}

@Override public boolean contains(T data) {

}

@Override public int size() { // DO NOT MODIFY THIS METHOD! return size; }

@Override public T getSecondLargest() { }

@Override public boolean equals(Object obj) {

}

@Override public void clear() {

}

@Override public int height() {

}

@Override public AVLNode getRoot() { // DO NOT MODIFY THIS METHOD! return root; } }

/** * The interface for an AVL tree. * DO NOT EDIT THIS FILE! * * * @version 1.0 */ public interface AVLInterface> { /** * Add the data as a leaf to the AVL. Should traverse the tree to find the * appropriate location. If the data is already in the tree, then nothing * should be done (the duplicate shouldn't get added, and size should not be * incremented). * * Remember to recalculate heights going up the tree, rebalancing if * necessary. * * @throws java.lang.IllegalArgumentException if the data is null * @param data the data to be added */ void add(T data);

/** * Removes the data from the tree. There are 3 cases to consider: * 1: the data is a leaf. In this case, simply remove it. * 2: the data has one child. In this case, simply replace the node with * the child node. * 3: the data has 2 children. For this assignment, use the successor to * replace the data you are removing, not the predecessor. * * Remember to recalculate heights going up the tree, rebalancing if * necessary. * * @throws java.lang.IllegalArgumentException if the data is null * @throws java.util.NoSuchElementException if the data is not in the tree * @param data data to remove from the tree * @return the data removed from the tree. Do not return the same data * that was passed in. Return the data that was stored in the tree. */ T remove(T data);

/** * Returns the data in the tree matching the parameter passed in. * * @throws java.lang.IllegalArgumentException if the data is null * @throws java.util.NoSuchElementException if the data is not found * @param data data to get in the AVL tree * @return the data in the tree equal to the parameter. Do not return the * same data that was passed in. Return the data that was stored in the * tree. */ T get(T data);

/** * Returns whether or not the parameter is contained within the tree. * * @throws java.lang.IllegalArgumentException if the data is null * @param data data to find in the AVL tree * @return whether or not the parameter is contained within the tree */ boolean contains(T data);

/** * Get the number of elements in the tree. * * @return the number of elements in the tree */ int size();

/** * Retrieves the second largest data from the tree. * * @throws java.util.NoSuchElementException if there isn't enough data in * the tree for there to be a second largest element * @return the second largest data in the tree */ T getSecondLargest();

/** * Determines whether this tree is equal to the passed in object. * * Two trees are considered equal if they are equivalent structurally * with equal data being in the same locations in each (use value equality). * * Do not consider the stored heights and balance factors in your equality * check, only the structure and the location of the data. * * Remember, the .equals() method from the Object class takes in an Object, * not an AVL object. So, once you've verified that the passed in object * is indeed an instance of AVL, you need to cast it to type AVL. If the * passed in object is not an AVL, then return false. Keep in mind that if * it's an AVL instance, you can access the root directly; do not use * the getRoot() method. * * You may not use anything implementing java.util.List or equivalent to * store the data for later use. * * Ordinarily, you would override the hashCode method as well, but you * shouldn't do so for this assignment. * * @param obj the object we are checking equality with * @return true if the trees are equal, false otherwise */ boolean equals(Object obj);

/** * Clear the tree. */ void clear();

/** * Return the height of the root of the tree. * * This method does not need to traverse the tree since this is an AVL. * * @return the height of the root of the tree, -1 if the tree is empty */ int height(); /** * THIS METHOD IS ONLY FOR TESTING PURPOSES. * DO NOT USE IT IN YOUR CODE * DO NOT CHANGE THIS METHOD * * @return the root of the tree */ AVLNode getRoot(); }

/** * This class represents a node in your AVL. * DO NOT EDIT THIS FILE! * * * @version 1.0 */ public class AVLNode> { private T data; private AVLNode left; private AVLNode right; private int height; private int balanceFactor;

/** * Create an AVL node with the specified data. * * @param data the data to be stored in this node */ public AVLNode(T data) { this.data = data; }

/** * Get the data in this node. * * @return data in this node */ public T getData() { return data; }

/** * Set the data in this node. * * @param data data to store in this node */ public void setData(T data) { this.data = data; }

/** * Get the node to the left of this node. * * @return node to the left of this node. */ public AVLNode getLeft() { return left; }

/** * Set the node to the left of this node. * * @param left node to the left of this node */ public void setLeft(AVLNode left) { this.left = left; }

/** * Get the node to the right of this node. * * @return node to the right of this node. */ public AVLNode getRight() { return right; }

/** * Set the node to the right of this node. * * @param right node to the right of this node */ public void setRight(AVLNode right) { this.right = right; }

/** * Get the height of this node. * * @return height of this node */ public int getHeight() { return height; }

/** * Set the height of this node. * * @param height height of this node */ public void setHeight(int height) { this.height = height; }

/** * Get the balance factor of this node. * * @return balance factor of this node. */ public int getBalanceFactor() { return balanceFactor; }

/** * Set the balance factor of this node. * * @param balanceFactor balance factor of this node */ public void setBalanceFactor(int balanceFactor) { this.balanceFactor = balanceFactor; }

/** * DO NOT USE EXCEPT FOR DEBUGGING PURPOSES */ @Override public String toString() { return String.format("Node containing %s (height %d, bf %d)", data.toString(), height, balanceFactor); } }

Here is the 1st j unit class make sure all tests work

import org.junit.Test; import java.util.Arrays; import java.util.Collections; import java.util.NoSuchElementException; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertNull; import static org.junit.Assert.assertSame; import static org.junit.Assert.assertTrue; /** * Tests for Gatech CS1332 Spring 2018 HW7 * * @author sergeys * @version 1 */ public class SS1332HW7Tests { public static final long TIMEOUT = 200L; @Test(timeout = TIMEOUT, expected = IllegalArgumentException.class) public void testAddException() { AVLInterface avl = new AVL<>(); avl.add(null); } @Test(timeout = TIMEOUT) public void testAddDuplicate() { AVLInterface avl = new AVL<>(); avl.add(0); avl.add(0); assertEquals(1, avl.size()); } @Test(timeout = TIMEOUT) public void testRootNull() { AVLInterface avl = new AVL<>(); avl.add(0); assertEquals(0, avl.getRoot().getData().intValue()); assertEquals(0, avl.remove(0).intValue()); assertNull(avl.getRoot()); } @Test(timeout = TIMEOUT) public void testClear() { AVLInterface avl = new AVL<>(); avl.add(0); assertEquals(0, avl.getRoot().getData().intValue()); avl.clear(); assertNull(avl.getRoot()); } @Test(timeout = TIMEOUT, expected = IllegalArgumentException.class) public void testRemoveException1() { AVLInterface avl = new AVL<>(); avl.remove(null); } @Test(timeout = TIMEOUT, expected = NoSuchElementException.class) public void testRemoveException2() { AVLInterface avl = new AVL<>(); avl.remove(0); } @Test(timeout = TIMEOUT, expected = IllegalArgumentException.class) public void testGetException1() { AVLInterface avl = new AVL<>(); avl.get(null); } @Test(timeout = TIMEOUT, expected = NoSuchElementException.class) public void testGetException2() { AVLInterface avl = new AVL<>(); avl.get(0); } @Test(timeout = TIMEOUT, expected = IllegalArgumentException.class) public void testContainsException() { AVLInterface avl = new AVL<>(); avl.contains(null); } @Test(timeout = TIMEOUT) public void testHeightEmpty() { AVLInterface avl = new AVL<>(); assertEquals(-1, avl.height()); } /* 0 -4 4 -6 -2 2 6 -7 -5 -3 -1 1 3 5 7 */ @Test(timeout = TIMEOUT) public void testAddBasic() { AVLInterface avl = new AVL<>(); avl.add(0); avl.add(-4); avl.add(4); avl.add(-2); avl.add(2); avl.add(-6); avl.add(6); avl.add(-1); avl.add(1); avl.add(-3); avl.add(3); avl.add(-7); avl.add(7); avl.add(-5); avl.add(5); assertEquals(0, avl.getRoot().getData().intValue()); assertEquals(-4, avl.getRoot().getLeft().getData().intValue()); assertEquals(-6, avl.getRoot().getLeft().getLeft().getData().intValue()); assertEquals(-7, avl.getRoot().getLeft().getLeft().getLeft().getData() .intValue()); assertEquals(-5, avl.getRoot().getLeft().getLeft().getRight().getData() .intValue()); assertEquals(-2, avl.getRoot().getLeft().getRight().getData().intValue()); assertEquals(-3, avl.getRoot().getLeft().getRight().getLeft().getData() .intValue()); assertEquals(-1, avl.getRoot().getLeft().getRight().getRight().getData() .intValue()); assertEquals(4, avl.getRoot().getRight().getData().intValue()); assertEquals(6, avl.getRoot().getRight().getRight().getData().intValue()); assertEquals(7, avl.getRoot().getRight().getRight().getRight().getData() .intValue()); assertEquals(5, avl.getRoot().getRight().getRight().getLeft().getData() .intValue()); assertEquals(2, avl.getRoot().getRight().getLeft().getData().intValue()); assertEquals(3, avl.getRoot().getRight().getLeft().getRight().getData() .intValue()); assertEquals(1, avl.getRoot().getRight().getLeft().getLeft().getData() .intValue()); } @Test(timeout = TIMEOUT) public void testConstructorBasic() { AVLInterface avl = new AVL<>( Arrays.asList(0, -4, 4, -2, 2, -6, 6, -1, 1, -3, 3, -7, 7, -5, 5)); assertEquals(0, avl.getRoot().getData().intValue()); assertEquals(-4, avl.getRoot().getLeft().getData().intValue()); assertEquals(-6, avl.getRoot().getLeft().getLeft().getData().intValue()); assertEquals(-7, avl.getRoot().getLeft().getLeft().getLeft().getData() .intValue()); assertEquals(-5, avl.getRoot().getLeft().getLeft().getRight().getData() .intValue()); assertEquals(-2, avl.getRoot().getLeft().getRight().getData().intValue()); assertEquals(-3, avl.getRoot().getLeft().getRight().getLeft().getData() .intValue()); assertEquals(-1, avl.getRoot().getLeft().getRight().getRight().getData() .intValue()); assertEquals(4, avl.getRoot().getRight().getData().intValue()); assertEquals(6, avl.getRoot().getRight().getRight().getData().intValue()); assertEquals(7, avl.getRoot().getRight().getRight().getRight().getData() .intValue()); assertEquals(5, avl.getRoot().getRight().getRight().getLeft().getData() .intValue()); assertEquals(2, avl.getRoot().getRight().getLeft().getData().intValue()); assertEquals(3, avl.getRoot().getRight().getLeft().getRight().getData() .intValue()); assertEquals(1, avl.getRoot().getRight().getLeft().getLeft().getData() .intValue()); } @Test(timeout = TIMEOUT) public void testAdd() { AVLInterface avl = new AVL<>(); avl.add(0); assertEquals(1, avl.size()); assertEquals(0, avl.getRoot().getData().intValue()); avl.add(1); assertEquals(2, avl.size()); assertEquals(0, avl.getRoot().getData().intValue()); assertEquals(1, avl.getRoot().getRight().getData().intValue()); avl.add(2); assertEquals(3, avl.size()); assertEquals(1, avl.getRoot().getData().intValue()); assertEquals(0, avl.getRoot().getLeft().getData().intValue()); assertEquals(2, avl.getRoot().getRight().getData().intValue()); avl.add(4); assertEquals(4, avl.size()); assertEquals(1, avl.getRoot().getData().intValue()); assertEquals(0, avl.getRoot().getLeft().getData().intValue()); assertEquals(2, avl.getRoot().getRight().getData().intValue()); assertEquals(4, avl.getRoot().getRight().getRight().getData().intValue()); avl.add(3); assertEquals(5, avl.size()); assertEquals(1, avl.getRoot().getData().intValue()); assertEquals(0, avl.getRoot().getLeft().getData().intValue()); assertEquals(3, avl.getRoot().getRight().getData().intValue()); assertEquals(2, avl.getRoot().getRight().getLeft().getData().intValue()); assertEquals(4, avl.getRoot().getRight().getRight().getData().intValue()); avl.add(5); assertEquals(6, avl.size()); assertEquals(3, avl.getRoot().getData().intValue()); assertEquals(1, avl.getRoot().getLeft().getData().intValue()); assertEquals(0, avl.getRoot().getLeft().getLeft().getData().intValue()); assertEquals(2, avl.getRoot().getLeft().getRight().getData().intValue()); assertEquals(4, avl.getRoot().getRight().getData().intValue()); assertEquals(5, avl.getRoot().getRight().getRight().getData().intValue()); avl.add(6); assertEquals(7, avl.size()); assertEquals(3, avl.getRoot().getData().intValue()); assertEquals(1, avl.getRoot().getLeft().getData().intValue()); assertEquals(0, avl.getRoot().getLeft().getLeft().getData().intValue()); assertEquals(2, avl.getRoot().getLeft().getRight().getData().intValue()); assertEquals(5, avl.getRoot().getRight().getData().intValue()); assertEquals(4, avl.getRoot().getRight().getLeft().getData().intValue()); assertEquals(6, avl.getRoot().getRight().getRight().getData().intValue()); } @Test(timeout = TIMEOUT) public void testConstructor() { AVLInterface avl = new AVL<>(Arrays.asList(0, 1, 2, 4, 3, 5, 6)); assertEquals(7, avl.size()); assertEquals(3, avl.getRoot().getData().intValue()); assertEquals(1, avl.getRoot().getLeft().getData().intValue()); assertEquals(0, avl.getRoot().getLeft().getLeft().getData().intValue()); assertEquals(2, avl.getRoot().getLeft().getRight().getData().intValue()); assertEquals(5, avl.getRoot().getRight().getData().intValue()); assertEquals(4, avl.getRoot().getRight().getLeft().getData().intValue()); assertEquals(6, avl.getRoot().getRight().getRight().getData().intValue()); } /* 0 -4 4 -6 -2 2 6 -7 -5 -3 -1 1 3 5 7 */ @Test(timeout = TIMEOUT) public void testRemove2ChildrenBasic() { AVLInterface avl = new AVL<>(); avl.add(0); avl.add(-4); avl.add(4); avl.add(-2); avl.add(2); avl.add(-6); avl.add(6); avl.add(-1); avl.add(1); avl.add(-3); avl.add(3); avl.add(-7); avl.add(7); avl.add(-5); avl.add(5); assertEquals(15, avl.size()); assertEquals(-6, avl.remove(-6).intValue()); assertEquals(-5, avl.getRoot().getLeft().getLeft().getData().intValue()); assertEquals(14, avl.size()); assertEquals(-2, avl.remove(-2).intValue()); assertEquals(-1, avl.getRoot().getLeft().getRight().getData().intValue()); assertEquals(13, avl.size()); assertEquals(2, avl.remove(2).intValue()); assertEquals(3, avl.getRoot().getRight().getLeft().getData().intValue()); assertEquals(12, avl.size()); assertEquals(6, avl.remove(6).intValue()); assertEquals(7, avl.getRoot().getRight().getRight().getData().intValue()); assertEquals(11, avl.size()); } /* 0 -4 4 -6 -2 2 6 -7 -5 -3 -1 1 3 5 7 */ @Test(timeout = TIMEOUT) public void testRemove2Children() { AVLInterface avl = new AVL<>( Arrays.asList(0, -4, 4, -6, -2, 2, 6, -7, -5, -3, -1, 1, 3, 5, 7)); assertEquals(15, avl.size()); assertEquals(0, avl.remove(0).intValue()); assertEquals(1, avl.getRoot().getData().intValue()); assertEquals(6, avl.getSecondLargest().intValue()); assertEquals(14, avl.size()); assertEquals(1, avl.remove(1).intValue()); assertEquals(2, avl.getRoot().getData().intValue()); assertEquals(6, avl.getSecondLargest().intValue()); assertEquals(13, avl.size()); assertEquals(2, avl.remove(2).intValue()); assertEquals(3, avl.getRoot().getData().intValue()); assertEquals(6, avl.getRoot().getRight().getData().intValue()); assertEquals(7, avl.getRoot().getRight().getRight().getData().intValue()); assertEquals(4, avl.getRoot().getRight().getLeft().getData().intValue()); assertEquals(5, avl.getRoot().getRight().getLeft().getRight().getData() .intValue()); assertEquals(6, avl.getSecondLargest().intValue()); assertEquals(12, avl.size()); assertEquals(3, avl.remove(3).intValue()); assertEquals(4, avl.getRoot().getData().intValue()); assertEquals(6, avl.getRoot().getRight().getData().intValue()); assertEquals(5, avl.getRoot().getRight().getLeft().getData().intValue()); assertEquals(7, avl.getRoot().getRight().getRight().getData().intValue()); assertEquals(6, avl.getSecondLargest().intValue()); assertEquals(11, avl.size()); assertEquals(4, avl.remove(4).intValue()); assertEquals(5, avl.getRoot().getData().intValue()); assertEquals(6, avl.getRoot().getRight().getData().intValue()); assertEquals(7, avl.getRoot().getRight().getRight().getData().intValue()); assertEquals(6, avl.getSecondLargest().intValue()); assertEquals(10, avl.size()); assertEquals(5, avl.remove(5).intValue()); assertEquals(-4, avl.getRoot().getData().intValue()); assertEquals(6, avl.getRoot().getRight().getData().intValue()); assertEquals(7, avl.getRoot().getRight().getRight().getData().intValue()); assertEquals(-2, avl.getRoot().getRight().getLeft().getData().intValue()); assertEquals(-3, avl.getRoot().getRight().getLeft().getLeft().getData() .intValue()); assertEquals(-1, avl.getRoot().getRight().getLeft().getRight().getData() .intValue()); assertEquals(-6, avl.getRoot().getLeft().getData().intValue()); assertEquals(-7, avl.getRoot().getLeft().getLeft().getData().intValue()); assertEquals(6, avl.getSecondLargest().intValue()); assertEquals(9, avl.size()); assertEquals(-4, avl.remove(-4).intValue()); assertEquals(-3, avl.getRoot().getData().intValue()); assertEquals(6, avl.getSecondLargest().intValue()); assertEquals(8, avl.size()); assertEquals(-3, avl.remove(-3).intValue()); assertEquals(-2, avl.getRoot().getData().intValue()); assertEquals(6, avl.getSecondLargest().intValue()); assertEquals(7, avl.size()); assertEquals(-2, avl.remove(-2).intValue()); assertEquals(-1, avl.getRoot().getData().intValue()); assertEquals(6, avl.getSecondLargest().intValue()); assertEquals(6, avl.size()); assertEquals(-1, avl.remove(-1).intValue()); assertEquals(6, avl.getRoot().getData().intValue()); assertEquals(6, avl.getSecondLargest().intValue()); assertEquals(5, avl.size()); assertEquals(6, avl.remove(6).intValue()); assertEquals(-6, avl.getRoot().getData().intValue()); assertEquals(-7, avl.getRoot().getLeft().getData().intValue()); assertEquals(7, avl.getRoot().getRight().getData().intValue()); assertEquals(-5, avl.getRoot().getRight().getLeft().getData().intValue()); assertEquals(-5, avl.getSecondLargest().intValue()); assertEquals(4, avl.size()); assertEquals(-6, avl.remove(-6).intValue()); assertEquals(-5, avl.getRoot().getData().intValue()); assertEquals(-5, avl.getSecondLargest().intValue()); assertEquals(3, avl.size()); assertEquals(-5, avl.remove(-5).intValue()); assertEquals(7, avl.getRoot().getData().intValue()); assertEquals(-7, avl.getSecondLargest().intValue()); assertEquals(2, avl.size()); assertEquals(7, avl.remove(7).intValue()); assertEquals(-7, avl.getRoot().getData().intValue()); assertEquals(1, avl.size()); assertEquals(-7, avl.remove(-7).intValue()); assertSame(null, avl.getRoot()); assertEquals(0, avl.size()); } @Test(timeout = TIMEOUT, expected = NoSuchElementException.class) public void testSecondLargestException() { new AVL<>(Collections.singletonList(0)).getSecondLargest(); } /* 0 -4 4 -6 -2 2 6 -7 -1 3 5 */ @Test(timeout = TIMEOUT) public void testRemove1ChildBasic() { AVLInterface avl = new AVL<>(); avl.add(0); avl.add(-4); avl.add(4); avl.add(-2); avl.add(2); avl.add(-6); avl.add(6); avl.add(-1); avl.add(3); avl.add(-7); avl.add(5); assertEquals(11, avl.size()); assertEquals(-6, avl.remove(-6).intValue()); assertEquals(-7, avl.getRoot().getLeft().getLeft().getData().intValue()); assertEquals(10, avl.size()); assertEquals(-2, avl.remove(-2).intValue()); assertEquals(-1, avl.getRoot().getLeft().getRight().getData().intValue()); assertEquals(9, avl.size()); assertEquals(6, avl.remove(6).intValue()); assertEquals(5, avl.getRoot().getRight().getRight().getData().intValue()); assertEquals(8, avl.size()); assertEquals(2, avl.remove(2).intValue()); assertEquals(3, avl.getRoot().getRight().getLeft().getData().intValue()); assertEquals(7, avl.size()); } /* 0 -4 4 -6 -2 2 6 -7 -1 3 5 */ @Test(timeout = TIMEOUT) public void testRemove1Child() { AVLInterface avl = new AVL<>(Arrays.asList(0, -4, 4, -2, 2, -6, 6, -1, 3, -7, 5)); assertEquals(11, avl.size()); assertEquals(6, avl.remove(6).intValue()); assertEquals(5, avl.getRoot().getRight().getRight().getData().intValue()); assertEquals(10, avl.size()); assertEquals(5, avl.remove(5).intValue()); assertEquals(4, avl.getRoot().getRight().getRight().getData().intValue()); assertEquals(9, avl.size()); assertEquals(2, avl.remove(2).intValue()); assertSame(null, avl.getRoot().getRight().getLeft()); assertEquals(8, avl.size()); /* 0 -4 3 -6 -2 -7 -1 */ assertEquals(3, avl.remove(3).intValue()); /* -4 -6 0 -7 -2 4 -1 */ assertEquals(-4, avl.getRoot().getData().intValue()); assertEquals(-6, avl.getRoot().getLeft().getData().intValue()); assertEquals(-7, avl.getRoot().getLeft().getLeft().getData().intValue()); assertEquals(0, avl.getRoot().getRight().getData().intValue()); assertEquals(4, avl.getRoot().getRight().getRight().getData().intValue()); assertEquals(-2, avl.getRoot().getRight().getLeft().getData().intValue()); assertEquals(-1, avl.getRoot().getRight().getLeft().getRight().getData() .intValue()); assertEquals(7, avl.size()); assertEquals(-6, avl.remove(-6).intValue()); /* -2 -4 0 -7 -1 4 */ assertEquals(-2, avl.getRoot().getData().intValue()); assertEquals(-4, avl.getRoot().getLeft().getData().intValue()); assertEquals(-7, avl.getRoot().getLeft().getLeft().getData().intValue()); assertEquals(0, avl.getRoot().getRight().getData().intValue()); assertEquals(4, avl.getRoot().getRight().getRight().getData().intValue()); assertEquals(-1, avl.getRoot().getRight().getLeft().getData().intValue()); assertEquals(6, avl.size()); assertEquals(-4, avl.remove(-4).intValue()); assertEquals(-7, avl.getRoot().getLeft().getData().intValue()); assertEquals(5, avl.size()); assertEquals(-7, avl.remove(-7).intValue()); /* 0 -2 4 -1 */ assertEquals(0, avl.getRoot().getData().intValue()); assertEquals(-2, avl.getRoot().getLeft().getData().intValue()); assertEquals(-1, avl.getRoot().getLeft().getRight().getData().intValue()); assertEquals(4, avl.getRoot().getRight().getData().intValue()); assertEquals(4, avl.size()); } /* 0 -4 4 -6 -2 2 6 */ @Test(timeout = TIMEOUT) public void testRemove0ChildrenBasic() { AVLInterface avl = new AVL<>(); avl.add(0); avl.add(-4); avl.add(4); avl.add(-2); avl.add(2); avl.add(-6); avl.add(6); assertEquals(7, avl.size()); assertEquals(-6, avl.remove(-6).intValue()); assertNull(avl.getRoot().getLeft().getLeft()); assertEquals(6, avl.size()); assertEquals(-2, avl.remove(-2).intValue()); assertNull(avl.getRoot().getLeft().getRight()); assertEquals(5, avl.size()); assertEquals(2, avl.remove(2).intValue()); assertNull(avl.getRoot().getRight().getLeft()); assertEquals(4, avl.size()); assertEquals(6, avl.remove(6).intValue()); assertNull(avl.getRoot().getRight().getRight()); assertEquals(3, avl.size()); assertEquals(-4, avl.remove(-4).intValue()); assertNull(avl.getRoot().getLeft()); assertEquals(2, avl.size()); assertEquals(4, avl.remove(4).intValue()); assertNull(avl.getRoot().getRight()); assertEquals(1, avl.size()); assertEquals(0, avl.remove(0).intValue()); assertNull(avl.getRoot()); assertEquals(0, avl.size()); } @Test(timeout = TIMEOUT) public void testContains() { AVLInterface avl = new AVL<>(); avl.add(0); avl.add(-4); avl.add(-2); avl.add(-1); avl.add(-3); avl.add(-6); avl.add(-7); avl.add(-5); avl.add(4); avl.add(2); avl.add(1); avl.add(3); avl.add(6); avl.add(7); avl.add(5); for (int i = -7; i <= 7; i++) { assertTrue(avl.contains(i)); } assertFalse(avl.contains(-8)); assertFalse(avl.contains(-9)); assertFalse(avl.contains(-10)); assertFalse(avl.contains(8)); assertFalse(avl.contains(9)); assertFalse(avl.contains(10)); } @SuppressWarnings("RedundantStringConstructorCall") @Test(timeout = TIMEOUT) public void testGet() { AVL avl = new AVL<>(); String s4 = new String("4"); String s3 = new String("3"); String s5 = new String("5"); avl.add(s4); avl.add("2"); avl.add("1"); avl.add(s3); avl.add("6"); avl.add(s5); avl.add("7"); assertSame(s4, avl.get(new String("4"))); assertSame(s3, avl.get(new String("3"))); assertSame(s5, avl.get(new String("5"))); } @SuppressWarnings("EqualsBetweenInconvertibleTypes") @Test(timeout = TIMEOUT) public void testEquals() { AVLInterface avl1 = new AVL<>(Arrays.asList(0, -4, 4, -2, 2, -6, 6, -1, 3, -7, 5)); AVLInterface avl2 = avl1; assertTrue(avl1.equals(avl2)); avl2 = new AVL<>(Arrays.asList(0, -4, 4, -2, 2, -6, 6, -1, 3, -7, 5)); assertTrue(avl1.equals(avl2)); avl1 = new AVL<>(Arrays.asList(0, 1)); avl2 = new AVL<>(Arrays.asList(1, 0)); assertFalse(avl1.equals(avl2)); assertFalse(avl1.equals("")); //An AVL of strings (not equal to Integers) assertFalse(avl1.equals(new AVL<>(Arrays.asList("0", "1")))); avl1 = new AVL<>(); //An empty AVL of strings assertTrue(avl1.equals(new AVL())); } } 

Here is the 2nd j unit class

import org.junit.Before; import org.junit.Test; import java.util.Arrays; import java.util.NoSuchElementException; import static org.junit.Assert.*; public class AVLTest { private AVL avl; @Before public void setup() { avl = new AVL<>(); } @Test public void basicTest() { assertEquals(0, avl.size()); assertNull(avl.getRoot()); assertEquals(-1, avl.height()); avl.add(10); assertEquals(1, avl.size()); assertTrue(avl.contains(10)); assertEquals(Integer.valueOf(10), avl.get(10)); assertEquals(Integer.valueOf(10), avl.getRoot().getData()); assertEquals(0, avl.height()); assertEquals(0, avl.getRoot().getHeight()); assertEquals(0, avl.getRoot().getBalanceFactor()); avl.add(5); assertEquals(2, avl.size()); assertTrue(avl.contains(5)); assertEquals(Integer.valueOf(5), avl.get(5)); assertEquals(Integer.valueOf(5), avl.getRoot().getLeft().getData()); assertEquals(1, avl.height()); assertEquals(1, avl.getRoot().getHeight()); assertEquals(1, avl.getRoot().getBalanceFactor()); assertEquals(0, avl.getRoot().getLeft().getHeight()); assertEquals(0, avl.getRoot().getLeft().getBalanceFactor()); assertEquals(Integer.valueOf(5), avl.getSecondLargest()); avl.add(15); assertEquals(3, avl.size()); assertTrue(avl.contains(15)); assertEquals(Integer.valueOf(15), avl.get(15)); assertEquals(Integer.valueOf(15), avl.getRoot().getRight().getData()); assertEquals(1, avl.height()); assertEquals(1, avl.getRoot().getHeight()); assertEquals(0, avl.getRoot().getBalanceFactor()); assertEquals(0, avl.getRoot().getLeft().getHeight()); assertEquals(0, avl.getRoot().getLeft().getBalanceFactor()); assertEquals(0, avl.getRoot().getRight().getHeight()); assertEquals(0, avl.getRoot().getRight().getBalanceFactor()); assertEquals(Integer.valueOf(10), avl.getSecondLargest()); avl.add(15); assertEquals(3, avl.size()); assertEquals(Integer.valueOf(15), avl.remove(15)); assertEquals(2, avl.size()); assertEquals(1, avl.height()); assertEquals(1, avl.getRoot().getHeight()); assertEquals(1, avl.getRoot().getBalanceFactor()); assertNull(avl.getRoot().getRight()); avl.clear(); assertEquals(0, avl.size()); assertNull(avl.getRoot()); } @Test public void exceptionTest() { try { avl = new AVL<>(null); fail(); } catch (IllegalArgumentException e) { } try { avl.add(null); fail(); } catch (IllegalArgumentException e) { } try { avl.remove(null); fail(); } catch (IllegalArgumentException e) { } try { avl.remove(5); fail(); } catch (NoSuchElementException e) { } try { avl.get(null); fail(); } catch (IllegalArgumentException e) { } try { avl.get(5); fail(); } catch (NoSuchElementException e) { } try { avl.contains(null); fail(); } catch (IllegalArgumentException e) { } try { avl.getSecondLargest(); fail(); } catch (NoSuchElementException e) { } avl.add(5); try { avl.getSecondLargest(); fail(); } catch (NoSuchElementException e) { } } @Test public void functionalityTest() { avl.add(10); avl.add(20); avl.add(30); assertEquals(3, avl.size()); assertEquals(Integer.valueOf(20), avl.getRoot().getData()); assertEquals(Integer.valueOf(10), avl.getRoot().getLeft().getData()); assertEquals(Integer.valueOf(30), avl.getRoot().getRight().getData()); assertEquals(1, avl.height()); assertEquals(0, avl.getRoot().getLeft().getHeight()); assertEquals(Integer.valueOf(20), avl.getSecondLargest()); avl.add(40); assertEquals(Integer.valueOf(30), avl.getSecondLargest()); avl.add(35); assertEquals(2, avl.height()); assertEquals(Integer.valueOf(20), avl.getRoot().getData()); assertEquals(Integer.valueOf(35), avl.getRoot().getRight().getData()); assertEquals(Integer.valueOf(30), avl.getRoot().getRight().getLeft().getData()); assertEquals(Integer.valueOf(40), avl.getRoot().getRight().getRight().getData()); assertEquals(Integer.valueOf(35), avl.getSecondLargest()); avl.add(33); assertEquals(Integer.valueOf(30), avl.getRoot().getData()); assertEquals(Integer.valueOf(20), avl.getRoot().getLeft().getData()); assertEquals(Integer.valueOf(35), avl.getRoot().getRight().getData()); assertEquals(Integer.valueOf(40), avl.getRoot().getRight().getRight().getData()); assertEquals(Integer.valueOf(33), avl.getRoot().getRight().getLeft().getData()); assertEquals(Integer.valueOf(10), avl.getRoot().getLeft().getLeft().getData()); assertEquals(Integer.valueOf(35), avl.getSecondLargest()); avl.remove(35); assertEquals(2, avl.height()); assertEquals(Integer.valueOf(40), avl.getRoot().getRight().getData()); assertEquals(Integer.valueOf(33), avl.getRoot().getRight().getLeft().getData()); avl.clear(); AVL avl2; avl.add(10); avl.add(30); avl.add(5); avl.add(40); avl.add(7); avl.add(15); Integer[] array = {10, 30, 5, 40, 7, 15}; avl2 = new AVL<>(Arrays.asList(array)); assertTrue(avl.equals(avl2)); assertFalse(avl.equals(null)); assertFalse(avl.equals(new Integer(5))); avl2.add(50); assertFalse(avl.equals(avl2)); avl.add(50); assertTrue(avl.equals(avl2)); } @Test public void edgeCaseTest() { avl.add(50); avl.add(25); assertEquals(Integer.valueOf(25), avl.getSecondLargest()); avl.add(75); avl.add(60); assertEquals(Integer.valueOf(60), avl.getSecondLargest()); avl.clear(); Integer[] array = {50, 25, 75, 10, 55, 90, 52, 60, 65}; avl = new AVL<>(Arrays.asList(array)); assertEquals(Integer.valueOf(50), avl.getRoot().getData()); assertEquals(Integer.valueOf(25), avl.getRoot().getLeft().getData()); assertEquals(Integer.valueOf(10), avl.getRoot().getLeft().getLeft().getData()); assertEquals(Integer.valueOf(60), avl.getRoot().getRight().getData()); assertEquals(Integer.valueOf(55), avl.getRoot().getRight().getLeft().getData()); assertEquals(Integer.valueOf(52), avl.getRoot().getRight().getLeft().getLeft().getData()); assertEquals(Integer.valueOf(75), avl.getRoot().getRight().getRight().getData()); assertEquals(Integer.valueOf(90), avl.getRoot().getRight().getRight().getRight().getData()); assertEquals(Integer.valueOf(65), avl.getRoot().getRight().getRight().getLeft().getData()); avl.remove(10); assertEquals(Integer.valueOf(60), avl.getRoot().getData()); assertEquals(Integer.valueOf(50), avl.getRoot().getLeft().getData()); assertEquals(Integer.valueOf(25), avl.getRoot().getLeft().getLeft().getData()); assertEquals(Integer.valueOf(55), avl.getRoot().getLeft().getRight().getData()); assertEquals(Integer.valueOf(52), avl.getRoot().getLeft().getRight().getLeft().getData()); assertEquals(Integer.valueOf(75), avl.getRoot().getRight().getData()); assertEquals(Integer.valueOf(65), avl.getRoot().getRight().getLeft().getData()); assertEquals(Integer.valueOf(90), avl.getRoot().getRight().getRight().getData()); assertEquals(3, avl.height()); avl.remove(55); assertEquals(Integer.valueOf(60), avl.getRoot().getData()); assertEquals(Integer.valueOf(50), avl.getRoot().getLeft().getData()); assertEquals(Integer.valueOf(25), avl.getRoot().getLeft().getLeft().getData()); assertEquals(Integer.valueOf(52), avl.getRoot().getLeft().getRight().getData()); assertEquals(Integer.valueOf(75), avl.getRoot().getRight().getData()); assertEquals(Integer.valueOf(65), avl.getRoot().getRight().getLeft().getData()); assertEquals(Integer.valueOf(90), avl.getRoot().getRight().getRight().getData()); avl.remove(60); assertEquals(Integer.valueOf(65), avl.getRoot().getData()); assertEquals(Integer.valueOf(50), avl.getRoot().getLeft().getData()); assertEquals(Integer.valueOf(25), avl.getRoot().getLeft().getLeft().getData()); assertEquals(Integer.valueOf(52), avl.getRoot().getLeft().getRight().getData()); assertEquals(Integer.valueOf(75), avl.getRoot().getRight().getData()); assertEquals(Integer.valueOf(90), avl.getRoot().getRight().getRight().getData()); assertEquals(2, avl.height()); } } 

Most importantly please make sure each method is being run efficiently with the correct big O.