Splay Trees

• splay trees guarantee that any M consecutive tree operations starting from an empty tree take at most O(M logN) time.
• a splay tree has an O(logN) amortized cost per operation.
• Splay trees are based on the fact that the O(N) worst-case time per operation for binary search trees is not bad, as long as it occurs relatively infrequently.
• The basic idea of the splay tree is that after a node is accessed, it is pushed to the root by a series of avl tree rotations.
• Splay trees also do not require the maintenance of height or balance information, thus saving space and simplifying the code to some extent
• zig-zag case


  we perform a double rotation, exactly like an avl double rotation
• zig-zig case


  we transform the tree on the left to the tree on the right.
• splaying not only moves the accessed node to the root but also has the effect of roughly halving the depth of most nodes on the access path