I have a question about Java AVL tree class... I have two insert functions---->
ID: 3864641 • Letter: I
Question
I have a question about Java AVL tree class...
I have two insert functions----> (1) private AVLNode Insert(AVLNode nd, Comparable item) (2)public boolean Insert(Comparable item) which returns true if the insertion is done successfully.
but when I run the main function some exceptions appeared. can you help me to fix it? thx!
and here are the main funtion and the avl tree code.
/////////////////////////main()/////////////////////////////
import java.util.Random;
public class A4driver {
public static void main(String[] args)
{
System.out.println("Entering Test1:...");
Test1();
System.out.println("Entering Test2:...");
// Test2();
}
public static void Test1()
{
Random r = new Random();
int maxvalue = 50;
int numitemstoinsert = 15;
AVLTree treeA = new AVLTree();
for (int i = 0; i < numitemstoinsert; i++)
{
treeA.Insert(new Integer(r.nextInt(maxvalue)));
}
System.out.println("Tree A:");
System.out.println(treeA.PrintTree());
System.out.println("Tree contains " + treeA.Size() + " items.");
System.out.println("Tree height: " + treeA.Height());
int numitemstoremove = 5;
System.out.println(" Attempting to remove " + numitemstoremove + " items...");
for (int j = 0; j < numitemstoremove; j++)
{
int value = r.nextInt(maxvalue);
System.out.print("Remove " + value + ": ");
if (treeA.Remove(new Integer(value)))
System.out.println("success!");
else
System.out.println("failed.");
}
System.out.println("Tree A:");
System.out.println(treeA.PrintTree());
System.out.println("Tree contains " + treeA.Size() + " items.");
System.out.println("Tree height: " + treeA.Height());
int numitemstofind = 3;
System.out.println("Searching for " + numitemstofind + " item...");
for (int k = 0; k < numitemstofind; k++)
{
int searchkey = r.nextInt(maxvalue);
System.out.println("Tree contains " + searchkey + ": " + treeA.Contains(searchkey));
}
System.out.println("Creating tree B as a copy of tree A...");
AVLTree treeB = new AVLTree(treeA);
System.out.println(" Removing all elements of tree A...");
treeA.RemoveAll();
System.out.println("Tree A:");
System.out.println(treeA.PrintTree());
System.out.println("Tree A contains " + treeA.Size() + " items.");
System.out.println("Tree A height: " + treeA.Height());
System.out.println("Tree B:");
System.out.println(treeB.PrintTree());
System.out.println("Tree B contains " + treeB.Size() + " items.");
System.out.println("Tree B height: " + treeB.Height());
}
// public static void Test2()
// {
// // add your own testing code here
//
// }
}
////////////avl tree/////////////////////
class AVLNode
{
public Comparable data;
public AVLNode left;
public AVLNode right;
public int height;
// default constructor
public AVLNode(Comparable value)
{
data = value;
left = null;
right = null;
height = 0;
}
// parameterized constructor
public AVLNode(Comparable value, AVLNode left1, AVLNode right1)
{
data = value;
left = left1;
right = right1;
height = 0;
}
// The ResetHeight method recomputes height if the
// left or right subtrees have changed.
void ResetHeight()
{
int leftheight = -1;
int rightheight = -1;
if (left != null)
leftheight = left.height;
if (right != null)
rightheight = right.height;
height = 1 + Math.max(leftheight, rightheight);
}
}
public class AVLTree {
// member attributes
private AVLNode root;
private int size;
// private methods
// recursive helper function for deep copy
// creates a new node based on sourcend's contents,
// recurses to create left and right children.
// returns a reference to the newly created node.
// The new tree should have the same structure as the source tree
private AVLNode CopyNode(AVLNode sourcend)
{
AVLNode left = null;
AVLNode right = null;
if (sourcend.left != null) {
left = CopyNode(sourcend.left);//copying left subtree
}
if (sourcend.right != null) {
right = CopyNode(sourcend.right);//copying right subtree
}
//creating new node...
return new AVLNode(sourcend.data, left, right);
}
// recursive insertion
// returns the root of the augmented tree
// (nd may or may not have been rotated)
// Performs ordinary (recursive) BST insertion,
// then computes left/right subtree heights and
// rebalance if necessary, otherwise reset nd's
// height and return.
// Does not affect size of the tree.
private AVLNode Insert(AVLNode nd, Comparable item)
{
if (nd == null)
return new AVLNode(item);
else if (item.compareTo (nd.data)<0)
nd.left = Insert(nd.left, item);
else
nd.right = Insert(nd.right, item);
// compute left/right heights and rebalance if needed
int lheight = nd.left.height;
int rheight = nd.right.height;
if (Math.abs(lheight - rheight) == 2)
return Balance(nd);
else {
nd.ResetHeight();
return nd;
}
}
// to be completed
// recursive remove
// returns root of the supplied (possibly rebalanced) tree
// with the key value removed (if found)
// return null if not found
private AVLNode Remove(AVLNode nd, Comparable item)
{
if (item==null) {
System.out.println("Node to be deleted, doesn't exist in this tree");
return null;
}
if (item.compareTo(nd.data) < 0 ) {
nd.left = Remove(nd.left, item);
int l = nd.left != null ? nd.left.height : 0;
if((nd.right != null) && (nd.right.height - l >= 2)) {
int rightHeight = nd.right.right != null ? nd.right.right.height : 0;
int leftHeight = nd.right.left != null ? nd.right.left.height : 0;
if(rightHeight >= leftHeight)
nd = LLBalance(nd);
else
nd = LRBalance(nd);
}
}
else if (item.compareTo(nd.data) > 0) {
nd.right = Remove(nd.right,item);
int r = nd.right != null ? nd.right.height : 0;
if((nd.left != null) && (nd.left.height - r >= 2)) {
int leftHeight = nd.left.left != null ? nd.left.left.height : 0;
int rightHeight = nd.left.right != null ? nd.left.right.height : 0;
if(leftHeight >= rightHeight)
nd = RRBalance(nd);
else
nd = RLBalance(nd);
}
}
return nd;
}
// Finds and returns the predecessor of the supplied subtree root node
private AVLNode Predecessor(AVLNode nd)
{
Comparable Predecessor;
if (nd!= null)
{ // go to the right most element in the left subtree, it will the
// predecessor.
if (nd.left != null)
{
AVLNode t = nd.left;
while (t.right != null)
{
t = t.right;
}
Predecessor = t.data;
}
}
return Predecessor;}
// Rebalances an AVL tree, returns the root of the balanced
// tree (formerly rooted at nd)
private AVLNode Balance(AVLNode nd)
{
int lheight = -1;
if (nd.left != null) lheight = nd.left.height;
int rheight = -1;
if (nd.right != null) rheight = nd.right.height;
if (rheight > lheight)
{
AVLNode rchild = nd.right;
int rrheight = -1;
if (rchild.right != null) rrheight = rchild.right.height;
int rlheight = -1;
if (rchild.left != null) rlheight = rchild.left.height;
if (rrheight > rlheight)
return RRBalance(nd);
else
return RLBalance(nd);
}
else
{
AVLNode lchild = nd.left;
int llheight = -1;
if (lchild.left != null) llheight = lchild.left.height;
int lrheight = -1;
if (lchild.right != null) lrheight = lchild.right.height;
if (llheight > lrheight)
return LLBalance(nd);
else
return LRBalance(nd);
}
}
// corrects an RR imbalance rooted at nd
// returns the balanced AVL tree
private AVLNode RRBalance(AVLNode nd)
{
AVLNode rchild = nd.right;
AVLNode rlchild = rchild.left;
rchild.left = nd;
nd.right = rlchild;
nd.ResetHeight();
rchild.ResetHeight();
return rchild;
}
//corrects an RL imbalance rooted at nd
// returns the balanced AVL tree
private AVLNode RLBalance(AVLNode nd)
{
AVLNode subroot = nd;
AVLNode rnode = subroot.right;
AVLNode rlnode = rnode.left;
AVLNode rlrtree = rlnode.right;
AVLNode rlltree = rlnode.left;
// build the restructured tree
rnode.left = rlrtree;
subroot.right = rlltree;
rlnode.left = subroot;
rlnode.right = rnode;
// adjust heights
rnode.ResetHeight();
subroot.ResetHeight();
rlnode.ResetHeight();
return rlnode;
}
// corrects an LL imbalance rooted at nd
// returns the balanced AVL tree
private AVLNode LLBalance(AVLNode nd)
{
AVLNode lchild = nd.left;
AVLNode lrchild = lchild.right;
lchild.right = nd;
nd.left = lrchild;
nd.ResetHeight();
lchild.ResetHeight();
return lchild;
}
//corrects an LR imbalance rooted at nd
// returns the balanced AVL tree
private AVLNode LRBalance(AVLNode nd)
{
AVLNode subroot = nd;
AVLNode lnode = subroot.left;
AVLNode lrnode = lnode.right;
AVLNode lrltree = lrnode.left;
AVLNode lrrtree = lrnode.right;
// build the restructured tree
lnode.right = lrltree;
subroot.left = lrrtree;
lrnode.left = lnode;
lrnode.right = subroot;
// adjust heights
lnode.ResetHeight();
subroot.ResetHeight();
lrnode.ResetHeight();
return lrnode;
}
// default constructor
public AVLTree()
{
root = null;
size = 0;
}
// copy constructor
public AVLTree(AVLTree tree)
{
// to be completed
// should set member attributes and perform deep copy
}
// gets the number of items in the tree
public int Size()
{
return size;
}
// gets the height of the tree (root)
public int Height()
{
if (root == null) return -1;
return root.height;
}
// searches the tree for a key
public Boolean Contains(Comparable item)
{
// to be completed
return false;
}
// Inserts an item into the tree.
public boolean Insert(Comparable item)
{
boolean result = false;
root = Insert(root, item);
AVLNode n = root;
if(n != null) {
result = true;
}
return result;
}
// Removes an item from the tree.
// Returns true if the item is successfully removed
// Returns false if the item cannot be removed (i.e. not found)
public boolean Remove(Comparable item)
{
root = Remove(root,item);
// to be completed
return false;
}
// removes all items in the tree
public void RemoveAll()
{
root=null;
// to be completed
}
// returns a formatted string, reverse in-order traversal
// (as done in lab 5)
public String PrintTree()
{
return PrintTree(root, 0, new StringBuilder()).toString();
}
// recursive helper for PrintTree
private StringBuilder PrintTree(AVLNode nd, int level, StringBuilder tree)
{
if (nd == null)
{
return tree;
}
else
{
PrintTree(nd.right, 1+level, tree);
for (int i = 0; i < level; i++)
{
tree.append(" ");
}
tree.append(nd.data + " ");
PrintTree(nd.left, 1+level, tree);
return tree;
}
}
}
Explanation / Answer
The problem is in Predecessor function. if you comment that function the program work with runtime error meanig that the value of predecessor is needed. So to use the function you need to do the type casting of the Predecessor variable into ObjectType.
This is how it works
so please do the changes accordingly
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.