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