Question

Write short note on Splay Tree.

Answer 1

Splay Tree

• A splay tree consists of a binary tree, with no additional fields.
• When a node in a splay tree is accessed, it is rotated or ‘splayed’ to the root, thereby changing the structure of the tree.
• Since the most frequently accessed node is always moved closer to the starting point of the search (or the root node), these nodes are therefore located faster.
• A simple idea behind it is that if an element is accessed, it is likely that it will be accessed again.
• In a splay tree, operations such as insertion, search, and deletion are combined with one basic operation called splaying
• Splaying the tree for a particular node rearranges the tree to place that node at the root.
•  A technique to do this is to first perform a standard binary tree search for that node and then use rotations in a specific order to bring the node on top.

Advantages and Disadvantages of Splay Trees

• A splay tree gives good performance for search, insertion, and deletion operations.
• This advantage centres on the fact that the splay tree is a self-balancing and a self-optimizing data structure.
• Splay trees are considerably simpler to implement.
• Splay trees minimize memory requirements as they do not store any bookkeeping data.
• Unlike other types of self-balancing trees, splay trees provide good performance.