+1 vote
in Data Structures & Algorithms I by (110k points)
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 Answer

+1 vote
by (672k points)
selected by
 
Best answer
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).

Related questions

Welcome to TalkJarvis QnA, a question-answer community website for the people by the people. On TalkJarvis QnA you can ask your doubts, curiosity, questions and whatever going in your mind either related to studies or others. Experts and people from different fields will answer.

Categories

...