Suppose we store, for each node, the number of null links in its subtree; call thisthe

Chapter 12, Problem 12.15

(choose chapter or problem)

Suppose we store, for each node, the number of null links in its subtree; call thisthe nodes weight. Adopt the following strategy: If the left and right subtrees haveweights that are not within a factor of 2 of each other, then completely rebuild thesubtree rooted at the node. Show the following:a. We can rebuild a node in O(S), where S is the weight of the node.b. The algorithm has amortized cost of O(logN) per insertion.c. We can rebuild a node in a k-d tree in O(S log S) time, where S is the weight ofthe node.d. We can apply the algorithm to k-d trees, at a cost of O(log2 N) per insertion