Suppose we store, for each node, the number of nullptr links in its subtree; call this the node'sweight. Adopt the following strategy: If the left and right subtrees have weights that are not within a factor of 2 of each other, then completely rebuild the subtree 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(log N) per insertion.
c. We can rebuild a node in a k-d tree in O(S log S) time, where S is the weight of the node.
d. We can apply the algorithm to k-d trees, at a cost of O(log2 N) per insertion.