Enhance the BST class with the following methods for doing experiments of balanc
ID: 641437 • Letter: E
Question
Enhance the BST class with the following methods for doing experiments of balancing binary search trees.
treeHeight, calculates tree height;
nodeBalanceLevel calculates the balance level of a given node as the difference between the height of its left subtree and the height of its right subtree;
numberOfNodesAtLevel calculates the number of nodes at the specified level;
calculateACE, calculates the ACE value according to the above algorithm;
calculateMinACE, calculates the minimum value of the ACE;
calculateMaxACE, calculates the maximum value of the ACE;
needsBalancing, evaluates whether this BST needs to be balanced or not. We consider that a BST needs to be balanced when its ACE value is greater than K * MinASE where K = 1.25;
balanceBST, executes the balance operation on this BST;
Additional methods may be added if necessary.
class BST<E extends Comparable<E>> {
protected TreeNode<E> root;
protected int size = 0;
/** Create a default binary tree */
public BST() {
}
/** Create a binary tree from an array of objects */
public BST(E[] objects) {
for (int i = 0; i < objects.length; i++)
insert(objects[i]);
}
/** Returns true if the element is in the tree */
public boolean search(E e) {
TreeNode<E> current = root; // Start from the root
while (current != null) {
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else // element matches current.element
return true; // Element is found
}
return false;
}
/** Insert element o into the binary tree
* Return true if the element is inserted successfully */
public boolean insert(E e) {
if (root == null)
root = createNewNode(e); // Create a new root
else {
// Locate the parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null)
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
return false; // Duplicate node not inserted
// Create the new node and attach it to the parent node
if (e.compareTo(parent.element) < 0)
parent.left = createNewNode(e);
else
parent.right = createNewNode(e);
}
size++;
return true; // Element inserted
}
protected TreeNode<E> createNewNode(E e) {
return new TreeNode<E>(e);
}
/** Inorder traversal from the root*/
public void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
protected void inorder(TreeNode<E> root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}
/** Postorder traversal from the root */
public void postorder() {
postorder(root);
}
/** Postorder traversal from a subtree */
protected void postorder(TreeNode<E> root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}
/** Preorder traversal from the root */
public void preorder() {
preorder(root);
}
/** Preorder traversal from a subtree */
protected void preorder(TreeNode<E> root) {
if (root == null) return;
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);
}
/** This inner class is static, because it does not access
any instance members defined in its outer class */
public static class TreeNode<E extends Comparable<E>> {
protected E element;
protected TreeNode<E> left;
protected TreeNode<E> right;
public TreeNode(E e) {
element = e;
}
}
/** Get the number of nodes in the tree */
public int getSize() {
return size;
}
/** Returns the root of the tree */
public TreeNode<E> getRoot() {
return root;
}
/** Returns a path from the root leading to the specified element */
public java.util.ArrayList<TreeNode<E>> path(E e) {
java.util.ArrayList<TreeNode<E>> list =
new java.util.ArrayList<TreeNode<E>>();
TreeNode<E> current = root; // Start from the root
while (current != null) {
list.add(current); // Add the node to the list
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else
break;
}
return list; // Return an array of nodes
}
/** Delete an element from the binary tree.
* Return true if the element is deleted successfully
* Return false if the element is not in the tree */
public boolean delete(E e) {
// Locate the node to be deleted and also locate its parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null) {
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
break; // Element is in the tree pointed at by current
}
if (current == null)
return false; // Element is not in the tree
// Case 1: current has no left children
if (current.left == null) {
// Connect the parent with the right child of the current node
if (parent == null) {
root = current.right;
}
else {
if (e.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
}
}
else {
// Case 2: The current node has a left child
// Locate the rightmost node in the left subtree of
// the current node and also its parent
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // Keep going to the right
}
// Replace the element in current by the element in rightMost
current.element = rightMost.element;
// Eliminate rightmost node
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
// Special case: parentOfRightMost == current
parentOfRightMost.left = rightMost.left;
}
size--;
return true; // Element inserted
}
/** Obtain an iterator. Use inorder. */
public java.util.Iterator<E> iterator() {
return new InorderIterator();
}
// Inner class InorderIterator
private class InorderIterator implements java.util.Iterator<E> {
// Store the elements in a list
private java.util.ArrayList<E> list =
new java.util.ArrayList<E>();
private int current = 0; // Point to the current element in list
public InorderIterator() {
inorder(); // Traverse binary tree and store elements in list
}
/** Inorder traversal from the root*/
private void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
private void inorder(TreeNode<E> root) {
if (root == null)return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
/** More elements for traversing? */
public boolean hasNext() {
if (current < list.size())
return true;
return false;
}
/** Get the current element and move to the next */
public E next() {
return list.get(current++);
}
/** Remove the current element */
public void remove() {
delete(list.get(current)); // Delete the current element
list.clear(); // Clear the list
inorder(); // Rebuild the list
}
}
/** Remove all elements from the tree */
public void clear() {
root = null;
size = 0;
}
}
Afterwards, create a driver program that will build an initial BST whose nodes contain positive integer values taken from an input file. In the input file, the values should be separated by the semicolon character. After building the BST, in a loop, the program should invite the user to select for execution one of the following operations: (1) in-order tree traversal, (2) pre-order tree traversal, (3) calculateACE, (4) calculateMinACE, (5) calculateMaxACE, (6) numberOfNodesAllLevels (this operation displays the number of nodes at each level of the tree), (7) treeHeight, (8) nodeBalanceLevel (9) needsBalancing, (10) balanceBST, (11) insert value, and (0) exit the loop and the program. As a result of each operation execution, relevant information will be displayed to the user.
Sample Text File
john;peter;mary;susan;george;debbie;tom;bill;
#
0 1 2
1 0 2
2 0 1 3 4 6
3 2 4 5
4 2 3
5 3 6
6 2 5 7
7 6
Explanation / Answer
Hey i can help you with this. Contact me on hunain60 at gmail
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.