What is a Splay Tree?
A splay tree is a type of binary search tree. A splay tree is commonly used in LRU caches. Splay trees aren’t necessarily balanced, but they allow for queries of more recent items to be faster. A splay tree would work very well if given an offline scenario (all input is given prior).
The search and deletion from a splay tree are completely identical to how they are done in a binary search tree. The first part of insertion into the splay tree is also similar to the typical BST scenario.
Insertion in a splay tree
When something is inserted into a splay tree, it is rotated into becoming the root. This means that the most recent item will have an O(1) search time. The point of rotation in a splay tree is not to achieve a balanced tree.
Getting value from the tree
First, insert the item into the BST in the same way it would be normally done. If the value that is being inserted is greater than the current node, then go right; otherwise, go left. Repeat this until there is an “open” spot for the new node.
Splaying Operation
If the splay tree is supposed to represent something such as a cache, then, after every insertion, a splay should take place. But a splay command could be used on any node to make it the root and reform the structure. The splay operation uses tree rotations to get the requested node to the root. There are three types of situations that may occur in the tree, and each calls for a different action.
Let’s call the newly added node “X.”
Locate node X in the tree using the standard BST search method.
Situation 1: Zig Zag
This situation is present when:
X is the left node of a right child.
X is the right node of a left child.
If X is the left node of a right child, Then right-left rotation on node X must happen.
If X is the right node of a left child, Then a left-right rotation on node X must happen.
Situation 2: Zig Zig
This situation is present when:
X is the left node of a left node.
X is the right node of a right node.
If X is the left node of a left child, Then do a right rotation on it’s parent. Then, right-rotate node X.
If X is the right node of the right child, Then, do a left rotation on its parents. Then, left-rotate node X.
Situation 3: Zig
Repeat the Zig Zag and Zig Zig operations until you reach the root. Sometimes this doesn’t align correctly, and it might leave node X as the left or right child of the root. So, a simple left or right rotation should be able to fix it.
This situation is present when:
X is the left node of the root.
X is the right node of the root.
If X is the left node of the root, Then rotate node X to the right.
If X is the right node of the root, then rotate node X to the left.
Why use splay trees?
The point of the splay tree is to get O(1) search time on the most recent items. But why use a splay tree when the hashtable has O(1) search for every item?
This guy explains it well (I did not contribute to this post)