Question

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.

Answer 1

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