A Splay Tree is a roughly balanced Binary Search Tree (BST) that always keeps

the recently accessed items closer to the root node. As a result, the search
operation works must faster when the same data is accessed again.

1. Introduction
Splay Tree is not strictly balanced like the AVL Tree but is intended to work faster
for 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 tree changes for even read-only search operations.

Representation

Splay Tree Representation

 Roughly balanced: Rotations are used to bring the recently accessed

node to the root. This helps the tree be roughly balanced.
 Zig Rotation: Right rotation.
 Zag Rotation: Left rotation.

Applications

 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.

Zig Rotation of Splay Tree

2.2 Zag Rotation

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

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).

Z
ig-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).

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).

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).

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.
o Left: Zig Rotation
o Right: Zag Rotation
4. If the target node has the grandparent, perform any of the following
rotations based on its position.
o Left-Left: Zig-Zig Rotation
o Right-Right: Zag-Zag Rotation
o Right-Left: Zig-Zag Rotation
o Left-Right: Zag-Zig Rotation

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.

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 as the root node.

Insert element 10

Create a new node 10 on the left of node (20).

 Subsequently, splay the tree to make node 10 as root.

 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)
Perform a Zig Rotation from the node (20)

Insert element 60

Insert element 60

 Create a new node 60 on the right of node (10) and perform splaying.
 The node (60) has the grandparent and is located on the Right-Right side,
so perform a Zag-Zag (Left-Left) rotation.
Perform a Zag-Zag Rotation

Perform a Zag-Zag Rotation

Insert element 40
 Insert element 40

 Create a new node (40) on the right of node (20) and perform splaying.
 The node (40) has the grandparent and is located on the Left-Right side,
so perform a Zag-Zig (Left-Right) rotation.
 Here we perform the operation on the parent node first.
Perform a Zag-Zig Rotation

Perform a Zag-Zig Rotation

Insert element 50
 Insert element 50

 Create a new node (50) on the left of node (60) and perform splaying.
 The node has the grandparent and is located on the Right-Left side.
 Hence perform a Zig-Zag (Right-Left) rotation to make the new node as
root.
Perform a Zig-Zag Rotation

Perform a Zig-Zag Rotation

Insert element 30
 Insert element 30

 Create a new node (30) on the right of node (20) and perform splaying.
 The node (30) has the grandparent and is located on the Left-Right side.
 Hence perform a Zag-Zig (Left-Right) rotation to make the new node as
root.
Perform a Zag-Zig Rotation

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.
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.
o No child for the target node: Set root to NULL.
o Only has the right subtree: Set root as the right subtree.
o Only has the left subtree: Set root as the left subtree.
o 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.

Examples

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

Delete the node (60)

Delete the node (60)

 The node (60) has a grandparent and is located on Right-Right, so perform

the Zag-Zag rotation to make it a root.
 Perform Zag rotation first on the grandparent (30)
 Perform the next Zag rotation on the parent (50)
 The target node (60) becomes the root after Zag-Zag rotation
Zag Zag Rotation to make the node (60) the Root

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.
 Aft
er Deleting the node (60)

Delete the node (30)

Delete the node (30)

 The node (30) does not have the grandparent and is located on the Left,
so perform the Zig rotation to make it the root.
 Find the node (30) and perform Zig rotation
 So, the target node (30) becomes the new root
Perform Zig Rotation and Delete the node (30)
 Zi
g 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.

M
erge 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.

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.

Search node (20) on Splay Tree

Zig rotation after Search