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:
Delete 3:
1 \ 4 \ 9 / \ 7 20 / \ 13 32
Delete 9:
7 / \ 4 20 / / \ 1 13 32
Delete 20:
13 / \ 7 32 / 4 / 1
Idea to Solve
To delete a node from the splay tree, we need to follow these steps:
- Search for the node to be deleted in the splay tree.
- If the node is found, splay it to the root.
- 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:
// Node not found
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.
Code Solution
-
1) Splay tree deletion in java
2) Splay tree deletion in c++
3) Splay tree deletion in c
4) Splay tree deletion in c#
5) Splay tree deletion in vb.net
6) Splay tree deletion in php
7) Splay tree deletion in node js
8) Splay tree deletion in typescript
9) Splay tree deletion in python
10) Splay tree deletion in ruby
11) Splay tree deletion in scala
12) Splay tree deletion in swift
13) Splay tree deletion in kotlin
14) Splay tree deletion in golang
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.
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.
New Comment