CONTACT Search … SEARCH search menu

DATA STRUCTURES Data Structures

Splay Tree in Data Structure 1. Array

calendar_month Updated April 21, 2023 2. Linked List

A Splay Tree is a roughly balanced Binary Search Tree (BST) that always keeps the Singly Linked List
recently accessed items closer to the root node. As a result, the search operation works Doubly Linked List
must faster when the same data is accessed again.
Circular Linked List

3. Stack
Table of Contents
1. Introduction 4. Queue
2. The Splay Operation Linear Queue
2.1 Zig Rotation
2.2 Zag Rotation Circular Queue
2.3 Zig-Zig Rotation
Priority Queue
2.4 Zag-Zag Rotation
2.5 Zig-Zag Rotation Double Ended Queue
2.6 Zag-Zig Rotation
5. Hash Table
3. Insertion on Splay Tree
4. Deletion on Splay Tree Separate Chaining
5. Search on Splay Tree Linear Probing
6. Traversals on Splay Tree
7. Implementation of Splay Tree in C++ 6. Tree
8. References Binary Tree

Binary Search Tree

1. Introduction
AVL Tree
Splay Tree is not strictly balanced like the AVL Tree but is intended to work faster for
Splay Tree
cache applications. Splaying is an additional operation carried out during the insert,
delete, and search operations. The recently accessed node becomes the root and the Heap

tree changes for even read-only search operations.

Representation Categories
Data Structures
30 Roughly balanced: Rotations are Kubernetes
used to bring the recently
20 50
accessed node to the root. This
Archives
10 40 60
helps the tree be roughly
March 2024
balanced.
Splay Tree Representation April 2023
Zig Rotation: Right rotation.
Zag Rotation: Left rotation. March 2023
 1. // Tree node representation
2. struct Node February 2023
3. {
4. int data; // Actual data January 2023
5. Node* left; // Pointer to left child
6. Node* right; // Pointer to right child December 2022
7. Node* parent; // Pointer to parent node
8. };
April 2022
9.
10. // The root node
11. Node* root; February 2022

January 2022
Applications
October 2021
Cache applications
Windows NT (in the virtual memory, networking, and file system code)
GCC compiler and GNU C++ library
The sed string editor
Fore Systems network routers
The most popular implementation of Unix malloc, Linux loadable kernel modules,
and much other software.

2. The Splay Operation

The splay tree operations such as insertion, deletion, and search are followed by one
special operation called splaying. It is nothing but a set of rotations performed to bring
the recently accessed node as the root.

Rotations

Splay tree rotation works primarily on three nodes: the target node, the parent, and the
grandparent. The following rotations are used by the splay-tree.

Zig – Right rotation

Zag – Left rotation
Zig-Zig – Right-Right rotation (grandparent first)
Zag-Zag – Left-Left rotation (grandparent first)
Zig-Zag – Righ-Left rotation (parent first)
Zag-Zig – Left-Right rotation (parent first)

The combination of simple Left and Right rotation can bring any node as root. So why
should we take the grandparent into account and have additional types of rotations?
Because the Zig-Zig and Zag-Zag rotations work on the grandparent first. So that it
better keeps the recently accessed items closer to the root and helps to maintain the
optimal balance.

2.1 Zig Rotation

Perform the Zig rotation to make the target node (10) as root.
 20 10

10 20

Zig Rotation of Splay Tree

2.2 Zag Rotation

Perform the Zag rotation to make the target node (20) as root.

10 20

20 10

Zag Rotation of Splay Tree

2.3 Zig-Zig Rotation

Perform the Zig-Zig rotation to make the target node (10) as root. Note that the
grandparent (30) is rotated first followed by the parent (20).

30 10

20 20 20

10 10 30 30

Zig-Zig Rotation of Splay Tree

2.4 Zag-Zag Rotation

Perform the Zag-Zag rotation to make the target node (30) as root. Note that the
grandparent (10) is rotated first followed by the parent (20).

10 30

20 20 20

30 10 30 10

Zag-Zag Rotation of AVL Tree

