What is the disadvantage of using splay trees?

Category: QuestionsWhat is the disadvantage of using splay trees?
Editor">Editor Staff asked 1 month ago

What is the disadvantage of using splay trees?
 
(a) height of a splay tree can be linear when accessing elements in non decreasing order.
 
(b) splay operations are difficult
 
(c) no significant disadvantage
 
(d) splay tree performs unnecessary splay when a node is only being read
 
The doubt is from Splay Tree topic in section Binary Trees of Data Structures & Algorithms I
 
I got this question during an interview for a job.

1 Answers
Editor">Editor Staff answered 1 month ago

The correct option is (a) height of a splay tree can be linear when accessing elements in non decreasing order.
 
The best I can explain: This will be the case after accessing all n elements in non-decreasing order. Since the height of a tree corresponds to the worst-case access time, this means that the actual cost of an operation can be high. However the amortized access cost of this worst case is logarithmic O(log n).