Data Structure Questions and Answers – Splay Tree


This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Splay Tree”.

1. Which of the following options is an application of splay trees?
A) cache Implementation
B) networks
C) send values
D) receive values

Explanation: Splay trees can be used for cache implementations because they allow for quicker access to recently accessed objects.

2. When we have red-black trees and AVL trees that can perform most of operations in logarithmic times, then what is the need for splay trees?
A) no there is no special usage
B) In real time it is estimated that 80% access is only to 20% data, hence most used ones must be easily available
C) redblack and avl are not upto mark
D) they are just another type of self balancing binary search trees

Explanation: It’s possible that the statistics showing 80-20% aren’t right, but in real time, that’s the most common scenario. If you find yourself in this situation, you should consider using splay trees.


3. After the insertion operation, is the resultant tree a splay tee?

A) true
B) false

Explanation: The right-hand side tree is made up of a zig-zag and a right operation (zig). For insertion in the splay tree, refer to splay operations.

4. What output does the below pseudo code produces?

    Tree_node function(Tree_node x)
        Tree_node y = x.left;
        x.left = y.right;
        y.right = x;
        return y;

A) right rotation of subtree
B) left rotation of subtree
C) zig-zag operation
D) zig-zig operation

Explanation: When a right rotation is performed, the rotating node’s parent becomes the rotating node’s right node, and the rotating node’s child becomes the rotating node’s left child.

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

Explanation: After accessing all n elements in non-decreasing order, this would be the case. The real cost of an operation can be high since the height of a tree corresponds to the worst-case access time. However, in the worst case, the amortised access cost is logarithmic O. (log n).

6. What are splay trees?
A) self adjusting binary search trees
B) self adjusting binary trees
C) a tree with strings
D) a tree with probability distributions

Explanation: Splay trees are self-adjusting, height-balanced BSTs.

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

Explanation: This is a function of the splay tree that allows for faster entry. The most commonly used nodes are pushed to the top, allowing for easier access to recently used values.

8. Why to prefer splay trees?
A) easier to program
B) space efficiency
C) easier to program and faster access to recently accessed items
D) quick searching

Explanation: When you insert, delete, or read an element, it will be moved or stored to the top, allowing for easy access to recently used items.

9. Is it true that splay trees have O(logn) amortized complexity ?
A) true
B) false

Explanation: When we believe that not all operations are bad and that some can be performed efficiently, we use amortised time complexity. Not all splay operations in splay trees have O(logn) worst-case complexity.

10. What is a splay operation?
A) moving parent node to down of child
B) moving a node to root
C) moving root to leaf
D) removing leaf node

Explanation: Splay trees are primarily based on splay operations. We splay the respective nodes to root whenever we insert, delete, or check for a node. We have operations that are zig-zag and zig-zig.

A splay tree is a binary search tree with the added feature of being easy to access previously accessed items. A splay tree, like self-balancing binary search trees, performs basic operations in O(log n) amortised time, such as insertion, look-up, and removal. Splay trees outperform other search trees for several non-random operations, even outperforming O(log n) for sufficiently non-random patterns, all without requiring prior knowledge of the pattern.

Leave a Reply

Your email address will not be published. Required fields are marked *