Splay tree insertion

The problem involves implementing a Splay Tree data structure and performing insertions while maintaining the Splay Tree properties. A Splay Tree is a self-adjusting binary search tree, where after each operation (like insertion, deletion, or lookup), the recently accessed node becomes the root of the tree. This helps improve the average-case time complexity of various operations.

Problem Statement

Given the basic structure of a Splay Tree and the operations to perform rotations (zig, zag, zig-zig, zag-zag, zig-zag, zag-zig) to maintain the tree's self-adjusting property, the task is to implement an insertion operation in the Splay Tree while preserving its properties.

Description with Example

Consider inserting the values 9, 3, 7, 13, 32, 1, and 4 into a Splay Tree. After each insertion, the tree would look like this:

Constructed Splay Tree
    ----------------------
       4
      / \
     /   \ 
    /     \
   1       9
    \     / \
    3   7   32
            /
          13

Idea to Solve the Problem

To solve this problem, we need to implement the insertion operation while ensuring that the Splay Tree properties are maintained. This involves performing rotations (zig, zag, zig-zig, zag-zag, zig-zag, zag-zig) on the tree to bring the newly inserted node to the root position. The rotations reorganize the tree to prioritize recently accessed nodes.

Class TreeNode:
    data
    left
    right
    parent
    
Class SplayTree:
    root
    
    Function zig(node):
        parent = node.parent
        parent.left = node.right
        if node.right != null:
            node.right.parent = parent
        node.right = parent
        node.parent = parent.parent
        parent.parent = node
    
    Function zag(node):
        parent = node.parent
        parent.right = node.left
        if parent.right != null:
            parent.right.parent = parent
        node.left = parent
        node.parent = parent.parent
        parent.parent = node
    
    Function zigZig(node):
        parent = node.parent
        grandParent = node.parent.parent
        parent.left = node.right
        if node.right != null:
            node.right.parent = parent
        node.right = parent
        parent.parent = node
        grandParent.left = parent.right
        if parent.right != null:
            parent.right.parent = grandParent
        parent.right = grandParent
        node.parent = grandParent.parent
        if grandParent.parent != null:
            if grandParent.parent.left == grandParent:
                grandParent.parent.left = node
            else:
                grandParent.parent.right = node
        grandParent.parent = parent
    
    Function zagZag(node):
        parent = node.parent
        grandParent = node.parent.parent
        parent.right = node.left
        if node.left != null:
            node.left.parent = parent
        node.left = parent
        node.parent = grandParent.parent
        if grandParent.parent != null:
            if grandParent.parent.left == grandParent:
                grandParent.parent.left = node
            else:
                grandParent.parent.right = node
        parent.parent = node
        grandParent.right = parent.left
        if parent.left != null:
            parent.left.parent = grandParent
        parent.left = grandParent
        grandParent.parent = parent
    
    Function zagZig(node):
        parent = node.parent
        grandParent = node.parent.parent
        parent.left = node.right
        if node.right != null:
            node.right.parent = parent
        grandParent.right = node
        node.parent = grandParent
        node.right = parent
        parent.parent = node
    
    Function zigZag(node):
        parent = node.parent
        grandParent = node.parent.parent
        parent.right = node.left
        if node.left != null:
            node.left.parent = parent
        grandParent.left = node
        node.parent = grandParent
        node.left = parent
        parent.parent = node
    
    Function applyRotation(node):
        if node.parent != null:
            if node.parent.left == node and node.parent.parent == null:
                zig(node)
            else if node.parent.right == node and node.parent.parent == null:
                zag(node)
            else if node.parent.left == node and node.parent.parent.left == node.parent:
                zigZig(node)
            else if node.parent.right == node and node.parent.parent.right == node.parent:
                zagZag(node)
            else if node.parent.right == node and node.parent.parent != null and node.parent.parent.left == node.parent:
                zigZag(node)
            else if node.parent.left == node and node.parent.parent != null and node.parent.parent.right == node.parent:
                zagZig(node)
            else:
                return
            applyRotation(node.parent)
    
    Function insertNode(data):
        node = TreeNode(data)
        if root == null:
            root = node
        else:
            temp = root
            while temp != null:
                if data > temp.data:
                    if temp.right == null:
                        temp.right = node
                        node.parent = temp
                        temp = null
                    else:
                        temp = temp.right
                else:
                    if temp.left == null:
                        temp.left = node
                        node.parent = temp
                        temp = null
                    else:
                        temp = temp.left
            applyRotation(node)
        root = node
    
    Function preOrder(node):
        if node != null:
            Print node.data
            preOrder(node.left)
            preOrder(node.right)
    
    Function inOrder(node):
        if node != null:
            inOrder(node.left)
            Print node.data
            inOrder(node.right)
    
    Function postOrder(node):
        if node != null:
            postOrder(node.left)
            postOrder(node.right)
            Print node.data
    
    Function printTree():
        if root == null:
            Print "Empty Tree"
        else:
            Print "Splay Tree"
            Print "Preorder:"
            preOrder(root)
            Print "Inorder:"
            inOrder(root)
            Print "Postorder:"
            postOrder(root)

Algorithm Explanation

1. Define a TreeNode class to represent nodes in the Splay Tree. Each node has data, left and right child pointers, and a parent pointer.

2. Define a SplayTree class to encapsulate the Splay Tree structure. The class contains methods for various rotations (zig, zag, zig-zig, zag-zag, zig-zag, zag-zig) and the insertNode method to insert a new node while maintaining the Splay Tree properties.

3. Implement rotations for different cases (zig, zag, zig-zig, zag-zag, zig-zag, zag-zig) as described in the code. These rotations are essential to bring the recently accessed node to the root position.

4. In the insertNode method, traverse the tree to find the appropriate position for the new node. Perform the necessary rotations to bring the newly inserted node to the root position.

5. Update the root of the tree after each insertion to maintain the Splay Tree properties.

6. Implement traversal methods (pre-order, in-order, post-order) to display the tree structure.

Code Solution

1) Splay tree insertion in java 2) Splay tree insertion in c++ 3) Splay tree insertion in c 4) Splay tree insertion in c# 5) Splay tree insertion in vb.net 6) Splay tree insertion in php 7) Splay tree insertion in node js 8) Splay tree insertion in typescript 9) Splay tree insertion in python 10) Splay tree insertion in ruby 11) Splay tree insertion in scala 12) Splay tree insertion in swift 13) Splay tree insertion in kotlin 14) Splay tree insertion in golang

Time Complexity

The time complexity of inserting a node into a Splay Tree depends on the height of the tree. In the worst case, the tree degenerates into a linked list, leading to an insertion time complexity of O(N), where N is the number of nodes. However, due to the self-adjusting property of the Splay Tree, the average-case time complexity for insertion and other operations is closer to O(log N).