Splay Tree
Splay Tree
A Splay Tree is a self-adjusting Binary Search Tree (BST) in which every time a node is
accessed, it is moved to the root of the tree using a process called splaying.
The idea is that recently accessed elements are likely to be accessed again, so they
are moved closer to the root.
Every Splay tree must be a binary search tree but it is need not to be balanced tree.
The concept was introduced by Daniel Sleator and Robert Tarjan in 1985.
2. Properties of Splay Tree
It follows the Binary Search Tree property
Left subtree → smaller values
Right subtree → larger values
After every operation:
The accessed node becomes the root.
Frequently accessed nodes remain near the root.
It does not store extra balance information like AVL or Red-Black Trees.
3. Basic Operations
Operations in a splay tree include:
1. Search
Search for the element like in a BST.
Once found, splay the node to the root.
2. Insert
Steps:
Insert the node using BST insertion.
Perform splaying to bring the inserted node to the root.
3. Delete
Steps:
Splay the node to be deleted to the root.
Remove the root.
Join the left and right subtrees.
4. Splaying Operation
1. Zig Rotation
2. Zag Rotation
3. Zig - Zig Rotation
4. Zag - Zag Rotation
5. Zig - Zag Rotation
6. Zag - Zig Rotation
Case 1: Zig Rotation
The Zig Rotation in splay tree is similar to the single right rotation in AVL Tree rotations.
In zig rotation, every node moves one position to the right from its current position.
Case 2: Zag Rotation
The Zag Rotation in splay tree is similar to the single left rotation in AVL Tree
rotations. In zag rotation, every node moves one position to the left from its
current position.
Case 3: Zig-Zig Rotation
The Zig-Zig Rotation in splay tree is a double zig rotation. In zig-zig rotation, every node moves two
positions to the right from its current position.
Case 4: Zag-Zag Rotation
The Zag-Zag Rotation in splay tree is a double zag rotation. In zag-zag rotation, every node moves
two positions to the left from its current position.
Case 5: Zig-Zag Rotation
The Zig-Zag Rotation in splay tree is a sequence of zig rotation followed by zag rotation.
In zig-zag rotation, every node moves one position to the right followed by one position to
the left from its current position.
Case 6: Zag-Zig Rotation
The Zag-Zig Rotation in splay tree is a sequence of zag rotation followed by zig rotation.
In zag-zig rotation, every node moves one position to the left followed by one position to
the right from its current position.
5. Time Complexity
Operation Average Time
Search O(log n)
Insert O(log n)
Delete O(log n)
Worst case: O(n)
But amortized complexity is O(log n).
6. Advantages
Simple to implement.
Frequently accessed nodes become faster to access.
No need for extra balance information.
Good for applications with repeated searches.
7. Disadvantages
Worst-case time can be O(n).
Not always perfectly balanced.
May perform many rotations.
8. Applications
1. Caching Systems
In caching systems, recently used data is accessed more often.
A Splay Tree moves recently accessed elements to the root, so the next time they can be found faster.
Example:
Web browsers storing recently visited websites.
2. Memory Management
Operating systems need to quickly access frequently used memory blocks.
Splay Trees help by keeping recently accessed memory locations near the top, making them faster to find again.
3. Network Routers
Routers often check some network addresses more frequently than others.
Splay Trees move these frequently used addresses closer to the root, so the router can process packets faster.
4. Data Compression Algorithms
In compression algorithms, some characters or patterns appear more often.
Splay Trees move these frequently used items closer to the root, which helps the algorithm encode and decode
data faster.