# Splay tree deletion

Splay trees are a type of self-adjusting binary search tree that aims to provide efficient access to recently accessed elements. In a splay tree, whenever an element is accessed or searched for, it is moved to the root of the tree using a set of rotations. This helps to improve the average-case access time for frequently accessed elements. In this post, we will focus on the deletion operation in a splay tree.

## Problem Statement

The problem we're addressing is the deletion of a node from a splay tree. Given a splay tree and a value to be deleted, we need to perform the deletion while maintaining the properties of a binary search tree and performing splay operations as needed.

## Example

Let's consider the following splay tree:

``````       4
/ \
/   \
1     9
\   / \
3 7   20
/  \
13  32``````

We will perform deletion operations as follows:

1. Delete 3:

``````
1
\
4
\
9
/ \
7   20
/   \
13  32``````
2. Delete 9:

``````
7
/ \
4   20
/   /  \
1   13   32``````
3. Delete 20:

``````
13
/  \
7    32
/
4
/
1``````

## Idea to Solve

To delete a node from the splay tree, we need to follow these steps:

1. Search for the node to be deleted in the splay tree.
2. If the node is found, splay it to the root.
3. Handle the cases based on the number of children the node has:
• If the node has no left child, make its right child the new root.
• If the node has no right child, make its left child the new root.
• If the node has both left and right children, find the in-order predecessor (maximum value node in the left subtree), splay it to the root, and attach its right subtree to the root's right child.

## Pseudocode

``````DeleteNode(value):
node = FindNode(root, value)
if node is not null:
Splay(node)
if node.left is null:
root = node.right
if root is not null:
root.parent = null
else if node.right is null:
root = node.left
if root is not null:
root.parent = null
else:
predecessor = MaximumNode(node.left)
Splay(predecessor)
predecessor.right = node.right
node.right.parent = predecessor
root = predecessor
predecessor.parent = null
else:

FindNode(current, value):
if current is null or current.value equals value:
return current
if value < current.value:
return FindNode(current.left, value)
else:
return FindNode(current.right, value)

MaximumNode(current):
while current.right is not null:
current = current.right
return current

Splay(node):
while node.parent is not null:
if node.parent.parent is null:
ZigOrZagRotation(node)
else if node.parent is left child and node is left child:
ZigZigRotation(node)
else if node.parent is right child and node is right child:
ZagZagRotation(node)
else if node.parent is left child and node is right child:
ZagZigRotation(node)
else:
ZigZagRotation(node)

ZigRotation(node):
// Perform Zig rotation

ZagRotation(node):
// Perform Zag rotation

ZigZigRotation(node):
// Perform Zig Zig rotation

ZagZagRotation(node):
// Perform Zag Zag rotation

ZigZagRotation(node):
// Perform Zig Zag rotation

ZagZigRotation(node):
// Perform Zag Zig rotation``````

## Algorithm Explanation

The above pseudocode describes the process of deleting a node from a splay tree. It includes operations like searching for a node, finding the maximum node in the left subtree, and various types of splay rotations. The rotations ensure that the tree remains balanced and adheres to the properties of a binary search tree.

## Time Complexity

• The `FindNode` operation takes O(h) time, where h is the height of the tree.
• The `MaximumNode` operation takes O(h) time.
• The `Splay` operation has an amortized time complexity of O(h), where h is the height of the tree.

Overall, the deletion operation in a splay tree has a time complexity of O(h), where h is the height of the tree.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.