Any sequence of k operations starting from an empty tree and never exceeding n items in tree will have O(k log n) worst case time.
The data structure ensures fast access to recently accessed data and much easier to program that other balanced trees like 2-3-4 tree.
Splay tree is not kept perfectly balanced all the time.
Tree rotation
Splay operation
We do splay operation whenever an item is accessed to move an item up through root. Repeatedly doing the operation moves the item up to the root of the tree.We continuously rotate the tree so that it takes the position of the item above (parent, grand parent, great grand parent etc.) until it becomes the root.
Given an item X to splay up there are three possible situations:
a. X is a left child of a right child or right child of a left child
For left child of a right child we rotate right first and then rotate left to move the item two level up. For right child of a left child we rotate left first and then rotate right to move the item two level up.
b. X is a left child of a left child or right child of a right child
For left child of a left child we rotate right twice to move the item two level up. For right child of a right child we rotate left twice to move the item two level up.
c. X is child of root
We rotate once as appropriate (left or right) to move the item to root.
In all cases one rotation moves the item one level in upper direction.
Splay tree operations
Find operation
find(k) Search for the key k as like a binary search tree or reached a leaf node Let X be the last node during the search whether it contains k or not Splay the node X up so that it becomes root through a sequence of tree rotation Splay X up to root using a sequence of rotation.
Insert Operation
insert(k) Insert k like binary search tree Splay the new node up to root through tree rotation
Remove operation
remove(k) Remove the node as ordinary binary search tree Splay the nodes parent up to root using tree rotation