2.5 Zig-Zag Rotation

Perform the Zig-Zag rotation to make the target node (20) as root. Note that the parent
(30) is rotated first followed by the grandparent (10).

10 10

30 20 20

20 30 10 30

Zig Zag Rotation of AVL Tree

2.6 Zag-Zig Rotation

Perform the Zag-Zig rotation to make the target node (20) as root. Note that the parent
node (10) is rotated first followed by the grandparent (30).

30 30

10 20 20

20 10 10 30

Zag-Zig Rotation of AVL Tree

For Zig-Zig and Zag-Zag cases, the rotation is performed on the grandparent first
followed by the parent. This is required to maintain the optimal tree balance and to
keep the recently accessed items closer to the root node.
For Zig-Zag and Zag-Zig cases, the rotation is performed on the parent first
followed by the grandparent. The reverse order does not work in this case, because
performing the first rotation on the grandparent would affect the original position
of the splaying node.

Algorithm

1. Get the address of the target node.

2. Iterate until the target node becomes the root.
3. If the target node has only the parent and not the grandparent, perform either Zig or
Zag rotation based on the position.
Left: Zig Rotation
Right: Zag Rotation
4. If the target node has the grandparent, perform any of the following rotations
based on its position.
Left-Left: Zig-Zig Rotation
Right-Right: Zag-Zag Rotation
Right-Left: Zig-Zag Rotation
 Left-Right: Zag-Zig Rotation

Code

1. // Splay the tree by a given node

2. void SplayTree::splay(Node* x)
3. {
4. while (x->parent != NULL) {
5. if (x->parent->parent == NULL) {
6. // Node has only parent and not grantparent
7. if (x == x->parent->left) {
8. // Node is on left: perform right rotation
9. // p x
10. // / => \
11. // x p
12. right_rotate(x->parent);
13. } else {
14. // Node is on right: perform left rotation
15. // p x
16. // \ => /
17. // x p
18. left_rotate(x->parent);
19. }
20.
21. } else {
22. // Node has parent and grandparent
23. Node* parent = x->parent;
24. Node* grandpa = x->parent->parent;
25. if (x == parent->left && parent == grandpa->left) {
26. // Zig zig rotation: Rotate grantparent first for better balance
27. // g p x
28. // / / \ \
29. // p => x g => p
30. // / \
31. // x g
32. right_rotate(x->parent->parent);
33. right_rotate(x->parent);
34. } else if (x == parent->right && parent == grandpa->right) {
35. // Zag zag rotation: Rotate grantparent first for better balance
36. // g p x
37. // \ / \ /
38. // p => g x => p
39. // \ /
40. // x g
41. left_rotate(x->parent->parent);
42. left_rotate(x->parent);
43. } else if (x == parent->left && parent == grandpa->right) {
44. // Zig zag rotation: Rotate parent first because rotating the
45. // grantparent first would change the position of the node
46. // g g x
47. // \ \ / \
48. // p => x => g p
49. // / \
50. // x p
51. right_rotate(x->parent);
52. left_rotate(x->parent);
53. } else {
54. // Zag zig rotation: Rotate parent first because rotating the
55. // grantparent first would change the position of the node
56. // g g x
57. // / \ /
58. // p => x => g
59. // \ / \
60. // x p p
61. left_rotate(x->parent);
62. right_rotate(x->parent);
63. }
64. }
65. }
66.
67. // Make the splay node as root
68. root = x;
69. }
70.
 71. // Perform zag (left) rotation of the given node
