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