Which of the following property of splay tree is correct?

Category: QuestionsWhich of the following property of splay tree is correct?
Editor">Editor Staff asked 1 month ago

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 Answers
Editor">Editor Staff answered 1 month ago

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.