CODEWITHSUNDEEP
algorithmdata-structuresbig-oanalysisamortized-analysis
Zarif
Zarif

Reputation: 485

Amortized Analysis of Splay Tree

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 ,

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 :)

Upvotes: 3

Views: 399

Answers (1)

Ami Tavory
Ami Tavory

Reputation: 76366

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.

Upvotes: 2

Related Questions