72. void SplayTree::left_rotate(Node* p)
73. {
74. // Pull up the right side node on top
75. Node* top = p->right;
76. top->parent = p->parent;
77. if (top->parent != NULL) {
78. if (p == p->parent->left) {
79. p->parent->left = top;
80. } else {
81. p->parent->right = top;
82. }
83. }
84.
85. // Link the left subtree to right of the target node p
86. p->right = top->left;
87. if (p->right) {
88. p->right->parent = p;
89. }
90.
91. // Pull down the target node p to left
92. top->left = p;
93. top->left->parent = top;
94. }
95.
96. // Perform zig rotation of the given node
97. void SplayTree::right_rotate(Node* p)
98. {
99. // Pull up the left side node on top
100. Node* top = p->left;
101. top->parent = p->parent;
102. if (top->parent != NULL) {
103. if (p == p->parent->left) {
104. p->parent->left = top;
105. } else {
106. p->parent->right = top;
107. }
108. }
109.
110. // Link the right subtree to left of the target node p
111. p->left = top->right;
112. if (p->left) {
113. p->left->parent = p;
114. }
115.
116. // Pull down the target node p to right
117. top->right = p;
118. top->right->parent = top;
119. }

3. Insertion on Splay Tree

A node is always inserted at the bottom of the tree. Traverse the tree based on the order,
insert the new node, and perform splaying to make the new node as root.

Algorithm

1. Start the traversal from the root node to find the data location.
2. If the data element is smaller than the current node, traverse on the left subtree.
3. Otherwise, traverse on the right subtree if the data element is greater.
4. Insert the node when the traversal reached the bottom.
5. Splay the tree to make the new node as root. Refer to “The Splay Operation” for
detailed steps.

Code

1. // Insert a new node

 2. void SplayTree::insert(int data)
3. {
4. if (root == NULL) {
5. // Insert the first node as root and return
6. root = new Node(data, NULL);
7. return;
8. }
9.
10. Node* p = root;
11. Node* pp = NULL;
12. // Traverse the tree from the root
13. while (1) {
14. pp = p;
15. if (data < p->data) {
16. // Traverse the left subtree if the data is smaller
17. p = p->left;
18. if (p == NULL) {
19. // Insert the node on left and stop the traversal
20. p = new Node(data, pp);
21. pp->left = p;
22. break;
23. }
24. } else {
25. // Traverse the right subtree if the data is greater
26. p = p->right;
27. if (p == NULL) {
28. // Insert the node on right and stop the traversal
29. p = new Node(data, pp);
30. pp->right = p;
31. break;
32. }
33. }
34. }
35.
36. // Splay the tree to make the new node as root
37. splay(p);
38. }

Examples

The following diagrams illustrate the insertion of the data 20, 10, 60, 40, 50, and 30.

Insert element 20

The initial tree is empty, so insert 20

20
as the root node.

Insert element 20

Insert element 10

Create a new node 10 on the left of

20
node (20).

10
Subsequently, splay the tree to make
node 10 as root.
Insert element 10 The node has only the parent and
not the grandparent, so perform a
Zig (right) rotation since the node is
on the left side of the root.
Perform a Zig Rotation from the node (20)

20 10

10 20

Perform a Zig Rotation from the node (20)

Insert element 60

10 Create a new node 60 on the right of

node (10) and perform splaying.
20 The node (60) has the grandparent
and is located on the Right-Right
60
side, so perform a Zag-Zag (Left-

Insert element 60
Left) rotation.

Perform a Zag-Zag Rotation

10 60

20 20 20

60 10 60 10

Perform a Zag-Zag Rotation

Insert element 40

Create a new node (40) on the right

60
of node (20) and perform splaying.

20
The node (40) has the grandparent
and is located on the Left-Right side,
10 40 so perform a Zag-Zig (Left-Right)
rotation.
Here we perform the operation on
the parent node first.
Insert element 40

Perform a Zag-Zig Rotation

 60 60

20 40 40

10 40 20 20 60

10 10

Perform a Zag-Zig Rotation

Insert element 50

Create a new node (50) on the left of

40
node (60) and perform splaying.
The node has the grandparent and is
20 60
located on the Right-Left side.
10 50 Hence perform a Zig-Zag (Right-
Left) rotation to make the new node
as root.

Insert element 50

Perform a Zig-Zag Rotation

50

40 40 40 60

20 60 20 50 20

10 50 10 60 10

Perform a Zig-Zag Rotation

Insert element 30

Create a new node (30) on the right

50
of node (20) and perform splaying.

