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:
• The maximum balance factor in the tree (the balance factor of the root of the subtree that will be rebalanced)
• The current height of the whole tree
• The average depth of the nodes in the whole tree before the rebalancing
• The average depth of the nodes in the whole tree after the rebalancing
• The number of nodes in the subtree that was rebalanced
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.
Attachment:- Assignment.rar