Create a balanced binary search tree. You will need to write a class named RebalancingTree that extends the BST class given at the link listed below. You will also need to incorporate the AbstractTree class and the Tree interface, all of which can be downloaded from the following locations:
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 the one lowest on 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 minimum possible height of a tree with the same number of nodes
- 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
The average depth of the nodes is proportional to the average search time, so you should verify that it decreases after the rebalancing.
Your test method should create a balanced binary search tree of integers and then randomly generate 10,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.