60
The node (30) has the grandparent
40
and is located on the Left-Right side.
20 Hence perform a Zag-Zig (Left-
Right) rotation to make the new
10 30
node as root.

Insert element 30
Perform a Zag-Zig Rotation

50 50

40 60 40 60

20 30

10 30 20

10

Perform a Zag-Zig Rotation

The new node (30) is still one level below the root node. Hence repeat the rotation
until it becomes the root.

Perform a Zig Rotation since the node (30) is on the left of the root.

50

30 60 30

20 40 20 50

10 10 40 60

Perform Zig rotation on the parent (50)

4. Deletion on Splay Tree

Firstly, traverse the tree to find the target and splay the node to make it root. Delete the
root node and combine the left and right subtree afterward. The left subtree becomes
the root if the right subtree is empty and vice versa. If it has both the left and right
subtree, the next smaller element will be identified from the right subtree and becomes
the new root.

Algorithm

1. Start the traversal from the root node to find the target node.
2. If the data element is smaller than the current node, traverse on the left subtree.
3. Otherwise, traverse on the right subtree if the data element is greater.
4. Splay the tree to bring the target node (or the last accessed node) as root. Refer to
“The Splay Operation” for detailed steps.
5. Delete the root node if the target matches and assign the new root.
No child for the target node: Set root to NULL.
 Only has the right subtree: Set root as the right subtree.
Only has the left subtree: Set root as the left subtree.
Has both left and right subtree: Find the next smaller data element (in-order
successor) node from the right subtree, splay to make this as the new root,
and link the left subtree on its left.

Code

1. // Delete the node by the given data

2. void SplayTree::remove(int data)
3. {
4. if (root == NULL) {
5. // Return if the tree is empty
6. return;
7. }
8.
9. // Traverse the tree and find the node
10. Node* p = root;
11. while(1) {
12. if (data < p->data && p->left != NULL) {
13. // Search on the left subtree for smaller elements.
14. p = p->left;
15.
16. } else if (data > p->data && p->right != NULL) {
17. // Search on the right subtree for greater elements.
18. p = p->right;
19.
20. } else {
21. // Found element
22. break;
23. }
24. }
25.
26. // Splay the target node or the last node as root
27. splay(p);
28.
29. if (data == p->data) {
30. // Delete the root node and the make it as two subtrees
31. Node* left_subtree = p->left;
32. Node* right_subtree = p->right;
33. delete p;
34.
35. // Node has either no child or one child
36. if (left_subtree != NULL && right_subtree != NULL) {
37. // Node has both left and right child.
38. // Find the smallest node on its right subtree (inorder successor)
39. Node* min;
40. for (min = right_subtree; min->left != NULL; min = min->left)
41. ;
42.
43. // Splay the inorder success node to bring it as root of the right
subtree
44. right_subtree->parent = NULL;
45. splay(min);
46.
47. // Make it as root and link left subtree on its left
48. root = min;
49. root->left = left_subtree;
50. left_subtree->parent = root;
51.
52. } else if (left_subtree == NULL) {
53. // The right child becomes root if left is NULL
54. root = right_subtree;
55. right_subtree->parent = NULL;
56.
57. } else {
58. // The left child becomes root if right is NULL
59. root = left_subtree;
60. left_subtree->parent = NULL;
61. }
62. }
 63. }

Examples

The following diagrams illustrate the deletion of nodes 60 and 30.

Delete the node (60)

The node (60) has a grandparent

30
and is located on Right-Right, so

20
perform the Zag-Zag rotation to
50
make it a root.
10 40 60 Perform Zag rotation first on the
grandparent (30)
Perform the next Zag rotation on the
parent (50)
Delete the node (60)
The target node (60) becomes the
root after Zag-Zag rotation

Zag Zag Rotation to make the node (60) the Root

60

30 50 50

20 50 30 60 30

10 40 60 20 40 20 40

10 10

Zag Zag Rotation to make the node (60) the Root

Delete the node (60) as it becomes the root now. The new root will be its left child
(50) since the right subtree is empty.

