QuestionQuestion

You have to modify the implementation of a binary search tree (BST) to form an AVL tree. The starting BST source code is given below.

Implementation Specifications
The provided AVLTree class is a simple but functional unbalanced BST implementation. The feature of AVL trees that is currently missing from this implementation is the rebalancing of the tree after add and remove operations. Rebalancing keeps the height of an AVL tree proportional to the logarithm of the number of nodes in the tree, i.e., O(log n). Operations that traverse a path through the tree, e.g., the search operation represented by the contains method, can therefore be performed in logarithmic time. The add and remove operations also run in logarithmic time, thus the additional rebalancing work can take only a logarithmic amount of time. Your primary task is to modify the add and remove methods to perform the AVL rebalancing. You're free to add helper methods, modify types, etc., to complete the AVL implementation, but you should not modify the public interface to the AVLTree class. It's unlikely that you need to modify the contains, size, or clear methods.
Do not include any extraneous files, such as Eclipse IDE files, bytecode files, or subversion files.

public class AVLTree<T extends Comparable<T>> {
private static class Node<T> {
public T item;
public Node<T> parent;
public Node<T> left;
public Node<T> right;

public Node(T item) {
this(item, null);
}

public Node(T item, Node<T> parent) {
this.item = item;
this.parent = parent;
}

public Node<T> getSuccessor() {
if (right != null) {
Node<T> successor = right;
while (successor.left != null)
successor = successor.left;
return successor;
} else {
Node<T> successor = this;
while (successor.parent != null && successor.parent.right == successor)
successor = successor.parent;
successor = successor.parent;
return successor;
}
}
}

private int size;
private Node<T> root;

public boolean add(T item) {
if (item == null)
throw new IllegalArgumentException();

if (root == null) {
root = new Node<T>(item);
size++;
return true;
} else
return add(root, item);
}

private boolean add(Node<T> n, T item) {
int cmp = n.item.compareTo(item);
if (cmp > 0)
// Add child to the left.
if (n.left == null) {
n.left = new Node<T>(item, n);
size++;
return true;
} else
return add(n.left, item);
else if (cmp < 0)
// Add child to the right.
if (n.right == null) {
n.right = new Node<T>(item, n);
size++;
return true;
} else
return add(n.right, item);
else
return false;
}

public boolean remove(T item) {
if (item == null)
throw new IllegalArgumentException();

return remove(root, item);
}

private boolean remove(Node<T> n, T item) {
int cmp = n.item.compareTo(item);
if (cmp > 0)
// Search to the left.
if (n.left == null)
return false;
else
return remove(n.left, item);
else if (cmp < 0)
// Search to the right.
if (n.right == null)
return false;
else
return remove(n.right, item);
else {
remove(n);
size--;
return true;
}
}

private void remove(Node<T> n) {
if (n.right == null) {
// No right subtree, move left subtree (if any) up to replace n.
if (n == root) {
root = n.left;
if (root != null)
root.parent = null;
} else {
if (n.parent.left == n)
n.parent.left = n.left;
else
n.parent.right = n.left;
if (n.left != null)
n.left.parent = n.parent;
}
} else if (n.left == null) {
// No left subtree, move right subtree up to replace n.
if (n == root) {
root = n.right;
root.parent = null;
} else {
if (n.parent.left == n)
n.parent.left = n.right;
else
n.parent.right = n.right;
n.right.parent = n.parent;
}
} else {
// Both children are present, replace n with its successor and
// remove the successor.
Node<T> successor = n.getSuccessor();
n.item = successor.item;
remove(successor);
}
}

public boolean contains(T item) {
if (item == null)
throw new IllegalArgumentException();

if (root == null)
return false;
else
return contains(root, item);
}

private boolean contains(Node<T> n, T item) {
int cmp = n.item.compareTo(item);
if (cmp > 0)
// Search to the left
if (n.left == null)
return false;
else
return contains(n.left, item);
else if (cmp < 0)
// Search to the right
if (n.right == null)
return false;
else
return contains(n.right, item);
else
return true;
}

public int size() {
return size;
}

public void clear() {
size = 0;
root = null;
}

public void hasValidStructure() {
if (root != null) {
assert root.parent == null;
hasValidStructure(root);
}
}

private void hasValidStructure(Node<T> n) {
if (n.left != null) {
assert n.left.item.compareTo(n.item) < 0;
hasValidStructure(n.left);
}
if (n.right != null) {
assert n.right.item.compareTo(n.item) > 0;
hasValidStructure(n.right);
}
}
}

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

private boolean add(Node<T> n, T item) {
int cmp = n.item.compareTo(item);
if (cmp > 0)
// Add child to the left.
if (n.left == null) {
n.left = new Node<T>(item, n);
size++;
return true;
} else{
if(add(n.left, item)){
if(balanceFactor(n) > 1 || balanceFactor(n) < -1)
rebalance(n);
return true;
}
return false;
}
else if (cmp < 0)
// Add child to the right.
if (n.right == null) {
n.right = new Node<T>(item, n);
size++;
return true;
} else{
if(add(n.right, item)){
if(balanceFactor(n) > 1 || balanceFactor(n) < -1)
rebalance(n);
return true;
}
return false;
}
else
return false;
}...
$20.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats