I need to balance a Binary Search Tree. The function declaration is shown below. My structs are as followed:
struct bst_node { int val; int numLeft; int numRight; struct bst_node *left; struct bst_node *right;
}; typedef struct bst_node NODE;
struct bst { NODE *root; int size; int min; int max; };
A straightforward approach to rebalancing a subtree is as follows Populate a temporary array with the elementsodes in the subtree in sorted order From this array, re-construct a perfectly balanced (as perfectly as possible) tree to replace the original tree. The details are up to you, but observe that the number of tree nodes before and after the re-balancing is unchanged, you should be able to re-use the already existing nodes. Statistics function: You will also implement a function which reports the total "work" done by re-balancing. Every time you do a re-balance, the cost or work performed is the size of the sub-tree that was rebalanced. You will keep track of the total amount of rebalancing work performed and report it via the following function: s function: bst sb work * description: returns the total amount of work performed by re-balancing since the creation of the tree Every time a rebalance operation happens, the work is equal to the size of the subtree that was rebalanced (size-number-of-nodes) The total work is simply taken over all re-balancing ops extern int bst_sb_work (BST t); A straightforward approach to rebalancing a subtree is as follows Populate a temporary array with the elementsodes in the subtree in sorted order From this array, re-construct a perfectly balanced (as perfectly as possible) tree to replace the original tree. The details are up to you, but observe that the number of tree nodes before and after the re-balancing is unchanged, you should be able to re-use the already existing nodes. Statistics function: You will also implement a function which reports the total "work" done by re-balancing. Every time you do a re-balance, the cost or work performed is the size of the sub-tree that was rebalanced. You will keep track of the total amount of rebalancing work performed and report it via the following function: s function: bst sb work * description: returns the total amount of work performed by re-balancing since the creation of the tree Every time a rebalance operation happens, the work is equal to the size of the subtree that was rebalanced (size-number-of-nodes) The total work is simply taken over all re-balancing ops extern int bst_sb_work (BST t)