60

50 50

30 30

20 40 20 40

10 10

After Deleting the node (60)

Delete the node (30)

 The node (30) does not have the
50
grandparent and is located on the

30
Left, so perform the Zig rotation to
make it the root.
20 40 Find the node (30) and perform Zig
rotation
10 So, the target node (30) becomes
the new root
Delete the node (30)

Perform Zig Rotation and Delete the node (30)

50

30 30 30

20 40 20 50 20 50

10 10 40 10 40

Zig Rotation to delete the node (30)

Deleting the node (30) separates the left and right subtree. So we need to identify
the smaller elements on the right subtree (Inorder-successor), and splay the node
to make the Root. Finally, link the left subtree with the new root.

40

20 50 20 40 20 50

10 40 10 50 10

Merge subtrees after Splay Tree deletion

5. Search on Splay Tree

Search the data element by traversing the tree from the root node. A splay operation is
performed at the end irrespective of whether the element is found or not. Hence a
search operation can modify the splay tree to keep the recently accessed items on top.

Algorithm

1. Start the traversal from the root node to find the target node.
 2. If the data matches the current node, return the node.
3. Traverse on the left subtree if the data element is smaller than the current node,
4. Traverse on the right subtree if the data element is greater.
5. Splay the tree with the target node found or with the last accessed node. Refer to
“The Splay Operation” for detailed steps.

Code

1. // Search the node by the given data

2. Node* SplayTree::search(int data)
3. {
4. Node* p = root;
5. while(1) {
6. if (data < p->data && p->left != NULL) {
7. // Search on the left subtree for smaller elements.
8. p = p->left;
9.
10. } else if (data > p->data && p->right != NULL) {
11. // Search on the right subtree for greater elements.
12. p = p->right;
13.
14. } else {
15. // Found element
16. break;
17. }
18. }
19.
20. // Always splay the tree either with target or the last node
21. splay(p);
22.
23. // Return the node if found, NULL otherwise
24. return (data == p->data)? p : NULL;
25. }

Example

Search the node (20)

The node (20) does not have a grandparent and is located on the Left, so perform the Zig
rotation to make it the root.

40 20

20 50 10 40

10 50

Search node (20) on Splay Tree Zig rotation after Search

6. Traversals on Splay Tree

See Traversals on Binary Tree that are applicable to the Splay Tree.

7. Implementation of Splay Tree in C++

1. /**
2. * C++ example to demonstrate the Splay Tree
 3. */
