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
-
Define a
TreeNode
class to represent nodes in the Splay Tree. Each node has data, left and right child pointers, and a parent pointer. -
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 theinsertNode
method to insert a new node while maintaining the Splay Tree properties. -
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.
-
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. -
Update the
root
of the tree after each insertion to maintain the Splay Tree properties. -
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).
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