A splay tree after ascending inserts, followed by find(1)

A splay tree inserts a key by ordinary BST insertion and then splays the new node to the root. Keys 1, 2, ..., n are inserted into an empty splay tree in increasing order, and then find(1) is called, which walks down to key 1 and splays it. Splay trees guarantee O(log n) amortized time per operation. What is the actual cost of the n inserts in total, and of the find(1)?

41 of 46 in Data Structures & Algorithms