Splay Tree
A splay tree is a self-adjusting binary search tree where recently accessed elements are quick to access again via rotations. It works by splaying accessed nodes to the root.
Java example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
}
}
Node splay(Node root, int key) {
if (root == null || root.key == key) {
return root;
}
if (key < root.key) {
// key in left subtree
if (root.left == null) {
return root;
}
// Zig-zag splay
if (key < root.left.key) {
// Rotate right child
root.left.right = splay(root.left.right, key);
// new right child
root = rotateLeft(root);
}
// Zag-zig splay
else if (key > root.left.key) {
root = rotateRight(root);
}
// Zig-zig splay
return rotateLeft(root);
}
// Mirror image logic for right subtree
}
|
C++ example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| struct Node {
int key;
Node *left, *right;
Node(int k) : key(k) {}
};
Node* splay(Node* root, int key) {
if (!root || root->key == key) {
return root;
}
// Key in left subtree
if (key < root->key) {
//Recurse
if (!root->left) return root;
// Zig-zag rotation
if (key < root->left->key) {
root->left->right = splay(root->left->right, key);
root = rightRotate(root);
}
// Zag-zig rotation
else if (key > root->left->key) {
root = leftRotate(root);
}
// Zig-zig rotation
return rightRotate(root);
}
// Mirror image logic for right subtree
return root;
}
|
Python example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Node:
def __init__(self, key):
self.key = key
self.left = self.right = None
def splay(root, key):
if not root or root.key == key:
return root
if key < root.key:
# Key in left subtree
if not root.left:
return root
# Zig-zag rotation
if key < root.left.key:
root.left.right = splay(root.left.right, key)
root = rightRotate(root)
# Zag-zig rotation
elif key > root.left.key:
root = leftRotate(root)
# Zig-zig rotation
return rightRotate(root)
# Mirror image logic for right subtree
return root
|
Splay trees dynamically restructure on access to improve future access time. Useful for caches and priority queues.
A Splay Tree is a self-adjusting binary search tree. Every time an operation like insertion, deletion, or search is performed, the tree is rearranged so that the node corresponding to that operation becomes the new root. This action is known as “splaying.” Splay Trees don’t guarantee constant log time for each operation but perform quite well in practice for access patterns with locality of reference.
Java Code for Splay Tree
Here’s a simplified Java example for inserting a node and splaying:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| class Node {
int key;
Node left, right;
}
class SplayTree {
Node root;
// Splay operation
private Node splay(Node root, int key) {
// Base cases
if (root == null || root.key == key) return root;
if (root.key > key) {
// Key is in the left subtree
if (root.left == null) return root;
// Splay the left child
root.left = splay(root.left, key);
// Rotate right
return rightRotate(root);
} else {
// Key is in the right subtree
if (root.right == null) return root;
// Splay the right child
root.right = splay(root.right, key);
// Rotate left
return leftRotate(root);
}
}
// Right rotation
private Node rightRotate(Node x) {
Node y = x.left;
x.left = y.right;
y.right = x;
return y;
}
// Left rotation
private Node leftRotate(Node x) {
Node y = x.right;
x.right = y.left;
y.left = x;
return y;
}
// Insert operation
public void insert(int key) {
root = insert(root, key);
}
private Node insert(Node root, int key) {
if (root == null) return new Node(key);
root = splay(root, key);
// Insert the new node
Node newNode = new Node(key);
if (key < root.key) {
newNode.right = root;
newNode.left = root.left;
root.left = null;
} else {
newNode.left = root;
newNode.right = root.right;
root.right = null;
}
return newNode;
}
}
|
C++ Code for Splay Tree
Here’s the C++ code snippet:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| struct Node {
int key;
Node *left, *right;
};
Node* rightRotate(Node *x) {
Node *y = x->left;
x->left = y->right;
y->right = x;
return y;
}
Node* leftRotate(Node *x) {
Node *y = x->right;
x->right = y->left;
y->left = x;
return y;
}
Node* splay(Node *root, int key) {
// Base cases and splay logic similar to Java example
// ...
}
Node* insert(Node *root, int key) {
// Insertion logic similar to Java example
// ...
}
|
Python Code for Splay Tree
Python code snippet:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def rightRotate(x):
y = x.left
x.left = y.right
y.right = x
return y
def leftRotate(x):
y = x.right
x.right = y.left
y.left = x
return y
def splay(root, key):
# Base cases and splay logic similar to Java example
# ...
def insert(root, key):
# Insertion logic similar to Java example
# ...
|
In all three implementations, the splay() function restructures the tree by moving the node associated with a given key to the root. The insert() function inserts a new node and then splays it to the root. Both right and left rotations are also implemented.