+1 vote
in Data Structures & Algorithms I by (110k points)
Which of the following property of splay tree is correct?

(a) it holds probability usage of the respective sub trees

(b) any sequence of j operations starting from an empty tree with h nodes atmost, takes O(jlogh) time complexity

(c) sequence of operations with h nodes can take O(logh) time complexity

(d) splay trees are unstable trees

My doubt is from Splay Tree in division Binary Trees of Data Structures & Algorithms I

I got this question in examination.

1 Answer

+1 vote
by (672k points)
selected by
 
Best answer
The correct choice is (b) any sequence of j operations starting from an empty tree with h nodes atmost, takes O(jlogh) time complexity

For explanation: This is a property of splay tree that ensures faster access. we push the most recently used nodes to top which leads to faster access to recently used values.

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

...