Splay Trees are an advanced type of self-adjusting binary search tree (BST) where frequently accessed elements are moved closer to the root through a process known as splaying. The main motivation for using a splay tree is to provide fast access to recently or frequently used items, achieving amortized time complexity of O(log n) for operations like search, insert, and delete.
Unlike balanced binary trees such as AVL or Red-Black trees, splay trees do not maintain strict balance rules. Instead, they leverage the principle of locality of reference by moving accessed elements closer to the root, reducing the cost of subsequent operations on those elements.
Key Features of Splay Trees
- Self-Adjusting: Nodes move closer to the root every time they are accessed.
- No Balancing Factor: Unlike AVL or Red-Black trees, splay trees do not store additional balancing info.
- Amortized Efficiency: Though one operation can be costly, amortized complexities for operations remain O(log n).
- Cache-Friendly: Frequently accessed data moves up, improving performance for non-uniform access patterns.
Basic Operations in Splay Tree
The primary operations of a splay tree—like search, insert, and delete—are built upon the fundamental operation called splay. The splay operation moves a node to the root using successive tree rotations.
The Splay Operation
Splaying is achieved by performing tree rotations in sequences based on the position of the accessed node relative to its parent and grandparent. The three main cases are:
- Zig: Single rotation when the node is a direct child of the root.
- Zig-Zig: Double rotation when both the node and its parent are either left children or right children.
- Zig-Zag: Double rotation when the node is a left child and the parent is a right child, or vice versa.
The above diagram shows the initial positioning of a node (X). Depending on whether it’s Zig, Zig-Zig, or Zig-Zag, rotations restructure the tree and promote X upward, eventually moving it to the root.
Insertion in Splay Tree
To insert an element into a splay tree:
- Perform a normal BST insertion.
- Splay the newly inserted node to the root.
Inserting 40 places it as the right child of 30. After insertion, 40 is splayed to the root.
Deletion in Splay Tree
To delete a node from a splay tree:
- Splay the node to be deleted to the root.
- Remove the root:
- If root has no left subtree, replace root with right subtree.
- If root has left subtree, splay the maximum node of the left subtree to make it root, then attach the right subtree.
If 30 is deleted, 20 (largest in left subtree) can be splayed to the root, then attach the right child 40.
Searching in a Splay Tree
Search operation follows normal BST rules, but at the end, the searched node (or the last accessed node if not found) is splayed to the root. This ensures fast access for subsequent operations if related nodes are accessed again.
Python Example of Splay Tree
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class SplayTree:
def __init__(self):
self.root = None
def right_rotate(self, x):
y = x.left
x.left = y.right
y.right = x
return y
def left_rotate(self, x):
y = x.right
x.right = y.left
y.left = x
return y
def splay(self, root, key):
if root is None or root.key == key:
return root
if key < root.key:
if root.left is None:
return root
if key < root.left.key:
root.left.left = self.splay(root.left.left, key)
root = self.right_rotate(root)
elif key > root.left.key:
root.left.right = self.splay(root.left.right, key)
if root.left.right:
root.left = self.left_rotate(root.left)
return self.right_rotate(root) if root.left else root
else:
if root.right is None:
return root
if key > root.right.key:
root.right.right = self.splay(root.right.right, key)
root = self.left_rotate(root)
elif key < root.right.key:
root.right.left = self.splay(root.right.left, key)
if root.right.left:
root.right = self.right_rotate(root.right)
return self.left_rotate(root) if root.right else root
def insert(self, key):
if self.root is None:
self.root = Node(key)
return
self.root = self.splay(self.root, key)
if self.root.key == key:
return
new_node = Node(key)
if key < self.root.key:
new_node.right = self.root
new_node.left = self.root.left
self.root.left = None
else:
new_node.left = self.root
new_node.right = self.root.right
self.root.right = None
self.root = new_node
Interactive Example
You can experiment with splay trees using online interactive platforms or by modifying the above Python code. Try inserting sequences like [10, 20, 30, 40, 50] and observing how the tree reshapes itself after every operation.
Advantages of Splay Trees
- Amortized O(log n) performance for operations.
- Excellent for adaptive data access patterns.
- No need for storing balancing information.
- Good alternative to other BST variants when frequent access of certain elements is expected.
Disadvantages of Splay Trees
- Worst-case time complexity can reach O(n) for a single operation.
- Not strictly balanced, so performance can degrade in rare cases if access patterns are uniform and unfavorable.
Use Cases of Splay Trees
- Implementing caches where recently accessed data is needed quickly.
- Managing memory allocators and garbage collectors.
- Data compression algorithms (like zip/unzip processes).
- Network routers where frequently accessed routes need fast lookup.
Conclusion
Splay Trees provide an elegant balance between simplicity and performance by leveraging self-adjustment instead of strict balancing rules. With their amortized efficiency and their ability to adapt to access patterns, they are a powerful tool in computer science that stands as an alternative to more rigid self-balancing trees like AVL and Red-Black trees.
