In a Java AVL tree class, some functions below are given. Question : how to comp

Question

In a Java AVL tree class, some functions below are given.

Question : how to compile

/////////////////////////////////////

// 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)
{
// to be completed
return false;
}
/////////////////////////////////////////////////
// removes all items in the tree
public void RemoveAll()
{
// to be completed
}

////////////////////////////////////////

these code below are given, but the are not tested. but I expect most of them are correct

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);}
       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.element) > 0) {
       nd.right = Remove(item,nd.right);
       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;
  
   if(Insert(root.left, item) != 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)
{
// to be completed
return false;
}
  
// removes all items in the tree
public void RemoveAll()
{
// 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

There is no main function provided in your code. And you have not said anything about execution this class.

I have corrected the errors in your code. Please find the changed code below. The compilation works perfect.

To Compile:

Please go to the path where this java file is present. and simply execute the below command for compilation.

> javac AVLTree.java

CODE:

AVLTree.java

package temp;

class AVLNode implements Comparable<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);
   }

   @Override
   public int compareTo(AVLNode arg0) {
       // TODO Auto-generated method stub
       return 0;
   }
}

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);}
   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((AVLNode) item,nd.right);
               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 Predr = null;
   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;
   }
   Predr = t.data;
   }
   }
   return (AVLNode) Predr;
   }
  
   // 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;
  
   if(Insert(root.left, item) != 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)
   {
   // to be completed
   return false;
   }
  
   // removes all items in the tree
   public void RemoveAll()
   {
   // 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;
   }
   }
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.