Skip to content

Commit 626ef44

Browse files
sozelfistsozelfist
committed
feat: implement SplayTree
1 parent 52f15b2 commit 626ef44

File tree

2 files changed

+425
-0
lines changed

2 files changed

+425
-0
lines changed

‎src/main/java/com/thealgorithms/datastructures/trees/SplayTree.java

Lines changed: 323 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,323 @@
1+
package com.thealgorithms.datastructures.trees;
2+
3+
import java.util.LinkedList;
4+
import java.util.List;
5+
6+
/**
7+
* Implementation of a Splay Tree data structure.
8+
*
9+
* <p>
10+
* A splay tree is a self-adjusting binary search tree with the additional property
11+
* that recently accessed elements are quick to access again. It performs basic
12+
* operations such as insertion, deletion, and searching in O(log n) amortized time,
13+
* where n is the number of elements in the tree.
14+
* </p>
15+
*
16+
* <p>
17+
* The key feature of splay trees is the splay operation, which moves a node closer
18+
* to the root of the tree when it is accessed. This operation helps to maintain
19+
* good balance and improves the overall performance of the tree. After performing
20+
* a splay operation, the accessed node becomes the new root of the tree.
21+
* </p>
22+
*
23+
* <p>
24+
* Splay trees have applications in various areas, including caching, network routing,
25+
* and dynamic optimality analysis.
26+
* </p>
27+
*/
28+
public class SplayTree {
29+
30+
private static class Node {
31+
int key;
32+
Node left, right;
33+
34+
Node(int key) {
35+
this.key = key;
36+
left = right = null;
37+
}
38+
}
39+
40+
private Node root;
41+
42+
/**
43+
* Constructs an empty SplayTree.
44+
*/
45+
public SplayTree() {
46+
root = null;
47+
}
48+
49+
/**
50+
* Zig operation.
51+
*
52+
* <p>
53+
* The zig operation is used to perform a single rotation on a node to move it closer to
54+
* the root of the tree. It is typically applied when the node is a left child of its parent
55+
* and needs to be rotated to the right.
56+
* </p>
57+
*
58+
* @param x The node to perform the zig operation on.
59+
* @return The new root node after the operation.
60+
*/
61+
private Node rotateRight(Node x) {
62+
Node y = x.left;
63+
x.left = y.right;
64+
y.right = x;
65+
return y;
66+
}
67+
68+
/**
69+
* Zag operation.
70+
*
71+
* <p>
72+
* The zag operation is used to perform a single rotation on a node to move it closer to
73+
* the root of the tree. It is typically applied when the node is a right child of its parent
74+
* and needs to be rotated to the left.
75+
* </p>
76+
*
77+
* @param x The node to perform the zag operation on.
78+
* @return The new root node after the operation.
79+
*/
80+
private Node rotateLeft(Node x) {
81+
Node y = x.right;
82+
x.right = y.left;
83+
y.left = x;
84+
return y;
85+
}
86+
87+
/**
88+
* Splay operation.
89+
*
90+
* <p>
91+
* The splay operation is the core operation of a splay tree. It moves a specified node
92+
* closer to the root of the tree by performing a series of rotations. The goal of the splay
93+
* operation is to improve the access time for frequently accessed nodes by bringing them
94+
* closer to the root.
95+
* </p>
96+
*
97+
* <p>
98+
* The splay operation consists of three main cases:
99+
* <ul>
100+
* <li>Zig-Zig case: Perform two consecutive rotations.</li>
101+
* <li>Zig-Zag case: Perform two consecutive rotations in opposite directions.</li>
102+
* <li>Zag-Zag case: Perform two consecutive rotations.</li>
103+
* </ul>
104+
* </p>
105+
*
106+
* <p>
107+
* After performing the splay operation, the accessed node becomes the new root of the tree.
108+
* </p>
109+
*
110+
* @param root The root of the subtree to splay.
111+
* @param key The key to splay around.
112+
* @return The new root of the splayed subtree.
113+
*/
114+
private Node splay(Node root, int key) {
115+
if (root == null || root.key == key) return root;
116+
117+
if (root.key > key) {
118+
if (root.left == null) return root;
119+
// Zig-Zig case
120+
if (root.left.key > key) {
121+
// Recursive call to splay on grandchild
122+
root.left.left = splay(root.left.left, key);
123+
// Perform zig operation on parent
124+
root = rotateRight(root);
125+
} // Zig-Zag case
126+
else if (root.left.key < key) {
127+
// Recursive call to splay on grandchild
128+
root.left.right = splay(root.left.right, key);
129+
// Perform zag operation on parent
130+
if (root.left.right != null) root.left = rotateLeft(root.left);
131+
}
132+
133+
return (root.left == null) ? root : rotateRight(root);
134+
} else {
135+
if (root.right == null) return root;
136+
// Zag-Zag case
137+
if (root.right.key > key) {
138+
// Recursive call to splay on grandchild
139+
root.right.left = splay(root.right.left, key);
140+
// Perform zig operation on parent
141+
if (root.right.left != null) root.right = rotateRight(root.right);
142+
} // Zag-Zig case
143+
else if (root.right.key < key) {
144+
// Recursive call to splay on grandchild
145+
root.right.right = splay(root.right.right, key);
146+
// Perform zag operation on parent
147+
root = rotateLeft(root);
148+
}
149+
150+
return (root.right == null) ? root : rotateLeft(root);
151+
}
152+
}
153+
154+
/**
155+
* Insert a key into the SplayTree.
156+
*
157+
* @param key The key to insert.
158+
*/
159+
public void insert(int key) {
160+
root = insertRec(root, key);
161+
root = splay(root, key);
162+
}
163+
164+
/**
165+
* Recursive function to insert a key.
166+
*
167+
* @param root The root of the subtree to insert the key into.
168+
* @param key The key to insert.
169+
* @return The root of the modified subtree.
170+
*/
171+
private Node insertRec(Node root, int key) {
172+
if (root == null) return new Node(key);
173+
174+
if (root.key > key) {
175+
root.left = insertRec(root.left, key);
176+
} else if (root.key < key) {
177+
root.right = insertRec(root.right, key);
178+
}
179+
180+
return root;
181+
}
182+
183+
/**
184+
* Search for a key in the SplayTree.
185+
*
186+
* @param key The key to search for.
187+
* @return True if the key is found, otherwise false.
188+
*/
189+
public boolean search(int key) {
190+
root = splay(root, key);
191+
return root != null && root.key == key;
192+
}
193+
194+
/**
195+
* Delete a key from the SplayTree.
196+
*
197+
* @param key The key to delete.
198+
*/
199+
public void delete(int key) {
200+
root = deleteRec(root, key);
201+
}
202+
203+
/**
204+
* Recursive function to delete a key.
205+
*
206+
* @param root The root of the subtree to delete the key from.
207+
* @param key The key to delete.
208+
* @return The root of the modified subtree.
209+
*/
210+
private Node deleteRec(Node root, int key) {
211+
if (root == null) return null;
212+
213+
if (root.key > key) {
214+
root.left = deleteRec(root.left, key);
215+
} else if (root.key < key) {
216+
root.right = deleteRec(root.right, key);
217+
} else {
218+
// Found the node to delete
219+
if (root.left == null)
220+
return root.right;
221+
else if (root.right == null)
222+
return root.left;
223+
224+
// Node with two children: Get the inorder successor (smallest in the right subtree)
225+
root.key = minValue(root.right);
226+
227+
// Delete the inorder successor
228+
root.right = deleteRec(root.right, root.key);
229+
}
230+
231+
return root;
232+
}
233+
234+
/**
235+
* Find the minimum value in a subtree.
236+
*
237+
* @param root The root of the subtree to find the minimum value in.
238+
* @return The minimum value in the subtree.
239+
*/
240+
private int minValue(Node root) {
241+
int minValue = root.key;
242+
while (root.left != null) {
243+
minValue = root.left.key;
244+
root = root.left;
245+
}
246+
return minValue;
247+
}
248+
249+
/**
250+
* Perform an in-order traversal of the SplayTree.
251+
*
252+
* @return A vector containing the keys in in-order traversal order.
253+
*/
254+
public List<Integer> inOrder() {
255+
List<Integer> result = new LinkedList<>();
256+
inOrderRec(root, result);
257+
return result;
258+
}
259+
260+
/**
261+
* Recursive function for in-order traversal.
262+
*
263+
* @param root The root of the subtree to traverse.
264+
* @param result The vector to store the traversal result.
265+
*/
266+
private void inOrderRec(Node root, List<Integer> result) {
267+
if (root != null) {
268+
inOrderRec(root.left, result);
269+
result.add(root.key);
270+
inOrderRec(root.right, result);
271+
}
272+
}
273+
274+
/**
275+
* Perform a pre-order traversal of the SplayTree.
276+
*
277+
* @return A vector containing the keys in pre-order traversal order.
278+
*/
279+
public List<Integer> preOrder() {
280+
List<Integer> result = new LinkedList<>();
281+
preOrderRec(root, result);
282+
return result;
283+
}
284+
285+
/**
286+
* Recursive function for pre-order traversal.
287+
*
288+
* @param root The root of the subtree to traverse.
289+
* @param result The vector to store the traversal result.
290+
*/
291+
private void preOrderRec(Node root, List<Integer> result) {
292+
if (root != null) {
293+
result.add(root.key);
294+
preOrderRec(root.left, result);
295+
preOrderRec(root.right, result);
296+
}
297+
}
298+
299+
/**
300+
* Perform a post-order traversal of the SplayTree.
301+
*
302+
* @return A vector containing the keys in post-order traversal order.
303+
*/
304+
public List<Integer> postOrder() {
305+
List<Integer> result = new LinkedList<>();
306+
postOrderRec(root, result);
307+
return result;
308+
}
309+
310+
/**
311+
* Recursive function for post-order traversal.
312+
*
313+
* @param root The root of the subtree to traverse.
314+
* @param result The vector to store the traversal result.
315+
*/
316+
private void postOrderRec(Node root, List<Integer> result) {
317+
if (root != null) {
318+
postOrderRec(root.left, result);
319+
postOrderRec(root.right, result);
320+
result.add(root.key);
321+
}
322+
}
323+
}

0 commit comments

Comments
 (0)