Question

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 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;
}...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Related Homework Solutions

Airplane Seating Chart System Simulation in Java
Homework Solution
$30.00
Java
Programming
Codes
Computer Science
Algorithms
Airplane Seating Chart
Simulation
Tickets
Seats
Diagrams
Coordinates
Customers
Passengers
Methods
Statements
Variables
Pyramid Using Asterisks in Java
Homework Solution
$30.00
Java
Programming
Codes
Algorithms
Computer Science
Statements
Variables
Loops
Input
Output
Integers
Strings
Asterisks
Symbols
Pyramid
Rows
Odd Numbers
Java Programming: Strings, Odd & Even Numbers, Absolute Values
Homework Solution
$25.00
Java
Programming
Computer Science
Odd Numbers
Even Numbers
Integers
Absolute Values
While Loop
IF-Statements
Data Sets
Input
Output
Sum
Functions
Methods
Strings
Lexicography Order
Java Programming: User Defined Company
Homework Solution
$40.00
Java
Programming
Computer Science
Company
Stock Symbol
Stock Value
Constructor
Methods
Strings
Variables
Business
Finance
Economy
Hardware
Software
Arrays
Lists
Java Programming Problems
Homework Solution
$30.00
Java
Programming
Computer Science
Arrays
Fractions
Variables
Strings
Numerator
Denominator
Statements
Constructor
Object
Initialization
Get help from a qualified tutor
Live Chats