***Code needs to be done in java*** Rebalancing a Binary Search Tree Your task i
ID: 3555576 • Letter: #
Question
***Code needs to be done in java***
Rebalancing a Binary Search Tree
Your task is to write a class RebalancingTree that extends the attached BST class. You should override the insert method in BST. Your overriding method should first call the method it is overriding. When 50 insertions have been performed since the last rebalancing, the tree should be examined to find the node with the highest balance factor. If there is more than one such node, always choose one that is the shallowest in the tree. You should then rebalance the subtree rooted at that node. Your rebalancing should produce a balanced subtree.
Each time a rebalancing occurs, you should display the following information:
Your test method should create a balanced binary search tree of integers and then randomly generate 1,000 integers between 0 and 999 and insert them into the tree. After all the insertions are complete, use the inorder iterator to produce a list of values in the tree and verify that it is in sorted order to ensure that your rebalancing operations were performed correctly.
Submission Instructions
In addition to your .java source files, you should submit a short document containing a short discussion of the algorithm that you used for determining the node with the highest balance factor, and the algorithm that you used to rebalance the subtree. Also provide the formulas you used to compute the other information that was displayed upon rebalancing. Submit all files as attachments to the assignment area. Remember to include the package statement in your Java source file(s) where the package name is your last name in lower case letters. The document can be in any format you find convenient.
Hints:
Most operations on binary trees can be done more simply and more naturally using recursion and that is the case with this project. In fact, most binary tree operations are based on one of the three traversals. If you need to determine and pass up values from a node's children before you can determine the value at the current node, then you use a postorder traversal. If you need to pass values down the tree, then you use a preorder traversal. If you need to process the nodes in sorted order, then you use an inorder traversal. In this project, I used all three traversals! -- and a fourth recursive method.
When finding the node with the greatest balance factor, you sometimes need to use a node's depth as a tie breaker. Hence, you need to determine each node's depth prior to finding the greatest balance factor. You can easily determine each node's depth as part of the method that also determines the sum of each node's depth (add a depth field to the class for a tree node). The greatest balance factor can be determined as part of the same method that determines the height of the tree.
--------------------------------------------------------------------------------------------------------------------------------
You want to identify the node whose balance factor (absolute value) is greatest. The balance factor of a node is the difference in the heighths of its left and right subtrees. So you also need to determine the heighths of the various nodes (you also need to print out the height of the entire tree). To determine the height of a node and to determine its balance factor, you first need to determine the heighths of the left and right subtrees. Hence, you can base this on a postorder traversal. In the visit step, you calculate and return the height of the node -- the height is one more than the larger heighth of its left and right subtrees. In the visit step, you can also determine the node's balance factor -- it is the difference in the heighths of its left and right subtrees. If the absolute value of the balance factor is bigger than the largest so far, then you update the maximum balance factor and the corresponding node (you can use class fields for the maximum balance factor and the corresponding node).
Thinking of a good way to balance an arbitrary subtree seems to be the hardest part of the project. Suppose you have a collection of nodes. Which one would be a good choice to pick as the root node? Ideally, you would like the number of nodes in the left and right subtrees to be same. What node would this be? The one that occurs in the middle of a sorted list. What nodes would be good choices for this node's left and right children? By the same reasoning, the node that is in the middle of the nodes that are < the root and
the node that is in the middle of the nodes that are > the root. This suggests that it might be good to first obtain a sorted list of the nodes. So we can use a two-step process.
(1) Make a sorted list of all the nodes in the subtree rooted at the node with the maximum balance factor.
(2) Convert the list into a tree. Pick the middle node as the root and recursively set its left and right children to the middle of the left and right halves of the list.
Code for BST.java (Binary search tree class):
import java.util.ArrayList;
import java.util.Iterator;
//+-------------------------------------------------------------------+
//| Class for a generic binary search tree without duplicate elements |
//+-------------------------------------------------------------------+
public class BST<E extends Comparable<E>>
{
//+-------------------------------------+
//| inner class for a generic tree node |
//+-------------------------------------+
protected static class Node<E extends Comparable<E>>
{
public E data; // the data item
public Node<E> left; // the left sub-tree
public Node<E> right; // the right sub-tree
public Node( E e ) // node constructor
{
left = null;
data = e;
right = null;
}
}
protected Node<E> root; // the root of the tree
protected int size = 0; // the number of nodes in the tree
private boolean inserted; // for insertion return -- true if inserted
//+----------------------+
//| create an empty tree |
//+----------------------+
public BST() { root = null; }
//+-----------------------------------------+
//| create a tree from an array of elements |
//+-----------------------------------------+
public BST( E[] objects )
{
for (int i = 0; i < objects.length; i++)
insert( objects[i] );
}
//+---------------------------------------------+
//| returns true iff the element is in the tree |
//+---------------------------------------------+
public boolean find( E e )
{
Node<E> current = root; // Start from the root
while (current != null)
{
if (e.compareTo( current.data ) < 0)
current = current.left;
else if (e.compareTo( current.data ) > 0)
current = current.right;
else // data matches current.data
return true; // Data is found
}
return false;
}
//+-----------------------------------------------------+
//| returns true if the element was inserted, and |
//| returns false if the element is already in the tree |
//+-----------------------------------------------------+
public boolean insert( E data )
{
inserted = false;
root = insert( root, data );
if (inserted) size++;
return inserted;
}
private Node<E> insert( Node<E> node, E data )
{
if (node == null)
{
inserted = true;
return new Node<>( data );
}
if (data.compareTo( node.data ) < 0)
node.left = insert( node.left, data );
else if (data.compareTo( node.data ) > 0)
node.right = insert( node.right, data );
return node;
}
//+----------------------------------------------+
//| returns true if the element was deleted |
//| returns false if the data is not in the tree |
//+----------------------------------------------+
public boolean delete( E e )
{
// Find the node and its parent
// ----------------------------
Node<E> parent = null;
Node<E> current = root;
while (current != null)
{
if (e.compareTo( current.data ) < 0)
{
parent = current;
current = current.left;
}
else if (e.compareTo( current.data ) > 0)
{
parent = current;
current = current.right;
}
else
break; // Data is in the tree pointed at by current
}
if (current == null) return false; // Data is not in the tree
// Case 1: node has no left child
// ------------------------------
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.data ) < 0)
parent.left = current.right;
else
parent.right = current.right;
}
}
else {
// Case 2: The node has a left child -- replace data in the
// node with that in the rightmost node in the left subtree
// ------------------------------------------------
Node<E> parentOfRightMost = current;
Node<E> rightMost = current.left; // step to left subtree
while (rightMost.right != null) // go right as far as possible
{
parentOfRightMost = rightMost;
rightMost = rightMost.right;
}
// Replace the data in current by the data in rightMost
// ----------------------------------------------------
current.data = rightMost.data;
// Eliminate rightmost node
// ------------------------
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
// Special case: parentOfRightMost == current
parentOfRightMost.left = rightMost.left;
}
size--; // decrement size
return true; // node was deleted
}
//+------------------------------+
//| Returns the root of the tree |
//+------------------------------+
public Node<E> getRoot() { return root; }
//+-------------------------------------+
//| Get the number of nodes in the tree |
//+-------------------------------------+
public int getSize() { return size; }
//+-------------------+
//| Inorder traversal |
//+-------------------+
public void inorder() { inorder( root ); }
protected void inorder( Node<E> node )
{
if (node == null) return;
inorder( node.left );
System.out.print( node.data + " " );
inorder( node.right );
}
//+---------------------+
//| Postorder traversal |
//+---------------------+
public void postorder() { postorder( root ); }
protected void postorder( Node<E> node )
{
if (node == null) return;
postorder( node.left );
postorder( node.right );
System.out.print( node.data + " " );
}
//+--------------------+
//| Preorder traversal |
//+--------------------+
public void preorder() { preorder( root ); }
protected void preorder( Node<E> node )
{
if (node == null) return;
System.out.print( node.data + " " );
preorder( node.left );
preorder( node.right );
}
//+---------------------------------+
//| Obtain an iterator. Use inorder |
//+---------------------------------+
public Iterator<E> iterator() { return new InorderIterator(); }
//+--------------------------------------+
//| inner class for the inorder iterator |
//+--------------------------------------+
private class InorderIterator implements Iterator<E>
{
private ArrayList<E> list = new ArrayList<E>(); // for data storage
private int current = 0; // Index to the current list item
public InorderIterator() { inorder(); } // default constructor
//+-------------------+
//| Inorder traversal |
//+-------------------+
private void inorder() { inorder( root ); }
private void inorder( Node<E> root )
{
if (root == null)return;
inorder( root.left );
list.add( root.data );
inorder( root.right );
}
//+------------------------+
//| more data to traverse? |
//+------------------------+
public boolean hasNext()
{
if (current < list.size())
return true;
return false;
}
//+-----------------------------------------+
//| get the next item and advance the index |
//+-----------------------------------------+
public E next() { return list.get( current++ ); }
//+-------------------------+
//| Remove the current item |
//+-------------------------+
public void remove()
{
delete( list.get( current ) ); // Delete the current item in the list
list.clear(); // Clear the list
inorder(); // Rebuild the list
}
}
}
Code for Rebalancing tree that needs to be modified to the requirements to work with BST.java:
import java.util.ArrayList;
public class RebalancingTree<E extends Comparable<E>> extends BST<E>
{
public RebalancingTree() { super(); }
@Override
public boolean insert( E e )
{
}
}
Explanation / Answer
hi the actual program is to write a AVL tree from the given BST code by overriding. I have a code for AVL tree which will be useful for your program please find below:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.