Question: So, I am currently working on Chapter 22 Programming Challenge 1. It asks me to add a remove method to the AVLTree class that was
So, I am currently working on Chapter 22 Programming Challenge 1. It asks me to add a remove method to the AVLTree class that was discussed in the chapter of the textbook, Starting out with Java (3rd edition). Then use a graphical user interface to allow the user to add and remove items of their own desire. The GUI is already part of the AVL Tree class in the book, all i need is to add a remove method in the AVLTree class. I need to use the remove method from the binary search tree class for the AVLTree class in the textbook. But, I need to modify the remove method in order for the tree to stay balance. Please help. Here are some photos of the AVLTree class. I hope this helps.
Down here photos of the binary search tree class with the remove methods.
Now, I need to find a way to modify the remove method from the binary search tree class in the AVLTree class, so it can be balanced.
public class AVLTree extends BinaryTree
{
// Convenience method casts the inherited root
// from Node to AVLNode.
private AVLNode getRoot()
{
return (AVLNode) root;
}
/**
* The getHeight method computes the height of an AVL tree.
* @param tree An AVL tree.
* @return The height of the AVL tree.
*/
static int getHeight(AVLNode tree)
{
if (tree == null)
return -1;
else
return tree.height;
}
/**
* The add method adds a value to this AVL tree.
* @param x The value to add.
* @return true.
*/
public boolean add(int x)
{
root = add((AVLNode) root, x);
return true;
}
/**
* The add method adds a value to an AVL tree.
* @return The root of the augmented AVL tree.
*/
private AVLNode add(AVLNode bTree, int x)
{
if (bTree == null)
{
return new AVLNode(x);
}
if (x
{
bTree.left = add(bTree.getLeft(), x);
} else
{
bTree.right = add(bTree.getRight(), x);
}
// Compute heights of the left and right subtrees
// and rebalance the tree if needed.
int leftHeight = getHeight(bTree.getLeft());
int rightHeight = getHeight(bTree.getRight());
if (Math.abs(leftHeight - rightHeight) == 2)
{
return balance(bTree);
} else
{
bTree.resetHeight();
return bTree;
}
}
private class RemovalProcess
{
Node node; // Removed node
Node tree; // Remaining tree
RemovalProcess(Node node, Node tree)
{
this.node = node;
this.tree = tree;
}
}
public boolean remove(int x)
{
RemovalProcess process = remove((AVLNode) root, x);
if (process == null)
{
return false;
}else
{
}
}
/**
* The balance method rebalances an AVL tree.
* @param bTree The AVL tree needing to be balanced.
* @return The balanced AVL tree.
*/
private AVLNode balance(AVLNode bTree)
{
// Balance the left and right height of the subtrees.
int rHeight = getHeight(bTree.getRight());
int lHeight = getHeight(bTree.getLeft());
if (rHeight > lHeight)
{
AVLNode rightChild = bTree.getRight();
int rrHeight = getHeight(rightChild.getRight());
int rlHeight = getHeight(rightChild.getLeft());
if (rrHeight > rlHeight)
{
return rrBalance(bTree);
} else
{
return rlBalance(bTree);
}
} else
{
AVLNode leftChild = bTree.getLeft();
int llHeight = getHeight(leftChild.getLeft());
int lrHeight = getHeight(leftChild.getRight());
if (llHeight > lrHeight)
{
return llBalance(bTree);
} else
{
return lrBalance(bTree);
}
}
}
/**
* The rrBlance method corrects an RR imbalance.
* @param bTree The AVL tree wih an RR imbalance.
* @return The balanced AVL tree.
*/
private AVLNode rrBalance(AVLNode bTree)
{
AVLNode rightChild = bTree.getRight();
AVLNode rightLeftChild = rightChild.getLeft();
rightChild.left = bTree;
bTree.right = rightLeftChild;
bTree.resetHeight();
rightChild.resetHeight();
return rightChild;
}
/**
* The rlBalance method corrects an RL imbalance.
* @parame bTree The AVL tree with an RL imbalance.
* @return The balanced AVL tree.
*/
private AVLNode rlBalance(AVLNode bTree)
{
AVLNode root = bTree;
AVLNode rNode = root.getRight();
AVLNode rlNode = rNode.getLeft();
AVLNode rlrTree = rlNode.getRight();
AVLNode rllTree = rlNode.getLeft();
// Build the restructured tree.
rNode.left = rlrTree;
root.right = rllTree;
rlNode.left = root;
rlNode.right = rNode;
// Adjust heights.
rNode.resetHeight();
root.resetHeight();
rlNode.resetHeight();
return rlNode;
}
/**
* The llBalance method corrects an LL imbalance.
* @param bTree The AVL tree with an LL imbalance.
* @return The balanced AVL tree.
*/
private AVLNode llBalance(AVLNode bTree)
{
AVLNode leftChild = bTree.getLeft();
AVLNode lrTree = leftChild.getRight();
leftChild.right = bTree;
bTree.left = lrTree;
bTree.resetHeight();
leftChild.resetHeight();
return leftChild;
}
/**
* The lrBalance method corrects an LR imbalance.
* @param bTree The AVL tree with an LR imbalance.
* @return The balanced AVL tree.
*/
private AVLNode lrBalance(AVLNode bTree)
{
AVLNode root = bTree;
AVLNode lNode = root.getLeft();
AVLNode lrNode = lNode.getRight();
AVLNode lrlTree = lrNode.getLeft();
AVLNode lrrTree = lrNode.getRight();
// Build the restructured tree.
lNode.right = lrlTree;
root.left = lrrTree;
lrNode.left = lNode;
lrNode.right = root;
// Adjust heights.
lNode.resetHeight();
root.resetHeight();
lrNode.resetHeight();
return lrNode;
}
}
BinanySearchTree.javaAVLTreejava X3 13 */ 15 public class AVLTree extends BinaryTree 16 17 18 // Convenience method casts the inherited root // from Node to AVLNode 0 19 private AVLNode getRoot 20 21 return (AVLNode) root; 23 24 /** 25 26 27 28 29 static int getHeight (AVLNode tree) 30 31 32 * The getHeight method computes the height of an AVL tree. aram tree An AVL tree. * return The height of the AVL tree. if (tree-null) return -1; else return tree.height; 34 35 36 * The add method adds a value to this AVL tree. * @param x The value 38 39 40 41 42 43 public boolean add (int x) to add return true. x); add ( (AVLNode) true; 45 46 47 48 49/** 50 51 52 53 54 private AVLNode add (AVLNode bTree, int x) root = return root, * The add method adds a value to an AVL tree. * return The root of the augmented AVL tree. if (bTree == null) 56 57 58 59 return new AVLNode (x)
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help