4. #include <iostream>
5. #include <queue>
6. using namespace std;
7.
8. // Tree node representation
9. struct Node
10. {
11. int data; // Actual data
12. Node* left; // Pointer to left child
13. Node* right; // Pointer to right child
14. Node* parent; // Pointer to parent node
15.
16. // Node constructor
17. Node(int d, Node* pp) : data(d), left(NULL), right(NULL), parent(pp)
18. {}
19. };
20.
21. /**
22. * Splay Tree implementation
23. */
24. class SplayTree
25. {
26. // The root node
27. Node* root;
28.
29. public:
30. // Constructor
31. SplayTree() : root(NULL)
32. {}
33.
34. // Insert a new node
35. void insert(int data);
36.
37. // Delete the node by the given data
38. void remove(int data);
39.
40. // Search the node by the given data
41. Node* search(int data);
42.
43. // Preorder traversal
44. void preorder() {
45. preorder(root);
46. }
47.
48. private:
49. // Splay the tree by the given node
50. void splay(Node* x);
51. // Perform zag rotation of the given node
52. void left_rotate(Node* p);
53. // Perform zig rotation of the given node
54. void right_rotate(Node* p);
55. // Traverse the tree in preorder
56. void preorder(Node* p);
57. };
58.
59. // Splay the tree by a given node
60. void SplayTree::splay(Node* x)
61. {
62. while (x->parent != NULL) {
63. if (x->parent->parent == NULL) {
64. // Node has only parent and not grantparent
65. if (x == x->parent->left) {
66. // Node is on left: perform right rotation
67. // p x
68. // / => \
69. // x p
70. right_rotate(x->parent);
71. } else {
72. // Node is on right: perform left rotation
73. // p x
74. // \ => /
75. // x p
76. left_rotate(x->parent);
77. }
78.
 79. } else {
80. // Node has parent and grandparent
81. Node* parent = x->parent;
82. Node* grandpa = x->parent->parent;
83. if (x == parent->left && parent == grandpa->left) {
84. // Zig zig rotation: Rotate grantparent first for better balance
85. // g p x
86. // / / \ \
87. // p => x g => p
88. // / \
89. // x g
90. right_rotate(x->parent->parent);
91. right_rotate(x->parent);
92. } else if (x == parent->right && parent == grandpa->right) {
93. // Zag zag rotation: Rotate grantparent first for better balance
94. // g p x
95. // \ / \ /
96. // p => g x => p
97. // \ /
98. // x g
99. left_rotate(x->parent->parent);
100. left_rotate(x->parent);
101. } else if (x == parent->left && parent == grandpa->right) {
102. // Zig zag rotation: Rotate parent first because rotating the
103. // grantparent first would change the position of the node
104. // g g x
105. // \ \ / \
106. // p => x => g p
107. // / \
108. // x p
109. right_rotate(x->parent);
110. left_rotate(x->parent);
111. } else {
112. // Zag zig rotation: Rotate parent first because rotating the
113. // grantparent first would change the position of the node
114. // g g x
115. // / \ /
116. // p => x => g
117. // \ / \
118. // x p p
119. left_rotate(x->parent);
120. right_rotate(x->parent);
121. }
122. }
123. }
124.
125. // Make the splay node as root
126. root = x;
127. }
128.
129. // Perform zag (left) rotation of the given node
130. void SplayTree::left_rotate(Node* p)
131. {
132. // Pull up the right side node on top
133. Node* top = p->right;
134. top->parent = p->parent;
135. if (top->parent != NULL) {
136. if (p == p->parent->left) {
137. p->parent->left = top;
138. } else {
139. p->parent->right = top;
140. }
141. }
142.
143. // Link the left subtree to right of the target node p
144. p->right = top->left;
145. if (p->right) {
146. p->right->parent = p;
147. }
148.
149. // Pull down the target node p to left
150. top->left = p;
151. top->left->parent = top;
152. }
153.
154. // Perform zig rotation of the given node
155. void SplayTree::right_rotate(Node* p)
156. {
157. // Pull up the left side node on top
158. Node* top = p->left;
159. top->parent = p->parent;
160. if (top->parent != NULL) {
161. if (p == p->parent->left) {
162. p->parent->left = top;
163. } else {
164. p->parent->right = top;
165. }
166. }
167.
168. // Link the right subtree to left of the target node p
169. p->left = top->right;
170. if (p->left) {
171. p->left->parent = p;
172. }
173.
174. // Pull down the target node p to right
175. top->right = p;
176. top->right->parent = top;
177. }
178.
179. // Insert a new node
180. void SplayTree::insert(int data)
181. {
182. if (root == NULL) {
183. // Insert the first node as root and return
184. root = new Node(data, NULL);
185. return;
186. }
187.
188. Node* p = root;
189. Node* pp = NULL;
190. // Traverse the tree from the root
191. while (1) {
192. pp = p;
193. if (data < p->data) {
194. // Traverse the left subtree if the data is smaller
195. p = p->left;
196. if (p == NULL) {
197. // Insert the node on left and stop the traversal
198. p = new Node(data, pp);
199. pp->left = p;
200. break;
201. }
202. } else {
203. // Traverse the right subtree if the data is greater
204. p = p->right;
205. if (p == NULL) {
206. // Insert the node on right and stop the traversal
207. p = new Node(data, pp);
208. pp->right = p;
209. break;
210. }
211. }
212. }
213.
214. // Splay the tree to make the new node as root
215. splay(p);
216. }
217.
218. // Delete the node by the given data
219. void SplayTree::remove(int data)
220. {
221. if (root == NULL) {
222. // Return if the tree is empty
223. return;
224. }
225.
226. // Traverse the tree and find the node
227. Node* p = root;
228. while(1) {
229. if (data < p->data && p->left != NULL) {
230. // Search on the left subtree for smaller elements.
231. p = p->left;
232.
233. } else if (data > p->data && p->right != NULL) {
234. // Search on the right subtree for greater elements.
235. p = p->right;
236.
237. } else {
238. // Found element
239. break;
240. }
241. }
242.
243. // Splay the target node or the last node as root
244. splay(p);
245.
246. if (data == p->data) {
247. // Delete the root node and the make it as two subtrees
248. Node* left_subtree = p->left;
249. Node* right_subtree = p->right;
250. delete p;
251.
252. // Node has either no child or one child
253. if (left_subtree != NULL && right_subtree != NULL) {
254. // Node has both left and right child.
255. // Find the smallest node on its right subtree (inorder successor)
256. Node* min;
257. for (min = right_subtree; min->left != NULL; min = min->left)
258. ;
259.
260. // Splay the inorder success node to bring it as root of the right
subtree
261. right_subtree->parent = NULL;
262. splay(min);
263.
264. // Make it as root and link left subtree on its left
265. root = min;
266. root->left = left_subtree;
267. left_subtree->parent = root;
268.
269. } else if (left_subtree == NULL) {
270. // The right child becomes root if left is NULL
271. root = right_subtree;
272. right_subtree->parent = NULL;
273.
274. } else {
275. // The left child becomes root if right is NULL
276. root = left_subtree;
277. left_subtree->parent = NULL;
278. }
279. }
280. }
281.
282. // Search the node by the given data
283. Node* SplayTree::search(int data)
284. {
285. Node* p = root;
286. while(1) {
287. if (data < p->data && p->left != NULL) {
288. // Search on the left subtree for smaller elements.
289. p = p->left;
290.
291. } else if (data > p->data && p->right != NULL) {
292. // Search on the right subtree for greater elements.
293. p = p->right;
294.
295. } else {
296. // Found element
297. break;
298. }
299. }
300.
301. // Always splay the tree either with target or the last node
302. splay(p);
303.
304. // Return the node if found, NULL otherwise
305. return (data == p->data)? p : NULL;
 306. }
