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:
      // 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.