import java.util.ArrayList;

public class AVLTree implements AVLTreeADT {

private int size;
private AVLTreeNode root;

public AVLTree() {
this.size = 0;
this.root = new AVLTreeNode();
}

@Override
public AVLTreeNode get(AVLTreeNode node, int key) {
AVLTreeNode current = node;
while (!current.isLeaf() && current.getKey() != key) {
if (key < current.getKey())
current = current.getLeft();
else
current = current.getRight();
}
return current;
}

@Override
public AVLTreeNode smallest(AVLTreeNode node) {
if (node.isLeaf())
return null;
AVLTreeNode current = node;
while (!current.getLeft().isLeaf()) {
current = current.getLeft();
}
return current;
}

@Override
public AVLTreeNode put(AVLTreeNode node, int key, int data) throws TreeException {
AVLTreeNode current = get(node, key);
if (current.isInternal())
throw new TreeException("Error: Duplicate key insertion.");
current.setKey(key);
current.setData(data);
current.setLeft(new AVLTreeNode(current));
current.setRight(new AVLTreeNode(current));
this.size++;
recomputeHeight(node);
return current;
}

@Override
public AVLTreeNode remove(AVLTreeNode node, int key) throws TreeException {
AVLTreeNode current = get(node, key);
if (current.isLeaf())
throw new TreeException("Error: Removal of key not in tree.");
// System.out.println("Current: " + current + " " + current.getLeft() + " " +
// current.getRight());
if (current.getLeft().isLeaf() && current.getRight().isLeaf()) {
if (current.isRoot()) {
setRoot(new AVLTreeNode());
current = root();
} else {
AVLTreeNode parent = current.getParent();
if (parent.getLeft().isInternal() && parent.getLeft().getKey() == key) {
parent.setLeft(new AVLTreeNode(parent));
current = parent.getLeft();
} else {
parent.setRight(new AVLTreeNode(parent));
current = parent.getRight();
}
}
this.size--;
} else if (current.getLeft().isLeaf()) {
if (current.isRoot()) {
setRoot(current.getRight());
} else {
AVLTreeNode parent = current.getParent();
if (parent.getLeft().isInternal() && parent.getLeft().getKey() == key) {
parent.setLeft(current.getRight());
parent.getLeft().setParent(parent);
} else {
parent.setRight(current.getRight());
parent.getRight().setParent(parent);
}
}
this.size--;
current = current.getRight();
} else if (current.getRight().isLeaf()) {
if (current.isRoot()) {
setRoot(current.getLeft());
} else {
AVLTreeNode parent = current.getParent();
if (parent.getLeft().isInternal() && parent.getLeft().getKey() == key) {
parent.setLeft(current.getLeft());
parent.getLeft().setParent(parent);
} else {
parent.setRight(current.getLeft());
parent.getRight().setParent(parent);
}
}
this.size--;
current = current.getLeft();
} else {
AVLTreeNode smallest = smallest(current.getRight());
//System.out.println("Smallest: " + smallest);
AVLTreeNode next = remove(node, smallest.getKey());
//System.out.println("Next: " + next);
if (current.isRoot()) {
setRoot(smallest);
root().setLeft(current.getLeft());
root().setRight(current.getRight

The focus of this assignment is to create your own class and use it...