307.
308. // Traverse the tree in preorder (parent, left, right)
309. void SplayTree::preorder(Node* p)
310. {
311. if (p != NULL) {
312. cout << p->data << endl;
313. preorder(p->left);
314. preorder(p->right);
315. }
316. }
317.
318. int main()
319. {
320. // Create a Splay tree and insert data
321. SplayTree tree;
322. tree.insert(20);
323. tree.insert(10);
324. tree.insert(60);
325. tree.insert(40);
326. tree.insert(50);
327. tree.insert(30);
328. cout << "Tree after inserting 20, 10, 60, 40, 50, and 30" << endl;
329. tree.preorder();
330.
331. // Delete data
332. tree.remove(60);
333. tree.remove(30);
334. cout << "Tree after removing 60 and 30" << endl;
335. tree.preorder();
336.
337. // Search
338. Node* p = tree.search(20);
339. if (p != NULL) {
340. cout << "search(20) located node: " << p->data << endl;
341. }
342. cout << "Tree after searching 20" << endl;
343. tree.preorder();
344. }

Output

Tree after inserting 20, 10, 60, 40, 50, and 30

30
20
10
50
40
60
Tree after removing 60 and 30
40
20
10
50
search(20) located node: 20
Tree after searching 20
20
10
40
50

8. References

Splay Tree Wiki

 TAGGED TREE
PREVIOUS POST NEXT POST
AVL Tree in Data Structure Heap Tree in Data Structure

YOU MIGHT ALSO LIKE

Heap Tree in Data Structure AVL Tree in Data Structure

calendar_month April 23, 2023 calendar_month April 21, 2023
Binary Search Tree in Data
Structure
calendar_month April 20, 2023

Copyright copyright 2024 Simplerize