First time here? Checkout the FAQ!
menu search
Write short note on Splay Tree.
thumb_up_off_alt 0 like thumb_down_off_alt 0 dislike

1 Answer

Best answer

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.
thumb_up_off_alt 0 like thumb_down_off_alt 0 dislike