Question
package forestanalyzer; import java.util.ArrayList; import java.util.concurrent.atomic.AtomicBoolean; import java.util.function.Function; public class AVLTree implements AVLTreeAPI { /** * The root node of this tree */ private Node
package forestanalyzer; import java.util.ArrayList; import java.util.concurrent.atomic.AtomicBoolean; import java.util.function.Function;
public class AVLTree
{
/**
* The root node of this tree
*/
private Node root;
/**
* The number of nodes in this tree
*/
private int count;
/**
* A node of a tree stores a data item and references
* to the child nodes to the left and to the right.
*/
private class Node
{
/**
* the data in this node
*/
public E data;
/**
* the left child
*/
public Node left;
/**
* the right child
*/
public Node right;
/**
* the balanced factor of this node
*/
BalancedFactor bal;
}
/**
Constructs an empty tree
*/
public AVLTree()
{
root = null;
count = 0;
}
public boolean isEmpty()
{
return (root == null);
}
public void insert(E obj)
{
Node newNode = new Node();
newNode.bal = BalancedFactor.EH;
newNode.data = obj;
AtomicBoolean forTaller = new AtomicBoolean();
if (!inTree(obj))
count++;
root = insert(root,newNode, forTaller);
}
public boolean inTree(E item)
{
Node tmp;
if (isEmpty())
return false;
/*find where it is */
tmp = root;
while (true)
{
int d = tmp.data.compareTo(item);
if (d == 0)
return true;
else if (d > 0)
{
if (tmp.left == null)
return false;
else
/* continue searching */
tmp = tmp.left;
}
else
{
if (tmp.right == null)
return false;
else
/* continue searching for insertion pt. */
tmp = tmp.right;
}
}
}
public void remove(E item)
{
AtomicBoolean shorter = new AtomicBoolean();
AtomicBoolean success = new AtomicBoolean();
Node newRoot;
if (!inTree(item))
return;
newRoot = remove(root,item, shorter, success);
if (success.get())
{
root = newRoot;
count--;
}
}
public E retrieve(E item) throws AVLTreeException
{
Node tmp;
if (isEmpty())
throw new AVLTreeException("AVL Tree Exception: tree empty on call to retrieve()");
/*find where it is */
tmp = root;
while (true)
{
int d = tmp.data.compareTo(item);
if (d == 0)
return tmp.data;
else if (d > 0)
{
if (tmp.left == null)
throw new AVLTreeException("AVL Tree Exception: key not in tree call to retrieve()");
else
/* continue searching */
tmp = tmp.left;
}
else
{
if (tmp.right == null)
throw new AVLTreeException("AVL Tree Exception: key not in tree call to retrieve()");
else
/* continue searching for insertion pt. */
tmp = tmp.right;
}
}
}
public void traverse(Function func)
{
traverse(root,func);
}
public int size()
{
return count;
}
/*===> BEGIN: Augmented public methods <===*/
/**
* Computes the depth of the specified search key in this tree.
* @param item the search key
* @return the depth of the specified search key if it is in the.
* this tree. If it is not, -1-d, where d is the depth at which
* it would have been found if inserted in the current tree.
*/
public int depth(E item)
{
//implement method
}
/**
* Gives the height of this tree.
* @return the height of this tree
*/
public int height()
{
return height(root);
}
/**
* Computes the diameter, the number of nodes on the longest
* path, in this tree
* @return the diameter of this tree
*/
public int diameter()
{
return diameter(root);
}
/**
* Determines whether or not this AVL tree is perfect.
* @return true if this tree is perfect; otherwise, false
*/
public boolean isPerfect()
{
//Implement this method
}
/**
* Determines whether or not this tree is full
* @return true if this tree is full; otherwise, false
*/
public boolean isFull()
{
return isFull(root);
}
/*===> END: Augmented public methods <===*/
/**
* A enumerated type for the balanced factor of a node
*/
private enum BalancedFactor
{
LH(-1),EH(0),RH(1);
BalancedFactor(int aValue)
{
value = aValue;
}
private int value;
}
/* private methods definitions */
/**
* An auxiliary method that inserts a new node in the tree or
* updates a node if the data is already in the tree.
* @param curRoot a root of a subtree
* @param newNode the new node to be inserted
* @param taller indicates whether the subtree becomes
* taller after the insertion
* @return a reference to the new node
*/
private Node insert(Node curRoot, Node newNode, AtomicBoolean taller)
{
if (curRoot == null)
{
curRoot = newNode;
taller.set(true);
return curRoot;
}
int d = newNode.data.compareTo(curRoot.data);
if (d < 0)
{
curRoot.left = insert(curRoot.left, newNode, taller);
if (taller.get())
switch(curRoot.bal)
{
case LH: // was left-high -- rotate
curRoot = leftBalance(curRoot,taller);
break;
case EH: //was balanced -- now LH
curRoot.bal = BalancedFactor.LH;
break;
case RH: //was right-high -- now EH
curRoot.bal = BalancedFactor.EH;
taller.set(false);
break;
}
return curRoot;
}
else if (d > 0)
{
curRoot.right = insert(curRoot.right,newNode,taller);
if (taller.get())
switch(curRoot.bal)
{
case LH: // was left-high -- now EH
curRoot.bal = BalancedFactor.EH;
taller.set(false);
break;
case EH: // was balance -- now RH
curRoot.bal = BalancedFactor.RH;
break;
case RH: //was right high -- rotate
curRoot = rightBalance(curRoot,taller);
break;
}
return curRoot;
}
else
{
curRoot.data = newNode.data;
taller.set(false);
return curRoot;
}
}
/**
* An auxiliary method that left-balances the specified node
* @param curRoot the node to be left-balanced
* @param taller indicates whether the tree becomes taller
* @return the root of the subtree after left-balancing
*/
private Node leftBalance(Node curRoot, AtomicBoolean taller)
{
Node rightTree;
Node leftTree;
leftTree = curRoot.left;
switch(leftTree.bal)
{
case LH: //left-high -- rotate right
curRoot.bal = BalancedFactor.EH;
leftTree.bal = BalancedFactor.EH;
// Rotate right
curRoot = rotateRight(curRoot);
taller.set(false);
break;
case EH: // This is an error
System.out.println("AVL Tree Error: error in balance tree in call to leftBalance()");
System.exit(1);
break;
case RH: // right-high - requires double rotation: first left, then right
rightTree = leftTree.right;
switch(rightTree.bal)
{
case LH:
curRoot.bal = BalancedFactor.RH;
leftTree.bal = BalancedFactor.EH;
break;
case EH:
curRoot.bal = BalancedFactor.EH;
leftTree.bal = BalancedFactor.EH; /* LH */
break;
case RH:
curRoot.bal = BalancedFactor.EH;
leftTree.bal = BalancedFactor.LH;
break;
}
rightTree.bal = BalancedFactor.EH;
// rotate left
curRoot.left = rotateLeft(leftTree);
//rotate right
curRoot = rotateRight(curRoot);
taller.set(false);
}
return curRoot;
}
/**
* An auxiliary method that right-balances the specified node
* @param curRoot the node to be right-balanced
* @param taller indicates whether the tree becomes taller
* @return the root of the subtree after right-balancing
*/
private Node rightBalance(Node curRoot, AtomicBoolean taller)
{
Node rightTree;
Node leftTree;
rightTree = curRoot.right;
switch(rightTree.bal)
{
case RH: //right-high -- rotate left
curRoot.bal = BalancedFactor.EH;
rightTree.bal = BalancedFactor.EH;
// Rotate left
curRoot = rotateLeft(curRoot);
taller.set(false);
break;
case EH: // This is an error
System.out.println("AVL Tree Error: error in balance tree in call to rightBalance()");
break;
case LH: // left-high - requires double rotation: first right, then left
leftTree = rightTree.left;
switch(leftTree.bal)
{
case RH:
curRoot.bal = BalancedFactor.LH;
rightTree.bal = BalancedFactor.EH;
break;
case EH:
curRoot.bal = BalancedFactor.EH;
rightTree.bal = BalancedFactor.EH; /* RH */
break;
case LH:
curRoot.bal = BalancedFactor.EH;
rightTree.bal = BalancedFactor.RH;
break;
}
leftTree.bal = BalancedFactor.EH;
// rotate right
curRoot.right = rotateRight(rightTree);
//rotate left
curRoot = rotateLeft(curRoot);
taller.set(false);
}
return curRoot;
}
/**
* An auxiliary method that Left-rotates the subtree at this node
* @param node the node at which the left-rotation occurs.
* @return the new node of the subtree after the left-rotation
*/
private Node rotateLeft(Node node)
{
Node tmp;
tmp = node.right;
node.right = tmp.left;
tmp.left = node;
return tmp;
}
/**
* An auxiliary method that right-rotates the subtree at this node
* @param node the node at which the right-rotation occurs.
* @return the new node of the subtree after the right-rotation
*/
private Node rotateRight(Node node)
{
Node tmp;
tmp = node.left;
node.left = tmp.right;
tmp.right = node;
return tmp;
}
/**
* An auxiliary method that in-order traverses the subtree at the specified node
* @param node the root of a subtree
* @param func the function to be applied to the data in each node
*/
private void traverse(Node node, Function func)
{
if (node != null)
{
traverse(node.left,func);
func.apply(node.data);
traverse(node.right,func);
}
}
/**
* An auxiliary method that deletes the specified node from this tree
* @param node the node to be deleted
* @param key the item stored in this node
* @param shorter indicates whether the subtree becomes shorter
* @param success indicates whether the node was successfully deleted
* @return a reference to the deleted node
*/
private Node remove(Node node, E key, AtomicBoolean shorter, AtomicBoolean success)
{
Node delPtr;
Node exchPtr;
Node newRoot;
if (node == null)
{
shorter.set(false);
success.set(false);
return null;
}
int d = key.compareTo(node.data);
if (d < 0)
{
node.left = remove(node.left,key,shorter,success);
if (shorter.get())
node = deleteRightBalance(node,shorter);
}
else if (d > 0)
{
node.right = remove(node.right,key,shorter,success);
if (shorter.get())
node = deleteLeftBalance(node,shorter);
}
else
{
delPtr = node;
if (node.right == null)
{
newRoot = node.left;
success.set(true);
shorter.set(true);
return newRoot;
}
else if(node.left == null)
{
newRoot = node.right;
success.set(true);
shorter.set(true);
return newRoot;
}
else
{
exchPtr = node.left;
while(exchPtr.right != null)
exchPtr = exchPtr.right;
node.data = exchPtr.data;
node.left = remove(node.left,exchPtr.data,shorter,success);
if (shorter.get())
node = deleteRightBalance(node,shorter);
}
}
return node;
}
/**
* An auxiliary method that right-balances this subtree after a deletion
* @param node the node to be right-balanced
* @param shorter indicates whether the subtree becomes shorter
* @return a reference to the root of the subtree after right-balancing.
*/
private Node deleteRightBalance(Node node, AtomicBoolean shorter)
{
Node rightTree;
Node leftTree;
switch(node.bal)
{
case LH: //deleted left -- now balanced
node.bal = BalancedFactor.EH;
break;
case EH: //now right high
node.bal = BalancedFactor.RH;
shorter.set(false);
break;
case RH: // right high -- rotate left
rightTree = node.right;
if (rightTree.bal == BalancedFactor.LH)
{
leftTree = rightTree.left;
switch(leftTree.bal)
{
case LH:
rightTree.bal = BalancedFactor.RH;
node.bal = BalancedFactor.EH;
break;
case EH:
node.bal = BalancedFactor.EH;
rightTree.bal = BalancedFactor.EH;
break;
case RH:
node.bal = BalancedFactor.LH;
rightTree.bal = BalancedFactor.EH;
break;
}
leftTree.bal = BalancedFactor.EH;
//rotate right, then left
node.right = rotateRight(rightTree);
node = rotateLeft(node);
}
else
{
switch(rightTree.bal)
{
case LH:
case RH:
node.bal = BalancedFactor.EH;
rightTree.bal = BalancedFactor.EH;
break;
case EH:
node.bal = BalancedFactor.RH;
rightTree.bal = BalancedFactor.LH;
shorter.set(false);
break;
}
node = rotateLeft(node);
}
}
return node;
}
/**
* An auxiliary method that left-balances this subtree after a deletion
* @param node the node to be left-balanced
* @param shorter indicates whether the subtree becomes shorter
* @return a reference to the root of the subtree after left-balancing.
*/
private Node deleteLeftBalance(Node node, AtomicBoolean shorter)
{
Node rightTree;
Node leftTree;
switch(node.bal)
{
case RH: //deleted right -- now balanced
node.bal = BalancedFactor.EH;
break;
case EH: //now left high
node.bal = BalancedFactor.LH;
shorter.set(false);
break;
case LH: // left high -- rotate right
leftTree = node.left;
if (leftTree.bal == BalancedFactor.RH)
{
rightTree = leftTree.right;
switch(rightTree.bal)
{
case RH:
leftTree.bal = BalancedFactor.LH;
node.bal = BalancedFactor.EH;
break;
case EH:
node.bal = BalancedFactor.EH;
leftTree.bal = BalancedFactor.EH;
break;
case LH:
node.bal = BalancedFactor.RH;
leftTree.bal = BalancedFactor.EH;
break;
}
rightTree.bal = BalancedFactor.EH;
//rotate left, then right
node.left = rotateLeft(leftTree);
node = rotateRight(node);
}
else
{
switch(leftTree.bal)
{
case RH:
case LH:
node.bal = BalancedFactor.EH;
leftTree.bal = BalancedFactor.EH;
break;
case EH:
node.bal = BalancedFactor.LH;
leftTree.bal = BalancedFactor.RH;
shorter.set(false);
break;
}
node = rotateRight(node);
}
}
return node;
}
/* BEGIN: Augmented Private Auxiliary Methods */
/**
* Recursively computes the height of the subtree
* rooted at the specified node
* @param node the root of a subtree
* @return the height of the subtree rooted at the
* specified node
*/
private int height(Node node)
{
if (node == null)
return 0;
int leftHeight = height (node.left);
int rightHeight = height (node.right);
if (rightHeight > leftHeight)
return 1 + rightHeight;
else
return 1 + leftHeight;
}
/**
* Recursively determines the diameter, the number of nodes on
* the longest path, of the subtree rooted at the specified node
* @param node the root of the specified subtree
* @return the diameter of the tree rooted at the specified node
*/
private int diameter(Node node)
{
}
/**
* Recursively determines whether the subtree rooted at the
* specified node is perfect.
* @param node the root of a subtree
* @param index the zero-based level-order index of this node
* @return true if the tree root at the specified node is perfect;
* otherwise, false
*/
private boolean isPerfect(Node node, int index)
{
//Implement this method
}
/**
* Recursively determines whether the subtree rooted at the specified node
* is full
* @param node the root of a subtree of this tree
* @return true if the subtree rooted at the specified node is full; otherwise, false
*/
private boolean isFull(Node node)
{
if(node == null)
return true;
if(node.left == null && node.right == null )
return true;
if((node.left!=null) && (node.right!=null))
return (isFull(node.left) && isFull(node.right));
return false;
}
/* END: Augmented Private Auxiliary Methods */
}
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