5 Play trees Professor Bille suggests a simpler version of Splay Trees that he calls Play...

Transcribed Image Text:

5 Play trees Professor Bille suggests a simpler version of Splay Trees that he calls Play trees. Play Trees are similar to Splay Trees but uses only single rotations when splaying. 5.1 What is the amortized cost of splay(x) if we only use single rotations? Analyze it with the same potential function as we used for Splay Trees. 5.2 What is the total (actual) cost of first n inserting elements with keys 1,2, 3,...,n in that order in a Play Tree and then searching for 1,2,3,...,n (in that order)? 5.3 Professor Bille claims that the amortized cost of the operations insert, search and delete in Play trees is O(logn). "You just need to use a more sophisticated potential function" he says. Could he be correct? 5 Play trees Professor Bille suggests a simpler version of Splay Trees that he calls Play trees. Play Trees are similar to Splay Trees but uses only single rotations when splaying. 5.1 What is the amortized cost of splay(x) if we only use single rotations? Analyze it with the same potential function as we used for Splay Trees. 5.2 What is the total (actual) cost of first n inserting elements with keys 1,2, 3,...,n in that order in a Play Tree and then searching for 1,2,3,...,n (in that order)? 5.3 Professor Bille claims that the amortized cost of the operations insert, search and delete in Play trees is O(logn). "You just need to use a more sophisticated potential function" he says. Could he be correct?

Answer rating: 100% (QA)

answer 51 The amortized cost of Splayx will be Olog n Splay trees are actually considered to be bina... View the full answer