Posted on by Kalkicode
Code Tree

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

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

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

Categories
Relative Post