Amortized Analysis of Splay Tree

Question

Splay Tree insert / delete can be done in different ways . One popular way is to insert the key and splay it to the root . But there is also a different approach that I've read about , the idea is to split it into 2 trees such that the left one has values <= the insert key and the right one has value > the insert key . Same goes for the alternate delete approach , the key to be deleted is splayed to the root and then the left and right tree is merged .

But the way I understand ,

• If the insertion is in increasing order , splitting the tree would always cause the right tree to be null , thus increasing the imbalance every time any key is inserted in this order .
• Same goes for the deletion , if we always delete the maximum element in a tree , in the merge operation the right subtree will be empty . And there is a huge imbalance .

My question is that , in this alternate process , is the amortized running time also stays O(logN) ? If so , how ? I tried searching over the internet but couldn't find any answer . Any kind of intuition would be really helpful :)

Answer 1

Yes, the amortized time remains O(log(n)).

The intuition is the splay tree's interplay between the cost of a single operation, and the imbalance. It is true that you can look at an operation and say "this is very expensive" or "this causes a lot of imbalance", but you need to consider both things simultaneously.

To use your first example, it is true that the inserts cause tremendous imbalance, but each one of them is O(1). At the end of m such operations the tree is imbalanced, but at this point, the cost was only O(m). Following this, the first different operation can be very expensive, but it will also decrease the imbalance.

The intuition for the series of deletes is similar. Intuitively, it also balances between these two.