Question

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.

Answer 1

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.