It is also a BST and self balancing tree like AVL and red-black trees but is used
in real-world applications where out of 100, 80 times the data which is queried
is 20% data in the database.
This tree implemenation not just balances the tree, to get insertion/deletion/search to complete
in O(log n) time, but also move recently accessed the data to the root. This way
frequent access to the same data will take O(1) time in next access.
Having said that, still the algorithm will result in O(log n) amortized time complexity.
Comparison between AVL, Red-Black and Splay trees
On contrary, Splay trees balances tree in read-only operation (like search) also.Splay tree does not have to keep extra book-keeping information in the data structure like AVL trees (height) or red-black trees (color)
Red-black trees are used in applications where insertion and deletion are frequent operations.Where as AVL trees are used for quick searching as searching takes O(Log n) because tree is balanced.
Due to insertion and deletion, tree need rebalancing. Hence if application involves
more insertion and deletion operations then AVL trees is not a best choice.
Use red-black trees instead for quick insertion and deletion.
Applications of Splay trees
- Due to their reference of locality property, they can be used in implementing logic behind caches.
- They can come handy in joining two trees – merging a tree between 2 elements of another tree (O(log M + N))
- Also they can be used in bifurcating the data into 2 distinguish data sets – cutting a tree
- Can be used in garbage collectors
- Querying faster than O(log(N)) for highly biased query distributions
- Used in network router (aprt from other data structures like Hash tables, trie, etc)
- Amortized O(log n) performance
- Requires no extra book-keeping info
- Can handle duplicate data (unlike other trees like AVL, red-black)
- Cannot be used in multithreading applications as even read-only(search) operations also alter the tree structure. Allowing multiple threads to search keys may corrupt the trees.