By changing the potential function, it is possible to prove different bounds for splaying. Let the weight function W(i) be some function assigned to each node in the tree, and let S(i) be the sum of the weights of all the nodes in the subtree rooted at i, including i itself. The special case W(i) = 1 for all nodes corresponds to the function used in the proof of the splaying bound. Let N be the number of nodes in the tree, and let M be the number of accesses. Prove the following two theorems:
a. The total access time is O(M + (M + N) logN).
b. If qi is the number of times that item i is accessed, and qi > 0 for all i, then the total access time is

Transcribed Image Text:

0M+E log(M/q) i=1