Splay tree insertion

Here given code implementation process.

// C Program
// Splay tree insertion
#include <stdio.h>
#include <stdlib.h>

//Node of splay tree
struct Node
{
	int data;
	struct Node *left, *right, *parent;
};
//Create a new node and return created node
struct Node *create_node(int data)
{
	//Create node memory using malloc
	struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
	if (new_node != NULL)
	{
		//Add left right and parent node value
		new_node->left = NULL;
		new_node->right = NULL;
		new_node->parent = NULL;
		//Assign Data value
		new_node->data = data;
	}
	else
	{
		printf("\n Memory Overflow ");
	}
	return new_node;
}
//Zig Rotation
void zig(struct Node *node)
{
	//Get the parent node 
	struct Node *parent = node->parent;
	// Change left subtree of parent node 
	// (This new subtree is right-subtree of given current node)
	parent->left = node->right;
	if (node->right != NULL)
	{
		//When add subtree not empty then change parent value
		node->right->parent = parent;
	}
	// Change parent node value
	node->right = parent;
	node->parent = parent->parent;
	parent->parent = node;
}
/*Zag Rotation*/
void zag(struct Node *node)
{
	//Get the parent node 
	struct Node *parent = node->parent;
	parent->right = node->left;
	if (parent->right != NULL)
	{
		//When add subtree not empty then change parent value
		parent->right->parent = parent;
	}
	// change parent node value
	node->left = parent;
	node->parent = parent->parent;
	parent->parent = node;
}
//Zig Zig rotation
void zig_zig(struct Node *node)
{
	//Get the parent node 
	struct Node *parent = node->parent;
	struct Node *grand_parent = node->parent->parent;
	parent->left = node->right;
	if (node->right != NULL)
	{
		//When add subtree not empty then change parent value
		node->right->parent = parent;
	}
	node->right = parent;
	parent->parent = node;
	grand_parent->left = parent->right;
	if (parent->right != NULL)
	{
		parent->right->parent = grand_parent;
	}
	parent->right = grand_parent;
	node->parent = grand_parent->parent;
	if (grand_parent->parent)
	{
		if (grand_parent->parent->left != NULL && grand_parent->parent->left == grand_parent)
		{
			grand_parent->parent->left = node;
		}
		else
		{
			grand_parent->parent->right = node;
		}
	}
	grand_parent->parent = parent;
}
//zag_zag rotation
void zag_zag(struct Node *node)
{
	//Get the parent node 
	struct Node *parent = node->parent;
	struct Node *grand_parent = node->parent->parent;
	parent->right = node->left;
	if (node->left != NULL)
	{
		//When add subtree not empty then change parent value
		node->left->parent = parent;
	}
	node->left = parent;
	node->parent = grand_parent->parent;
	if (grand_parent->parent)
	{
		if (grand_parent->parent->left != NULL && grand_parent->parent->left == grand_parent)
		{
			grand_parent->parent->left = node;
		}
		else
		{
			grand_parent->parent->right = node;
		}
	}
	parent->parent = node;
	grand_parent->right = parent->left;
	if (parent->left != NULL)
	{
		parent->left->parent = grand_parent;
	}
	parent->left = grand_parent;
	grand_parent->parent = parent;
}
// Zag zig rotation
void zag_zig(struct Node *node)
{
	//Get the parent node 
	struct Node *parent = node->parent;
	struct Node *grand_parent = node->parent->parent;
	parent->left = node->right;
	if (node->right != NULL)
	{
		//When add subtree not empty then change parent value
		node->right->parent = parent;
	}
	grand_parent->right = node;
	node->parent = grand_parent;
	node->right = parent;
	parent->parent = node;
}
// Zig zag rotation
void zig_zag(struct Node *node)
{
	//Get the parent node 
	struct Node *parent = node->parent;
	struct Node *grand_parent = node->parent->parent;
	parent->right = node->left;
	if (node->left != NULL)
	{
		//When add subtree not empty then change parent value
		node->left->parent = parent;
	}
	grand_parent->left = node;
	node->parent = grand_parent;
	node->left = parent;
	parent->parent = node;
}
// Check of the which rotation are required to given node as a root of tree.
// Perform basic 6 rotation
void check_rotation(struct Node *node)
{
	if (node->parent != NULL)
	{
		// Zig rotation condition
		if (node->parent->left != NULL && node->parent->left == node && node->parent->parent == NULL)
		{
			zig(node);
		}
		// Zag rotation condition
		else if (node->parent->right != NULL && node->parent->right == node && node->parent->parent == NULL)
		{
			zag(node);
		}
		// Zig Zig rotation condition 
		else if (node->parent->left != NULL && node->parent->left == node && node->parent->parent->left != NULL && node->parent->parent->left == node->parent)
		{
			zig_zig(node);
		}
		//Zag Zag rotation condition
		else if (node->parent->right != NULL && node->parent->right == node && node->parent->parent->right != NULL && node->parent->parent->right == node->parent)
		{
			zag_zag(node);
		}
		//Zig Zag rotation condition
		else if (node->parent->right != NULL && node->parent->right == node && node->parent->parent != NULL && node->parent->parent->left != NULL && node->parent->parent->left == node->parent)
		{
			zig_zag(node);
		}
		//Zag Zig rotation condition
		else if (node->parent->left != NULL && node->parent->left == node && node->parent->parent && node->parent->parent->right != NULL && node->parent->parent->right == node->parent)
		{
			zag_zig(node);
		}
		else
		{
			return;
		}
		check_rotation(node);
	}
}
//Create a new node and converting into splay tree
struct Node *insert_node(struct Node *root, int data)
{
	// Get new node of tree
	struct Node *new_node = create_node(data);
	struct Node *temp = NULL;
	if (new_node != NULL)
	{
		if (root == NULL)
		{
			// When splay tree empty then return first node
			return new_node;
		}
		else
		{
			temp = root;
			//Insert new node at proper position this is similar to BST
			while (temp != NULL)
			{
				//Check whether inserted value is greater than tree current node data
				if (data > temp->data)
				{
					//if insert value are greater to current node value
					if (temp->right == NULL)
					{
						//If current node Right child is NULL. 
						//insert new node to this position
						temp->right = new_node;
						new_node->parent = temp;
						temp = NULL;
					}
					else
					{
						//Visit right child
						temp = temp->right;
					}
				}
				else
				{
					if (temp->left == NULL)
					{
						// If current node left child is NULL. 
						// insert new node to this position
						temp->left = new_node;
						new_node->parent = temp;
						temp = NULL;
					}
					else
					{
						//Visit left child
						temp = temp->left;
					}
				}
			}
			//make this newly node as root node of tree
			check_rotation(new_node);
		}
	}
	else
	{
		printf("\n Memory Overflow");
	}
	return new_node;
}
/*Display pre order splay tree data*/
void pre_order(struct Node *temp)
{
	if (temp != NULL)
	{
		printf("  %d", temp->data);
		pre_order(temp->left);
		pre_order(temp->right);
	}
}
/*Display in order splay tree data*/
void in_order(struct Node *temp)
{
	if (temp != NULL)
	{
		in_order(temp->left);
		printf("  %d", temp->data);
		in_order(temp->right);
	}
}
/*Display post order splay tree data*/
void post_order(struct Node *temp)
{
	if (temp != NULL)
	{
		post_order(temp->left);
		post_order(temp->right);
		printf("  %d", temp->data);
	}
}
void print_tree(struct Node *root)
{
	if (root == NULL)
	{
		printf("\n Empty Tree \n");
	}
	else
	{
		printf("\nSplay Tree ");
		printf("\nPreorder  :");
		pre_order(root);
		printf("\nInorder   :");
		in_order(root);
		printf("\nPostorder :");
		post_order(root);
	}
}
/*Main function*/
int main()
{
	struct Node *root = NULL;
	//Add tree node
	root = insert_node(root, 9);
	root = insert_node(root, 3);
	root = insert_node(root, 7);
	root = insert_node(root, 13);
	root = insert_node(root, 32);
	root = insert_node(root, 1);
	root = insert_node(root, 4);
	/*
	  Constructed Splay Tree
	  ----------------------

	    4
	  /    \
	 1      9
	  \    / \
	   3  7   32
	         /
	        13 
	*/
	print_tree(root);
	return 0;
}

Output

Splay Tree
Preorder  :  4  1  3  9  7  32  13
Inorder   :  1  3  4  7  9  13  32
Postorder :  3  1  7  13  32  9  4
// Java program
// Splay Tree insertion

//Splay tree node
class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node parent;
	public Node(int data)
	{
		//Set node value of Splay-Tree
		this.data = data;
		this.left = null;
		this.right = null;
		this.parent = null;
	}
}
class SplayTree
{
	public Node root;
	public SplayTree()
	{
		this.root = null;
	}
	//Zig Rotation
	public void zig(Node node)
	{
		//Get the parent node 
		Node parent = node.parent;
		// Change left subtree of parent node 
		// (This new subtree is right-subtree of given current node)
		parent.left = node.right;
		if (node.right != null)
		{
			//When add subtree not empty then change parent value
			node.right.parent = parent;
		}
		// Change parent node value
		node.right = parent;
		node.parent = parent.parent;
		parent.parent = node;
	}
	//zag rotation
	public void zag(Node node)
	{
		//Get the parent node 
		Node parent = node.parent;
		parent.right = node.left;
		if (parent.right != null)
		{
			//When add subtree not empty then change parent value
			parent.right.parent = parent;
		}
		// change parent node value
		node.left = parent;
		node.parent = parent.parent;
		parent.parent = node;
	}
	//zig zig rotation
	public void zig_zig(Node node)
	{
		//Get the parent node 
		Node parent = node.parent;
		Node grand_parent = node.parent.parent;
		parent.left = node.right;
		if (node.right != null)
		{
			//When add subtree not empty then change parent value
			node.right.parent = parent;
		}
		node.right = parent;
		parent.parent = node;
		grand_parent.left = parent.right;
		if (parent.right != null)
		{
			parent.right.parent = grand_parent;
		}
		parent.right = grand_parent;
		node.parent = grand_parent.parent;
		if (grand_parent.parent != null)
		{
			if (grand_parent.parent.left != null && grand_parent.parent.left == grand_parent)
			{
				grand_parent.parent.left = node;
			}
			else
			{
				grand_parent.parent.right = node;
			}
		}
		grand_parent.parent = parent;
	}
	//zag_zag rotation
	public void zag_zag(Node node)
	{
		//Get the parent node 
		Node parent = node.parent;
		Node grand_parent = node.parent.parent;
		parent.right = node.left;
		if (node.left != null)
		{
			//When add subtree not empty then change parent value
			node.left.parent = parent;
		}
		node.left = parent;
		node.parent = grand_parent.parent;
		if (grand_parent.parent != null)
		{
			if (grand_parent.parent.left != null && grand_parent.parent.left == grand_parent)
			{
				grand_parent.parent.left = node;
			}
			else
			{
				grand_parent.parent.right = node;
			}
		}
		parent.parent = node;
		grand_parent.right = parent.left;
		if (parent.left != null)
		{
			parent.left.parent = grand_parent;
		}
		parent.left = grand_parent;
		grand_parent.parent = parent;
	}
	// Zag zig rotation
	public void zag_zig(Node node)
	{
		//Get the parent node 
		Node parent = node.parent;
		Node grand_parent = node.parent.parent;
		parent.left = node.right;
		if (node.right != null)
		{
			//When add subtree not empty then change parent value
			node.right.parent = parent;
		}
		grand_parent.right = node;
		node.parent = grand_parent;
		node.right = parent;
		parent.parent = node;
	}
	// Zig zag rotation
	public void zig_zag(Node node)
	{
		//Get the parent node 
		Node parent = node.parent;
		Node grand_parent = node.parent.parent;
		parent.right = node.left;
		if (node.left != null)
		{
			//When add subtree not empty then change parent value
			node.left.parent = parent;
		}
		grand_parent.left = node;
		node.parent = grand_parent;
		node.left = parent;
		parent.parent = node;
	}
	// Check of the which rotation are required to given node as a root of tree.
	// Perform basic 6 rotation
	public void check_rotation(Node node)
	{
		if (node.parent != null)
		{
			// Zig rotation condition
			if (node.parent.left != null && node.parent.left == node && node.parent.parent == null)
			{
				zig(node);
			}
			// Zag rotation condition
			else if (node.parent.right != null && node.parent.right == node && node.parent.parent == null)
			{
				zag(node);
			}
			// Zig Zig rotation condition 
			else if (node.parent.left != null && node.parent.left == node && node.parent.parent.left != null && node.parent.parent.left == node.parent)
			{
				zig_zig(node);
			}
			//Zag Zag rotation condition
			else if (node.parent.right != null && node.parent.right == node && node.parent.parent.right != null && node.parent.parent.right == node.parent)
			{
				zag_zag(node);
			}
			//Zig Zag rotation condition
			else if (node.parent.right != null && node.parent.right == node && node.parent.parent != null && node.parent.parent.left != null && node.parent.parent.left == node.parent)
			{
				zig_zag(node);
			}
			//Zag Zig rotation condition
			else if (node.parent.left != null && node.parent.left == node && node.parent.parent != null && node.parent.parent.right != null && node.parent.parent.right == node.parent)
			{
				zag_zig(node);
			}
			else
			{
				return;
			}
			check_rotation(node);
		}
	}
	//Create a new node and converting into splay tree
	public void insert_node(int data)
	{
		// Get new node of tree
		Node new_node = new Node(data);
		Node temp = null;
		if (this.root == null)
		{
			// When splay tree empty then this is first node
			this.root = new_node;
		}
		else
		{
			temp = root;
			//Insert new node at proper position this is similar to BST
			while (temp != null)
			{
				//Check whether inserted value is greater than tree current node data
				if (data > temp.data)
				{
					//if insert value are greater to current node value
					if (temp.right == null)
					{
						//If current node Right child is null. 
						//insert new node to this position
						temp.right = new_node;
						new_node.parent = temp;
						temp = null;
					}
					else
					{
						//Visit right child
						temp = temp.right;
					}
				}
				else
				{
					if (temp.left == null)
					{
						// If current node left child is null. 
						// insert new node to this position
						temp.left = new_node;
						new_node.parent = temp;
						temp = null;
					}
					else
					{
						//Visit left child
						temp = temp.left;
					}
				}
			}
			//make this newly node as root node of tree
			check_rotation(new_node);
		}
		this.root = new_node;
	}
	public void pre_order(Node temp)
	{
		if (temp != null)
		{
			System.out.print("  " + temp.data);
			pre_order(temp.left);
			pre_order(temp.right);
		}
	}
	public void in_order(Node temp)
	{
		if (temp != null)
		{
			in_order(temp.left);
			System.out.print("  " + temp.data);
			in_order(temp.right);
		}
	}
	public void post_order(Node temp)
	{
		if (temp != null)
		{
			post_order(temp.left);
			post_order(temp.right);
			System.out.print("  " + temp.data);
		}
	}
	//This are handling the request to display tree elements
	public void print_tree()
	{
		if (this.root == null)
		{
			System.out.print("\n Empty Tree \n");
		}
		else
		{
			System.out.print("\nSplay Tree ");
			System.out.print("\nPreorder  :");
			pre_order(this.root);
			System.out.print("\nInorder   :");
			in_order(this.root);
			System.out.print("\nPostorder :");
			post_order(this.root);
		}
	}
	public static void main(String[] args)
	{
		SplayTree obj = new SplayTree();
		//Add tree node
		obj.insert_node(9);
		obj.insert_node(3);
		obj.insert_node(7);
		obj.insert_node(13);
		obj.insert_node(32);
		obj.insert_node(1);
		obj.insert_node(4);
		/*
		    Constructed Splay Tree
		    ----------------------

		      4
		    /    \
		   1      9
		    \    / \
		     3  7   32
		           /
		          13 
		*/
		obj.print_tree();
	}
}

Output

Splay Tree
Preorder  :  4  1  3  9  7  32  13
Inorder   :  1  3  4  7  9  13  32
Postorder :  3  1  7  13  32  9  4
//Include header file
#include <iostream>
using namespace std;

// C++ program
// Splay Tree insertion

//Splay tree node
class Node
{
	public: int data;
	Node * left;
	Node * right;
	Node * parent;
	Node(int data)
	{
		//Set node value of Splay-Tree
		this->data = data;
		this->left = NULL;
		this->right = NULL;
		this->parent = NULL;
	}
};
class SplayTree
{
	public: Node * root;
	SplayTree()
	{
		this->root = NULL;
	}
	//Zig Rotation
	void zig(Node * node)
	{
		//Get the parent node 
		Node * parent = node->parent;
		// Change left subtree of parent node 
		// (This new subtree is right-subtree of given current node)
		parent->left = node->right;
		if (node->right != NULL)
		{
			//When add subtree not empty then change parent value
			node->right->parent = parent;
		}
		// Change parent node value
		node->right = parent;
		node->parent = parent->parent;
		parent->parent = node;
	}
	//zag rotation
	void zag(Node * node)
	{
		//Get the parent node 
		Node * parent = node->parent;
		parent->right = node->left;
		if (parent->right != NULL)
		{
			//When add subtree not empty then change parent value
			parent->right->parent = parent;
		}
		// change parent node value
		node->left = parent;
		node->parent = parent->parent;
		parent->parent = node;
	}
	//zig zig rotation
	void zig_zig(Node * node)
	{
		//Get the parent node 
		Node * parent = node->parent;
		Node * grand_parent = node->parent->parent;
		parent->left = node->right;
		if (node->right != NULL)
		{
			//When add subtree not empty then change parent value
			node->right->parent = parent;
		}
		node->right = parent;
		parent->parent = node;
		grand_parent->left = parent->right;
		if (parent->right != NULL)
		{
			parent->right->parent = grand_parent;
		}
		parent->right = grand_parent;
		node->parent = grand_parent->parent;
		if (grand_parent->parent != NULL)
		{
			if (grand_parent->parent->left != NULL && grand_parent->parent->left == grand_parent)
			{
				grand_parent->parent->left = node;
			}
			else
			{
				grand_parent->parent->right = node;
			}
		}
		grand_parent->parent = parent;
	}
	//zag_zag rotation
	void zag_zag(Node * node)
	{
		//Get the parent node 
		Node * parent = node->parent;
		Node * grand_parent = node->parent->parent;
		parent->right = node->left;
		if (node->left != NULL)
		{
			//When add subtree not empty then change parent value
			node->left->parent = parent;
		}
		node->left = parent;
		node->parent = grand_parent->parent;
		if (grand_parent->parent != NULL)
		{
			if (grand_parent->parent->left != NULL && grand_parent->parent->left == grand_parent)
			{
				grand_parent->parent->left = node;
			}
			else
			{
				grand_parent->parent->right = node;
			}
		}
		parent->parent = node;
		grand_parent->right = parent->left;
		if (parent->left != NULL)
		{
			parent->left->parent = grand_parent;
		}
		parent->left = grand_parent;
		grand_parent->parent = parent;
	}
	// Zag zig rotation
	void zag_zig(Node * node)
	{
		//Get the parent node 
		Node * parent = node->parent;
		Node * grand_parent = node->parent->parent;
		parent->left = node->right;
		if (node->right != NULL)
		{
			//When add subtree not empty then change parent value
			node->right->parent = parent;
		}
		grand_parent->right = node;
		node->parent = grand_parent;
		node->right = parent;
		parent->parent = node;
	}
	// Zig zag rotation
	void zig_zag(Node * node)
	{
		//Get the parent node 
		Node * parent = node->parent;
		Node * grand_parent = node->parent->parent;
		parent->right = node->left;
		if (node->left != NULL)
		{
			//When add subtree not empty then change parent value
			node->left->parent = parent;
		}
		grand_parent->left = node;
		node->parent = grand_parent;
		node->left = parent;
		parent->parent = node;
	}
	// Check of the which rotation are required to given node as a root of tree.
	// Perform basic 6 rotation
	void check_rotation(Node * node)
	{
		if (node->parent != NULL)
		{
			// Zig rotation condition
			if (node->parent->left != NULL && node->parent->left == node && node->parent->parent == NULL)
			{
				this->zig(node);
			}
			// Zag rotation condition
			else if (node->parent->right != NULL && node->parent->right == node && node->parent->parent == NULL)
			{
				this->zag(node);
			}
			// Zig Zig rotation condition 
			else if (node->parent->left != NULL && node->parent->left == node && node->parent->parent->left != NULL && node->parent->parent->left == node->parent)
			{
				this->zig_zig(node);
			}
			//Zag Zag rotation condition
			else if (node->parent->right != NULL && node->parent->right == node && node->parent->parent->right != NULL && node->parent->parent->right == node->parent)
			{
				this->zag_zag(node);
			}
			//Zig Zag rotation condition
			else if (node->parent->right != NULL && node->parent->right == node && node->parent->parent != NULL && node->parent->parent->left != NULL && node->parent->parent->left == node->parent)
			{
				this->zig_zag(node);
			}
			//Zag Zig rotation condition
			else if (node->parent->left != NULL && node->parent->left == node && node->parent->parent != NULL && node->parent->parent->right != NULL && node->parent->parent->right == node->parent)
			{
				this->zag_zig(node);
			}
			else
			{
				return;
			}
			this->check_rotation(node);
		}
	}
	//Create a new node and converting into splay tree
	void insert_node(int data)
	{
		// Get new node of tree
		Node * new_node = new Node(data);
		Node * temp = NULL;
		if (this->root == NULL)
		{
			// When splay tree empty then this is first node
			this->root = new_node;
		}
		else
		{
			temp = this->root;
			//Insert new node at proper position this is similar to BST
			while (temp != NULL)
			{
				//Check whether inserted value is greater than tree current node data
				if (data > temp->data)
				{
					//if insert value are greater to current node value
					if (temp->right == NULL)
					{
						//If current node Right child is null. 
						//insert new node to this position
						temp->right = new_node;
						new_node->parent = temp;
						temp = NULL;
					}
					else
					{
						//Visit right child
						temp = temp->right;
					}
				}
				else
				{
					if (temp->left == NULL)
					{
						// If current node left child is null. 
						// insert new node to this position
						temp->left = new_node;
						new_node->parent = temp;
						temp = NULL;
					}
					else
					{
						//Visit left child
						temp = temp->left;
					}
				}
			}
			//make this newly node as root node of tree
			this->check_rotation(new_node);
		}
		this->root = new_node;
	}
	void pre_order(Node * temp)
	{
		if (temp != NULL)
		{
			cout << "  " << temp->data;
			this->pre_order(temp->left);
			this->pre_order(temp->right);
		}
	}
	void in_order(Node * temp)
	{
		if (temp != NULL)
		{
			this->in_order(temp->left);
			cout << "  " << temp->data;
			this->in_order(temp->right);
		}
	}
	void post_order(Node * temp)
	{
		if (temp != NULL)
		{
			this->post_order(temp->left);
			this->post_order(temp->right);
			cout << "  " << temp->data;
		}
	}
	//This are handling the request to display tree elements
	void print_tree()
	{
		if (this->root == NULL)
		{
			cout << "\n Empty Tree \n";
		}
		else
		{
			cout << "\nSplay Tree ";
			cout << "\nPreorder  :";
			this->pre_order(this->root);
			cout << "\nInorder   :";
			this->in_order(this->root);
			cout << "\nPostorder :";
			this->post_order(this->root);
		}
	}
};
int main()
{
	SplayTree obj = SplayTree();
	//Add tree node
	obj.insert_node(9);
	obj.insert_node(3);
	obj.insert_node(7);
	obj.insert_node(13);
	obj.insert_node(32);
	obj.insert_node(1);
	obj.insert_node(4);
	/*
			    Constructed Splay Tree
			    ----------------------

			      4
			    /    \
			   1      9
			    \    / \
			     3  7   32
			           /
			          13 
	*/
	obj.print_tree();
	return 0;
}

Output

Splay Tree
Preorder  :  4  1  3  9  7  32  13
Inorder   :  1  3  4  7  9  13  32
Postorder :  3  1  7  13  32  9  4
//Include namespace system
using System;

// C# program
// Splay Tree insertion

//Splay tree node
class Node
{
	public int data;
	public Node left;
	public Node right;
	public Node parent;
	public Node(int data)
	{
		//Set node value of Splay-Tree
		this.data = data;
		this.left = null;
		this.right = null;
		this.parent = null;
	}
}
class SplayTree
{
	public Node root;
	public SplayTree()
	{
		this.root = null;
	}
	//Zig Rotation
	public void zig(Node node)
	{
		//Get the parent node 
		Node parent = node.parent;
		// Change left subtree of parent node 
		// (This new subtree is right-subtree of given current node)
		parent.left = node.right;
		if (node.right != null)
		{
			//When add subtree not empty then change parent value
			node.right.parent = parent;
		}
		// Change parent node value
		node.right = parent;
		node.parent = parent.parent;
		parent.parent = node;
	}
	//zag rotation
	public void zag(Node node)
	{
		//Get the parent node 
		Node parent = node.parent;
		parent.right = node.left;
		if (parent.right != null)
		{
			//When add subtree not empty then change parent value
			parent.right.parent = parent;
		}
		// change parent node value
		node.left = parent;
		node.parent = parent.parent;
		parent.parent = node;
	}
	//zig zig rotation
	public void zig_zig(Node node)
	{
		//Get the parent node 
		Node parent = node.parent;
		Node grand_parent = node.parent.parent;
		parent.left = node.right;
		if (node.right != null)
		{
			//When add subtree not empty then change parent value
			node.right.parent = parent;
		}
		node.right = parent;
		parent.parent = node;
		grand_parent.left = parent.right;
		if (parent.right != null)
		{
			parent.right.parent = grand_parent;
		}
		parent.right = grand_parent;
		node.parent = grand_parent.parent;
		if (grand_parent.parent != null)
		{
			if (grand_parent.parent.left != null && grand_parent.parent.left == grand_parent)
			{
				grand_parent.parent.left = node;
			}
			else
			{
				grand_parent.parent.right = node;
			}
		}
		grand_parent.parent = parent;
	}
	//zag_zag rotation
	public void zag_zag(Node node)
	{
		//Get the parent node 
		Node parent = node.parent;
		Node grand_parent = node.parent.parent;
		parent.right = node.left;
		if (node.left != null)
		{
			//When add subtree not empty then change parent value
			node.left.parent = parent;
		}
		node.left = parent;
		node.parent = grand_parent.parent;
		if (grand_parent.parent != null)
		{
			if (grand_parent.parent.left != null && grand_parent.parent.left == grand_parent)
			{
				grand_parent.parent.left = node;
			}
			else
			{
				grand_parent.parent.right = node;
			}
		}
		parent.parent = node;
		grand_parent.right = parent.left;
		if (parent.left != null)
		{
			parent.left.parent = grand_parent;
		}
		parent.left = grand_parent;
		grand_parent.parent = parent;
	}
	// Zag zig rotation
	public void zag_zig(Node node)
	{
		//Get the parent node 
		Node parent = node.parent;
		Node grand_parent = node.parent.parent;
		parent.left = node.right;
		if (node.right != null)
		{
			//When add subtree not empty then change parent value
			node.right.parent = parent;
		}
		grand_parent.right = node;
		node.parent = grand_parent;
		node.right = parent;
		parent.parent = node;
	}
	// Zig zag rotation
	public void zig_zag(Node node)
	{
		//Get the parent node 
		Node parent = node.parent;
		Node grand_parent = node.parent.parent;
		parent.right = node.left;
		if (node.left != null)
		{
			//When add subtree not empty then change parent value
			node.left.parent = parent;
		}
		grand_parent.left = node;
		node.parent = grand_parent;
		node.left = parent;
		parent.parent = node;
	}
	// Check of the which rotation are required to given node as a root of tree.
	// Perform basic 6 rotation
	public void check_rotation(Node node)
	{
		if (node.parent != null)
		{
			// Zig rotation condition
			if (node.parent.left != null && node.parent.left == node && node.parent.parent == null)
			{
				zig(node);
			}
			// Zag rotation condition
			else if (node.parent.right != null && node.parent.right == node && node.parent.parent == null)
			{
				zag(node);
			}
			// Zig Zig rotation condition 
			else if (node.parent.left != null && node.parent.left == node && node.parent.parent.left != null && node.parent.parent.left == node.parent)
			{
				zig_zig(node);
			}
			//Zag Zag rotation condition
			else if (node.parent.right != null && node.parent.right == node && node.parent.parent.right != null && node.parent.parent.right == node.parent)
			{
				zag_zag(node);
			}
			//Zig Zag rotation condition
			else if (node.parent.right != null && node.parent.right == node && node.parent.parent != null && node.parent.parent.left != null && node.parent.parent.left == node.parent)
			{
				zig_zag(node);
			}
			//Zag Zig rotation condition
			else if (node.parent.left != null && node.parent.left == node && node.parent.parent != null && node.parent.parent.right != null && node.parent.parent.right == node.parent)
			{
				zag_zig(node);
			}
			else
			{
				return;
			}
			check_rotation(node);
		}
	}
	//Create a new node and converting into splay tree
	public void insert_node(int data)
	{
		// Get new node of tree
		Node new_node = new Node(data);
		Node temp = null;
		if (this.root == null)
		{
			// When splay tree empty then this is first node
			this.root = new_node;
		}
		else
		{
			temp = root;
			//Insert new node at proper position this is similar to BST
			while (temp != null)
			{
				//Check whether inserted value is greater than tree current node data
				if (data > temp.data)
				{
					//if insert value are greater to current node value
					if (temp.right == null)
					{
						//If current node Right child is null. 
						//insert new node to this position
						temp.right = new_node;
						new_node.parent = temp;
						temp = null;
					}
					else
					{
						//Visit right child
						temp = temp.right;
					}
				}
				else
				{
					if (temp.left == null)
					{
						// If current node left child is null. 
						// insert new node to this position
						temp.left = new_node;
						new_node.parent = temp;
						temp = null;
					}
					else
					{
						//Visit left child
						temp = temp.left;
					}
				}
			}
			//make this newly node as root node of tree
			check_rotation(new_node);
		}
		this.root = new_node;
	}
	public void pre_order(Node temp)
	{
		if (temp != null)
		{
			Console.Write("  " + temp.data);
			pre_order(temp.left);
			pre_order(temp.right);
		}
	}
	public void in_order(Node temp)
	{
		if (temp != null)
		{
			in_order(temp.left);
			Console.Write("  " + temp.data);
			in_order(temp.right);
		}
	}
	public void post_order(Node temp)
	{
		if (temp != null)
		{
			post_order(temp.left);
			post_order(temp.right);
			Console.Write("  " + temp.data);
		}
	}
	//This are handling the request to display tree elements
	public void print_tree()
	{
		if (this.root == null)
		{
			Console.Write("\n Empty Tree \n");
		}
		else
		{
			Console.Write("\nSplay Tree ");
			Console.Write("\nPreorder  :");
			pre_order(this.root);
			Console.Write("\nInorder   :");
			in_order(this.root);
			Console.Write("\nPostorder :");
			post_order(this.root);
		}
	}
	public static void Main(String[] args)
	{
		SplayTree obj = new SplayTree();
		//Add tree node
		obj.insert_node(9);
		obj.insert_node(3);
		obj.insert_node(7);
		obj.insert_node(13);
		obj.insert_node(32);
		obj.insert_node(1);
		obj.insert_node(4);
		/*
				    Constructed Splay Tree
				    ----------------------

				      4
				    /    \
				   1      9
				    \    / \
				     3  7   32
				           /
				          13 
				*/
		obj.print_tree();
	}
}

Output

Splay Tree
Preorder  :  4  1  3  9  7  32  13
Inorder   :  1  3  4  7  9  13  32
Postorder :  3  1  7  13  32  9  4
<?php
// Php program
// Splay Tree insertion

//Splay tree node
class Node
{
	public $data;
	public $left;
	public $right;
	public $parent;

	function __construct($data)
	{
		//Set node value of Splay-Tree
		$this->data = $data;
		$this->left = null;
		$this->right = null;
		$this->parent = null;
	}
}
class SplayTree
{
	public $root;

	function __construct()
	{
		$this->root = null;
	}
	//Zig Rotation
	public	function zig($node)
	{
		//Get the parent node 
		$parent = $node->parent;
		// Change left subtree of parent node 
		// (This new subtree is right-subtree of given current node)
		$parent->left = $node->right;
		if ($node->right != null)
		{
			//When add subtree not empty then change parent value
			$node->right->parent = $parent;
		}
		// Change parent node value
		$node->right = $parent;
		$node->parent = $parent->parent;
		$parent->parent = $node;
	}
	//zag rotation
	public	function zag($node)
	{
		//Get the parent node 
		$parent = $node->parent;
		$parent->right = $node->left;
		if ($parent->right != null)
		{
			//When add subtree not empty then change parent value
			$parent->right->parent = $parent;
		}
		// change parent node value
		$node->left = $parent;
		$node->parent = $parent->parent;
		$parent->parent = $node;
	}
	//zig zig rotation
	public	function zig_zig($node)
	{
		//Get the parent node 
		$parent = $node->parent;
		$grand_parent = $node->parent->parent;
		$parent->left = $node->right;
		if ($node->right != null)
		{
			//When add subtree not empty then change parent value
			$node->right->parent = $parent;
		}
		$node->right = $parent;
		$parent->parent = $node;
		$grand_parent->left = $parent->right;
		if ($parent->right != null)
		{
			$parent->right->parent = $grand_parent;
		}
		$parent->right = $grand_parent;
		$node->parent = $grand_parent->parent;
		if ($grand_parent->parent != null)
		{
			if ($grand_parent->parent->left != null && $grand_parent->parent->left == $grand_parent)
			{
				$grand_parent->parent->left = $node;
			}
			else
			{
				$grand_parent->parent->right = $node;
			}
		}
		$grand_parent->parent = $parent;
	}
	//zag_zag rotation
	public	function zag_zag($node)
	{
		//Get the parent node 
		$parent = $node->parent;
		$grand_parent = $node->parent->parent;
		$parent->right = $node->left;
		if ($node->left != null)
		{
			//When add subtree not empty then change parent value
			$node->left->parent = $parent;
		}
		$node->left = $parent;
		$node->parent = $grand_parent->parent;
		if ($grand_parent->parent != null)
		{
			if ($grand_parent->parent->left != null && $grand_parent->parent->left == $grand_parent)
			{
				$grand_parent->parent->left = $node;
			}
			else
			{
				$grand_parent->parent->right = $node;
			}
		}
		$parent->parent = $node;
		$grand_parent->right = $parent->left;
		if ($parent->left != null)
		{
			$parent->left->parent = $grand_parent;
		}
		$parent->left = $grand_parent;
		$grand_parent->parent = $parent;
	}
	// Zag zig rotation
	public	function zag_zig($node)
	{
		//Get the parent node 
		$parent = $node->parent;
		$grand_parent = $node->parent->parent;
		$parent->left = $node->right;
		if ($node->right != null)
		{
			//When add subtree not empty then change parent value
			$node->right->parent = $parent;
		}
		$grand_parent->right = $node;
		$node->parent = $grand_parent;
		$node->right = $parent;
		$parent->parent = $node;
	}
	// Zig zag rotation
	public	function zig_zag($node)
	{
		//Get the parent node 
		$parent = $node->parent;
		$grand_parent = $node->parent->parent;
		$parent->right = $node->left;
		if ($node->left != null)
		{
			//When add subtree not empty then change parent value
			$node->left->parent = $parent;
		}
		$grand_parent->left = $node;
		$node->parent = $grand_parent;
		$node->left = $parent;
		$parent->parent = $node;
	}
	// Check of the which rotation are required to given node as a root of tree.
	// Perform basic 6 rotation
	public	function check_rotation($node)
	{
		if ($node->parent != null)
		{
			// Zig rotation condition
			if ($node->parent->left != null && $node->parent->left == $node && $node->parent->parent == null)
			{
				$this->zig($node);
			}
			// Zag rotation condition
			else if ($node->parent->right != null && $node->parent->right == $node && $node->parent->parent == null)
			{
				$this->zag($node);
			}
			// Zig Zig rotation condition 
			else if ($node->parent->left != null && $node->parent->left == $node && $node->parent->parent->left != null && $node->parent->parent->left == $node->parent)
			{
				$this->zig_zig($node);
			}
			//Zag Zag rotation condition
			else if ($node->parent->right != null && $node->parent->right == $node && $node->parent->parent->right != null && $node->parent->parent->right == $node->parent)
			{
				$this->zag_zag($node);
			}
			//Zig Zag rotation condition
			else if ($node->parent->right != null && $node->parent->right == $node && $node->parent->parent != null && $node->parent->parent->left != null && $node->parent->parent->left == $node->parent)
			{
				$this->zig_zag($node);
			}
			//Zag Zig rotation condition
			else if ($node->parent->left != null && $node->parent->left == $node && $node->parent->parent != null && $node->parent->parent->right != null && $node->parent->parent->right == $node->parent)
			{
				$this->zag_zig($node);
			}
			else
			{
				return;
			}
			$this->check_rotation($node);
		}
	}
	//Create a new node and converting into splay tree
	public	function insert_node($data)
	{
		// Get new node of tree
		$new_node = new Node($data);
		$temp = null;
		if ($this->root == null)
		{
			// When splay tree empty then this is first node
			$this->root = $new_node;
		}
		else
		{
			$temp = $this->root;
			//Insert new node at proper position this is similar to BST
			while ($temp != null)
			{
				//Check whether inserted value is greater than tree current node data
				if ($data > $temp->data)
				{
					//if insert value are greater to current node value
					if ($temp->right == null)
					{
						//If current node Right child is null. 
						//insert new node to this position
						$temp->right = $new_node;
						$new_node->parent = $temp;
						$temp = null;
					}
					else
					{
						//Visit right child
						$temp = $temp->right;
					}
				}
				else
				{
					if ($temp->left == null)
					{
						// If current node left child is null. 
						// insert new node to this position
						$temp->left = $new_node;
						$new_node->parent = $temp;
						$temp = null;
					}
					else
					{
						//Visit left child
						$temp = $temp->left;
					}
				}
			}
			//make this newly node as root node of tree
			$this->check_rotation($new_node);
		}
		$this->root = $new_node;
	}
	public	function pre_order($temp)
	{
		if ($temp != null)
		{
			echo "  ". $temp->data;
			$this->pre_order($temp->left);
			$this->pre_order($temp->right);
		}
	}
	public	function in_order($temp)
	{
		if ($temp != null)
		{
			$this->in_order($temp->left);
			echo "  ". $temp->data;
			$this->in_order($temp->right);
		}
	}
	public	function post_order($temp)
	{
		if ($temp != null)
		{
			$this->post_order($temp->left);
			$this->post_order($temp->right);
			echo "  ". $temp->data;
		}
	}
	//This are handling the request to display tree elements
	public	function print_tree()
	{
		if ($this->root == null)
		{
			echo "\n Empty Tree \n";
		}
		else
		{
			echo "\nSplay Tree ";
			echo "\nPreorder  :";
			$this->pre_order($this->root);
			echo "\nInorder   :";
			$this->in_order($this->root);
			echo "\nPostorder :";
			$this->post_order($this->root);
		}
	}
}

function main()
{
	$obj = new SplayTree();
	//Add tree node
	$obj->insert_node(9);
	$obj->insert_node(3);
	$obj->insert_node(7);
	$obj->insert_node(13);
	$obj->insert_node(32);
	$obj->insert_node(1);
	$obj->insert_node(4);
	/*
			    Constructed Splay Tree
			    ----------------------

			      4
			    /    \
			   1      9
			    \    / \
			     3  7   32
			           /
			          13 
			*/
	$obj->print_tree();
}
main();

Output

Splay Tree
Preorder  :  4  1  3  9  7  32  13
Inorder   :  1  3  4  7  9  13  32
Postorder :  3  1  7  13  32  9  4
// Node Js program
// Splay Tree insertion

//Splay tree node
class Node
{
	constructor(data)
	{
		//Set node value of Splay-Tree
		this.data = data;
		this.left = null;
		this.right = null;
		this.parent = null;
	}
}
class SplayTree
{
	constructor()
	{
		this.root = null;
	}
	//Zig Rotation
	zig(node)
	{
		//Get the parent node 
		var parent = node.parent;
		// Change left subtree of parent node 
		// (This new subtree is right-subtree of given current node)
		parent.left = node.right;
		if (node.right != null)
		{
			//When add subtree not empty then change parent value
			node.right.parent = parent;
		}
		// Change parent node value
		node.right = parent;
		node.parent = parent.parent;
		parent.parent = node;
	}
	//zag rotation
	zag(node)
	{
		//Get the parent node 
		var parent = node.parent;
		parent.right = node.left;
		if (parent.right != null)
		{
			//When add subtree not empty then change parent value
			parent.right.parent = parent;
		}
		// change parent node value
		node.left = parent;
		node.parent = parent.parent;
		parent.parent = node;
	}
	//zig zig rotation
	zig_zig(node)
	{
		//Get the parent node 
		var parent = node.parent;
		var grand_parent = node.parent.parent;
		parent.left = node.right;
		if (node.right != null)
		{
			//When add subtree not empty then change parent value
			node.right.parent = parent;
		}
		node.right = parent;
		parent.parent = node;
		grand_parent.left = parent.right;
		if (parent.right != null)
		{
			parent.right.parent = grand_parent;
		}
		parent.right = grand_parent;
		node.parent = grand_parent.parent;
		if (grand_parent.parent != null)
		{
			if (grand_parent.parent.left != null && grand_parent.parent.left == grand_parent)
			{
				grand_parent.parent.left = node;
			}
			else
			{
				grand_parent.parent.right = node;
			}
		}
		grand_parent.parent = parent;
	}
	//zag_zag rotation
	zag_zag(node)
	{
		//Get the parent node 
		var parent = node.parent;
		var grand_parent = node.parent.parent;
		parent.right = node.left;
		if (node.left != null)
		{
			//When add subtree not empty then change parent value
			node.left.parent = parent;
		}
		node.left = parent;
		node.parent = grand_parent.parent;
		if (grand_parent.parent != null)
		{
			if (grand_parent.parent.left != null && grand_parent.parent.left == grand_parent)
			{
				grand_parent.parent.left = node;
			}
			else
			{
				grand_parent.parent.right = node;
			}
		}
		parent.parent = node;
		grand_parent.right = parent.left;
		if (parent.left != null)
		{
			parent.left.parent = grand_parent;
		}
		parent.left = grand_parent;
		grand_parent.parent = parent;
	}
	// Zag zig rotation
	zag_zig(node)
	{
		//Get the parent node 
		var parent = node.parent;
		var grand_parent = node.parent.parent;
		parent.left = node.right;
		if (node.right != null)
		{
			//When add subtree not empty then change parent value
			node.right.parent = parent;
		}
		grand_parent.right = node;
		node.parent = grand_parent;
		node.right = parent;
		parent.parent = node;
	}
	// Zig zag rotation
	zig_zag(node)
	{
		//Get the parent node 
		var parent = node.parent;
		var grand_parent = node.parent.parent;
		parent.right = node.left;
		if (node.left != null)
		{
			//When add subtree not empty then change parent value
			node.left.parent = parent;
		}
		grand_parent.left = node;
		node.parent = grand_parent;
		node.left = parent;
		parent.parent = node;
	}
	// Check of the which rotation are required to given node as a root of tree.
	// Perform basic 6 rotation
	check_rotation(node)
	{
		if (node.parent != null)
		{
			// Zig rotation condition
			if (node.parent.left != null && node.parent.left == node && node.parent.parent == null)
			{
				this.zig(node);
			}
			// Zag rotation condition
			else if (node.parent.right != null && node.parent.right == node && node.parent.parent == null)
			{
				this.zag(node);
			}
			// Zig Zig rotation condition 
			else if (node.parent.left != null && node.parent.left == node && node.parent.parent.left != null && node.parent.parent.left == node.parent)
			{
				this.zig_zig(node);
			}
			//Zag Zag rotation condition
			else if (node.parent.right != null && node.parent.right == node && node.parent.parent.right != null && node.parent.parent.right == node.parent)
			{
				this.zag_zag(node);
			}
			//Zig Zag rotation condition
			else if (node.parent.right != null && node.parent.right == node && node.parent.parent != null && node.parent.parent.left != null && node.parent.parent.left == node.parent)
			{
				this.zig_zag(node);
			}
			//Zag Zig rotation condition
			else if (node.parent.left != null && node.parent.left == node && node.parent.parent != null && node.parent.parent.right != null && node.parent.parent.right == node.parent)
			{
				this.zag_zig(node);
			}
			else
			{
				return;
			}
			this.check_rotation(node);
		}
	}
	//Create a new node and converting into splay tree
	insert_node(data)
	{
		// Get new node of tree
		var new_node = new Node(data);
		var temp = null;
		if (this.root == null)
		{
			// When splay tree empty then this is first node
			this.root = new_node;
		}
		else
		{
			temp = this.root;
			//Insert new node at proper position this is similar to BST
			while (temp != null)
			{
				//Check whether inserted value is greater than tree current node data
				if (data > temp.data)
				{
					//if insert value are greater to current node value
					if (temp.right == null)
					{
						//If current node Right child is null. 
						//insert new node to this position
						temp.right = new_node;
						new_node.parent = temp;
						temp = null;
					}
					else
					{
						//Visit right child
						temp = temp.right;
					}
				}
				else
				{
					if (temp.left == null)
					{
						// If current node left child is null. 
						// insert new node to this position
						temp.left = new_node;
						new_node.parent = temp;
						temp = null;
					}
					else
					{
						//Visit left child
						temp = temp.left;
					}
				}
			}
			//make this newly node as root node of tree
			this.check_rotation(new_node);
		}
		this.root = new_node;
	}
	pre_order(temp)
	{
		if (temp != null)
		{
			process.stdout.write("  " + temp.data);
			this.pre_order(temp.left);
			this.pre_order(temp.right);
		}
	}
	in_order(temp)
	{
		if (temp != null)
		{
			this.in_order(temp.left);
			process.stdout.write("  " + temp.data);
			this.in_order(temp.right);
		}
	}
	post_order(temp)
	{
		if (temp != null)
		{
			this.post_order(temp.left);
			this.post_order(temp.right);
			process.stdout.write("  " + temp.data);
		}
	}
	//This are handling the request to display tree elements
	print_tree()
	{
		if (this.root == null)
		{
			process.stdout.write("\n Empty Tree \n");
		}
		else
		{
			process.stdout.write("\nSplay Tree ");
			process.stdout.write("\nPreorder  :");
			this.pre_order(this.root);
			process.stdout.write("\nInorder   :");
			this.in_order(this.root);
			process.stdout.write("\nPostorder :");
			this.post_order(this.root);
		}
	}
}

function main()
{
	var obj = new SplayTree();
	//Add tree node
	obj.insert_node(9);
	obj.insert_node(3);
	obj.insert_node(7);
	obj.insert_node(13);
	obj.insert_node(32);
	obj.insert_node(1);
	obj.insert_node(4);
	/*
			    Constructed Splay Tree
			    ----------------------

			      4
			    /    \
			   1      9
			    \    / \
			     3  7   32
			           /
			          13 
			*/
	obj.print_tree();
}
main();

Output

Splay Tree
Preorder  :  4  1  3  9  7  32  13
Inorder   :  1  3  4  7  9  13  32
Postorder :  3  1  7  13  32  9  4
#  Python 3 program
#  Splay Tree insertion

# Splay tree node
class Node :
	
	def __init__(self, data) :
		# Set node value of Splay-Tree
		self.data = data
		self.left = None
		self.right = None
		self.parent = None
	

class SplayTree :
	
	def __init__(self) :
		self.root = None
	
	# Zig Rotation
	def zig(self, node) :
		# Get the parent node 
		parent = node.parent
		#  Change left subtree of parent node 
		#  (This new subtree is right-subtree of given current node)
		parent.left = node.right
		if (node.right != None) :
			# When add subtree not empty then change parent value
			node.right.parent = parent
		
		#  Change parent node value
		node.right = parent
		node.parent = parent.parent
		parent.parent = node
	
	# zag rotation
	def zag(self, node) :
		# Get the parent node 
		parent = node.parent
		parent.right = node.left
		if (parent.right != None) :
			# When add subtree not empty then change parent value
			parent.right.parent = parent
		
		#  change parent node value
		node.left = parent
		node.parent = parent.parent
		parent.parent = node
	
	# zig zig rotation
	def zig_zig(self, node) :
		# Get the parent node 
		parent = node.parent
		grand_parent = node.parent.parent
		parent.left = node.right
		if (node.right != None) :
			# When add subtree not empty then change parent value
			node.right.parent = parent
		
		node.right = parent
		parent.parent = node
		grand_parent.left = parent.right
		if (parent.right != None) :
			parent.right.parent = grand_parent
		
		parent.right = grand_parent
		node.parent = grand_parent.parent
		if (grand_parent.parent != None) :
			if (grand_parent.parent.left != None and grand_parent.parent.left == grand_parent) :
				grand_parent.parent.left = node
			else :
				grand_parent.parent.right = node
			
		
		grand_parent.parent = parent
	
	# zag_zag rotation
	def zag_zag(self, node) :
		# Get the parent node 
		parent = node.parent
		grand_parent = node.parent.parent
		parent.right = node.left
		if (node.left != None) :
			# When add subtree not empty then change parent value
			node.left.parent = parent
		
		node.left = parent
		node.parent = grand_parent.parent
		if (grand_parent.parent != None) :
			if (grand_parent.parent.left != None and grand_parent.parent.left == grand_parent) :
				grand_parent.parent.left = node
			else :
				grand_parent.parent.right = node
			
		
		parent.parent = node
		grand_parent.right = parent.left
		if (parent.left != None) :
			parent.left.parent = grand_parent
		
		parent.left = grand_parent
		grand_parent.parent = parent
	
	#  Zag zig rotation
	def zag_zig(self, node) :
		# Get the parent node 
		parent = node.parent
		grand_parent = node.parent.parent
		parent.left = node.right
		if (node.right != None) :
			# When add subtree not empty then change parent value
			node.right.parent = parent
		
		grand_parent.right = node
		node.parent = grand_parent
		node.right = parent
		parent.parent = node
	
	#  Zig zag rotation
	def zig_zag(self, node) :
		# Get the parent node 
		parent = node.parent
		grand_parent = node.parent.parent
		parent.right = node.left
		if (node.left != None) :
			# When add subtree not empty then change parent value
			node.left.parent = parent
		
		grand_parent.left = node
		node.parent = grand_parent
		node.left = parent
		parent.parent = node
	
	#  Check of the which rotation are required to given node as a root of tree.
	#  Perform basic 6 rotation
	def check_rotation(self, node) :
		if (node.parent != None) :
			#  Zig rotation condition
			if (node.parent.left != None and node.parent.left == node and node.parent.parent == None) :
				self.zig(node)
			
			#  Zag rotation condition
			elif(node.parent.right != None and node.parent.right == node and node.parent.parent == None) :
				self.zag(node)
			
			#  Zig Zig rotation condition 
			elif(node.parent.left != None and node.parent.left == node and node.parent.parent.left != None and node.parent.parent.left == node.parent) :
				self.zig_zig(node)
			
			# Zag Zag rotation condition
			elif(node.parent.right != None and node.parent.right == node and node.parent.parent.right != None and node.parent.parent.right == node.parent) :
				self.zag_zag(node)
			
			# Zig Zag rotation condition
			elif(node.parent.right != None and node.parent.right == node and node.parent.parent != None and node.parent.parent.left != None and node.parent.parent.left == node.parent) :
				self.zig_zag(node)
			
			# Zag Zig rotation condition
			elif(node.parent.left != None and node.parent.left == node and node.parent.parent != None and node.parent.parent.right != None and node.parent.parent.right == node.parent) :
				self.zag_zig(node)
			else :
				return
			
			self.check_rotation(node)
		
	
	# Create a new node and converting into splay tree
	def insert_node(self, data) :
		#  Get new node of tree
		new_node = Node(data)
		temp = None
		if (self.root == None) :
			#  When splay tree empty then this is first node
			self.root = new_node
		else :
			temp = self.root
			# Insert new node at proper position this is similar to BST
			while (temp != None) :
				# Check whether inserted value is greater than tree current node data
				if (data > temp.data) :
					# if insert value are greater to current node value
					if (temp.right == None) :
						# If current node Right child is null. 
						# insert new node to this position
						temp.right = new_node
						new_node.parent = temp
						temp = None
					else :
						# Visit right child
						temp = temp.right
					
				else :
					if (temp.left == None) :
						#  If current node left child is null. 
						#  insert new node to this position
						temp.left = new_node
						new_node.parent = temp
						temp = None
					else :
						# Visit left child
						temp = temp.left
					
				
			
			# make this newly node as root node of tree
			self.check_rotation(new_node)
		
		self.root = new_node
	
	def pre_order(self, temp) :
		if (temp != None) :
			print("  ", temp.data, end = "")
			self.pre_order(temp.left)
			self.pre_order(temp.right)
		
	
	def in_order(self, temp) :
		if (temp != None) :
			self.in_order(temp.left)
			print("  ", temp.data, end = "")
			self.in_order(temp.right)
		
	
	def post_order(self, temp) :
		if (temp != None) :
			self.post_order(temp.left)
			self.post_order(temp.right)
			print("  ", temp.data, end = "")
		
	
	# This are handling the request to display tree elements
	def print_tree(self) :
		if (self.root == None) :
			print("\n Empty Tree \n", end = "")
		else :
			print("\nSplay Tree ", end = "")
			print("\nPreorder  :", end = "")
			self.pre_order(self.root)
			print("\nInorder   :", end = "")
			self.in_order(self.root)
			print("\nPostorder :", end = "")
			self.post_order(self.root)
		
	

def main() :
	obj = SplayTree()
	# Add tree node
	obj.insert_node(9)
	obj.insert_node(3)
	obj.insert_node(7)
	obj.insert_node(13)
	obj.insert_node(32)
	obj.insert_node(1)
	obj.insert_node(4)
	# 
	# 		    Constructed Splay Tree
	# 		    ----------------------
	# 		      4
	# 		    /    \
	# 		   1      9
	# 		    \    / \
	# 		     3  7   32
	# 		           /
	# 		          13 
	# 		
	
	obj.print_tree()

if __name__ == "__main__": main()

Output

Splay Tree
Preorder  :   4   1   3   9   7   32   13
Inorder   :   1   3   4   7   9   13   32
Postorder :   3   1   7   13   32   9   4
#  Ruby program
#  Splay Tree insertion

# Splay tree node
class Node 

	# Define the accessor and reader of class Node  
	attr_reader :data, :left, :right, :parent
	attr_accessor :data, :left, :right, :parent
    
	def initialize(data)
	
		# Set node value of Splay-Tree
		self.data = data
		self.left = nil
		self.right = nil
		self.parent = nil
	end
end
class SplayTree 

	# Define the accessor and reader of class SplayTree  
	attr_reader :root
	attr_accessor :root

	def initialize()
		self.root = nil
	end
	# Zig Rotation
	def zig(node)
	
		# Get the parent node 
		parent = node.parent
		#  Change left subtree of parent node 
		#  (This new subtree is right-subtree of given current node)
		parent.left = node.right
		if (node.right != nil)
			# When add subtree not empty then change parent value
			node.right.parent = parent
		end
		#  Change parent node value
		node.right = parent
		node.parent = parent.parent
		parent.parent = node
	end
	# zag rotation
	def zag(node)
	
		# Get the parent node 
		parent = node.parent
		parent.right = node.left
		if (parent.right != nil)
			# When add subtree not empty then change parent value
			parent.right.parent = parent
		end
		#  change parent node value
		node.left = parent
		node.parent = parent.parent
		parent.parent = node
	end
	# zig zig rotation
	def zig_zig(node)
	
		# Get the parent node 
		parent = node.parent
		grand_parent = node.parent.parent
		parent.left = node.right
		if (node.right != nil)
			# When add subtree not empty then change parent value
			node.right.parent = parent
		end
		node.right = parent
		parent.parent = node
		grand_parent.left = parent.right
		if (parent.right != nil)
			parent.right.parent = grand_parent
		end
		parent.right = grand_parent
		node.parent = grand_parent.parent
		if (grand_parent.parent != nil)
		
			if (grand_parent.parent.left != nil && grand_parent.parent.left == grand_parent)
			
				grand_parent.parent.left = node
			else
			
				grand_parent.parent.right = node
			end
		end
		grand_parent.parent = parent
	end
	# zag_zag rotation
	def zag_zag(node)
	
		# Get the parent node 
		parent = node.parent
		grand_parent = node.parent.parent
		parent.right = node.left
		if (node.left != nil)
		
			# When add subtree not empty then change parent value
			node.left.parent = parent
		end
		node.left = parent
		node.parent = grand_parent.parent
		if (grand_parent.parent != nil)
		
			if (grand_parent.parent.left != nil && grand_parent.parent.left == grand_parent)
			
				grand_parent.parent.left = node
			else
			
				grand_parent.parent.right = node
			end
		end
		parent.parent = node
		grand_parent.right = parent.left
		if (parent.left != nil)
		
			parent.left.parent = grand_parent
		end
		parent.left = grand_parent
		grand_parent.parent = parent
	end
	#  Zag zig rotation
	def zag_zig(node)
	
		# Get the parent node 
		parent = node.parent
		grand_parent = node.parent.parent
		parent.left = node.right
		if (node.right != nil)
		
			# When add subtree not empty then change parent value
			node.right.parent = parent
		end
		grand_parent.right = node
		node.parent = grand_parent
		node.right = parent
		parent.parent = node
	end
	#  Zig zag rotation
	def zig_zag(node)
	
		# Get the parent node 
		parent = node.parent
		grand_parent = node.parent.parent
		parent.right = node.left
		if (node.left != nil)
		
			# When add subtree not empty then change parent value
			node.left.parent = parent
		end
		grand_parent.left = node
		node.parent = grand_parent
		node.left = parent
		parent.parent = node
	end
	#  Check of the which rotation are required to given node as a root of tree.
	#  Perform basic 6 rotation
	def check_rotation(node)
	
		if (node.parent != nil)
		
			#  Zig rotation condition
			if (node.parent.left != nil && node.parent.left == node && node.parent.parent == nil)
				self.zig(node)

			#  Zag rotation condition
			elsif(node.parent.right != nil && node.parent.right == node && node.parent.parent == nil)
				self.zag(node)
			#  Zig Zig rotation condition 
			elsif(node.parent.left != nil && node.parent.left == node && node.parent.parent.left != nil && node.parent.parent.left == node.parent)
			
				self.zig_zig(node)
			# Zag Zag rotation condition
			elsif(node.parent.right != nil && node.parent.right == node && node.parent.parent.right != nil && node.parent.parent.right == node.parent)
				self.zag_zag(node)
			# Zig Zag rotation condition
			elsif(node.parent.right != nil && node.parent.right == node && node.parent.parent != nil && node.parent.parent.left != nil && node.parent.parent.left == node.parent)
			
				self.zig_zag(node)
			# Zag Zig rotation condition
			elsif(node.parent.left != nil && node.parent.left == node && node.parent.parent != nil && node.parent.parent.right != nil && node.parent.parent.right == node.parent)
			
				self.zag_zig(node)
			else
			
				return
			end
			self.check_rotation(node)
		end
	end
	# Create a new node and converting into splay tree
	def insert_node(data)
	
		#  Get new node of tree
		new_node = Node.new(data)
		temp = nil
		if (self.root == nil)
		
			#  When splay tree empty then this is first node
			self.root = new_node
		else
		
			temp = @root
			# Insert new node at proper position this is similar to BST
			while (temp != nil)
			
				# Check whether inserted value is greater than tree current node data
				if (data > temp.data)
				
					# if insert value are greater to current node value
					if (temp.right == nil)
					
						# If current node Right child is null. 
						# insert new node to this position
						temp.right = new_node
						new_node.parent = temp
						temp = nil
					else
					
						# Visit right child
						temp = temp.right
					end
				else
				
					if (temp.left == nil)
					
						#  If current node left child is null. 
						#  insert new node to this position
						temp.left = new_node
						new_node.parent = temp
						temp = nil
					else
					
						# Visit left child
						temp = temp.left
					end
				end
			end
			# make this newly node as root node of tree
			self.check_rotation(new_node)
		end
		self.root = new_node
	end
	def pre_order(temp)
	
		if (temp != nil)
		
			print("  ", temp.data)
			self.pre_order(temp.left)
			self.pre_order(temp.right)
		end
	end
	def in_order(temp)
	
		if (temp != nil)
		
			self.in_order(temp.left)
			print("  ", temp.data)
			self.in_order(temp.right)
		end
	end
	def post_order(temp)
	
		if (temp != nil)
		
			self.post_order(temp.left)
			self.post_order(temp.right)
			print("  ", temp.data)
		end
	end
	# This are handling the request to display tree elements
	def print_tree()
	
		if (self.root == nil)
		
			print("\n Empty Tree \n")
		else
		
			print("\nSplay Tree ")
			print("\nPreorder  :")
			self.pre_order(self.root)
			print("\nInorder   :")
			self.in_order(self.root)
			print("\nPostorder :")
			self.post_order(self.root)
		end
	end
end
def main()

	obj = SplayTree.new()
	# Add tree node
	obj.insert_node(9)
	obj.insert_node(3)
	obj.insert_node(7)
	obj.insert_node(13)
	obj.insert_node(32)
	obj.insert_node(1)
	obj.insert_node(4)
	# 
	# 		    Constructed Splay Tree
	# 		    ----------------------
	# 		      4
	# 		    /    \
	# 		   1      9
	# 		    \    / \
	# 		     3  7   32
	# 		           /
	# 		          13 
	# 		
	
	obj.print_tree()
end
main()

Output

Splay Tree 
Preorder  :  4  1  3  9  7  32  13
Inorder   :  1  3  4  7  9  13  32
Postorder :  3  1  7  13  32  9  4
// Scala program
// Splay Tree insertion

//Splay tree node
class Node(var data: Int,
	var left: Node,
		var right: Node,
			var parent: Node)
{
	def this(data: Int)
	{
		this(data, null, null, null);
	}
}
class SplayTree(var root: Node)
{
	def this()
	{
		this(null);
	}
	//Zig Rotation
	def zig(node: Node): Unit = {
		//Get the parent node 
		var parent: Node = node.parent;
		// Change left subtree of parent node 
		// (This new subtree is right-subtree of given current node)
		parent.left = node.right;
		if (node.right != null)
		{
			//When add subtree not empty then change parent value
			node.right.parent = parent;
		}
		// Change parent node value
		node.right = parent;
		node.parent = parent.parent;
		parent.parent = node;
	}
	//zag rotation
	def zag(node: Node): Unit = {
		//Get the parent node 
		var parent: Node = node.parent;
		parent.right = node.left;
		if (parent.right != null)
		{
			//When add subtree not empty then change parent value
			parent.right.parent = parent;
		}
		// change parent node value
		node.left = parent;
		node.parent = parent.parent;
		parent.parent = node;
	}
	//zig zig rotation
	def zig_zig(node: Node): Unit = {
		//Get the parent node 
		var parent: Node = node.parent;
		var grand_parent: Node = node.parent.parent;
		parent.left = node.right;
		if (node.right != null)
		{
			//When add subtree not empty then change parent value
			node.right.parent = parent;
		}
		node.right = parent;
		parent.parent = node;
		grand_parent.left = parent.right;
		if (parent.right != null)
		{
			parent.right.parent = grand_parent;
		}
		parent.right = grand_parent;
		node.parent = grand_parent.parent;
		if (grand_parent.parent != null)
		{
			if (grand_parent.parent.left != null && grand_parent.parent.left == grand_parent)
			{
				grand_parent.parent.left = node;
			}
			else
			{
				grand_parent.parent.right = node;
			}
		}
		grand_parent.parent = parent;
	}
	//zag_zag rotation
	def zag_zag(node: Node): Unit = {
		//Get the parent node 
		var parent: Node = node.parent;
		var grand_parent: Node = node.parent.parent;
		parent.right = node.left;
		if (node.left != null)
		{
			//When add subtree not empty then change parent value
			node.left.parent = parent;
		}
		node.left = parent;
		node.parent = grand_parent.parent;
		if (grand_parent.parent != null)
		{
			if (grand_parent.parent.left != null && grand_parent.parent.left == grand_parent)
			{
				grand_parent.parent.left = node;
			}
			else
			{
				grand_parent.parent.right = node;
			}
		}
		parent.parent = node;
		grand_parent.right = parent.left;
		if (parent.left != null)
		{
			parent.left.parent = grand_parent;
		}
		parent.left = grand_parent;
		grand_parent.parent = parent;
	}
	// Zag zig rotation
	def zag_zig(node: Node): Unit = {
		//Get the parent node 
		var parent: Node = node.parent;
		var grand_parent: Node = node.parent.parent;
		parent.left = node.right;
		if (node.right != null)
		{
			//When add subtree not empty then change parent value
			node.right.parent = parent;
		}
		grand_parent.right = node;
		node.parent = grand_parent;
		node.right = parent;
		parent.parent = node;
	}
	// Zig zag rotation
	def zig_zag(node: Node): Unit = {
		//Get the parent node 
		var parent: Node = node.parent;
		var grand_parent: Node = node.parent.parent;
		parent.right = node.left;
		if (node.left != null)
		{
			//When add subtree not empty then change parent value
			node.left.parent = parent;
		}
		grand_parent.left = node;
		node.parent = grand_parent;
		node.left = parent;
		parent.parent = node;
	}
	// Check of the which rotation are required to given node as a root of tree.
	// Perform basic 6 rotation
	def check_rotation(node: Node): Unit = {
		if (node.parent != null)
		{
			// Zig rotation condition
			if (node.parent.left != null && node.parent.left == node && node.parent.parent == null)
			{
				zig(node);
			}
			// Zag rotation condition
			else if (node.parent.right != null && node.parent.right == node && node.parent.parent == null)
			{
				zag(node);
			}
			// Zig Zig rotation condition 
			else if (node.parent.left != null && node.parent.left == node && node.parent.parent.left != null && node.parent.parent.left == node.parent)
			{
				zig_zig(node);
			}
			//Zag Zag rotation condition
			else if (node.parent.right != null && node.parent.right == node && node.parent.parent.right != null && node.parent.parent.right == node.parent)
			{
				zag_zag(node);
			}
			//Zig Zag rotation condition
			else if (node.parent.right != null && node.parent.right == node && node.parent.parent != null && node.parent.parent.left != null && node.parent.parent.left == node.parent)
			{
				zig_zag(node);
			}
			//Zag Zig rotation condition
			else if (node.parent.left != null && node.parent.left == node && node.parent.parent != null && node.parent.parent.right != null && node.parent.parent.right == node.parent)
			{
				zag_zig(node);
			}
			else
			{
				return;
			}
			check_rotation(node);
		}
	}
	//Create a new node and converting into splay tree
	def insert_node(data: Int): Unit = {
		// Get new node of tree
		var new_node: Node = new Node(data);
		var temp: Node = null;
		if (this.root == null)
		{
			// When splay tree empty then this is first node
			this.root = new_node;
		}
		else
		{
			temp = root;
			//Insert new node at proper position this is similar to BST
			while (temp != null)
			{
				//Check whether inserted value is greater than tree current node data
				if (data > temp.data)
				{
					//if insert value are greater to current node value
					if (temp.right == null)
					{
						//If current node Right child is null. 
						//insert new node to this position
						temp.right = new_node;
						new_node.parent = temp;
						temp = null;
					}
					else
					{
						//Visit right child
						temp = temp.right;
					}
				}
				else
				{
					if (temp.left == null)
					{
						// If current node left child is null. 
						// insert new node to this position
						temp.left = new_node;
						new_node.parent = temp;
						temp = null;
					}
					else
					{
						//Visit left child
						temp = temp.left;
					}
				}
			}
			//make this newly node as root node of tree
			check_rotation(new_node);
		}
		this.root = new_node;
	}
	def pre_order(temp: Node): Unit = {
		if (temp != null)
		{
			print("  " + temp.data);
			pre_order(temp.left);
			pre_order(temp.right);
		}
	}
	def in_order(temp: Node): Unit = {
		if (temp != null)
		{
			in_order(temp.left);
			print("  " + temp.data);
			in_order(temp.right);
		}
	}
	def post_order(temp: Node): Unit = {
		if (temp != null)
		{
			post_order(temp.left);
			post_order(temp.right);
			print("  " + temp.data);
		}
	}
	//This are handling the request to display tree elements
	def print_tree(): Unit = {
		if (this.root == null)
		{
			print("\n Empty Tree \n");
		}
		else
		{
			print("\nSplay Tree ");
			print("\nPreorder  :");
			pre_order(this.root);
			print("\nInorder   :");
			in_order(this.root);
			print("\nPostorder :");
			post_order(this.root);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: SplayTree = new SplayTree();
		//Add tree node
		obj.insert_node(9);
		obj.insert_node(3);
		obj.insert_node(7);
		obj.insert_node(13);
		obj.insert_node(32);
		obj.insert_node(1);
		obj.insert_node(4);
		/*
				    Constructed Splay Tree
				    ----------------------

				      4
				    /    \
				   1      9
				    \    / \
				     3  7   32
				           /
				          13 
				*/
		obj.print_tree();
	}
}

Output

Splay Tree
Preorder  :  4  1  3  9  7  32  13
Inorder   :  1  3  4  7  9  13  32
Postorder :  3  1  7  13  32  9  4
// Swift program
// Splay Tree insertion
//Splay tree node
class Node
{
	var data: Int;
	var left: Node? ;
	var right: Node? ;
	var parent: Node? ;
	init(_ data: Int)
	{
		//Set node value of Splay-Tree
		self.data = data;
		self.left = nil;
		self.right = nil;
		self.parent = nil;
	}
}
class SplayTree
{
	var root: Node? ;
	init()
	{
		self.root = nil;
	}
	//Zig Rotation
	func zig(_ node: Node? )
	{
		//Get the parent node 
		let parent: Node? = node!.parent;
		// Change left subtree of parent node 
		// (This new subtree is right-subtree of given current node)
		parent!.left = node!.right;
		if (node!.right != nil)
		{
			//When add subtree not empty then change parent value
			node!.right!.parent = parent;
		}
		// Change parent node value
		node!.right = parent;
		node!.parent = parent!.parent;
		parent!.parent = node;
	}
	//zag rotation
	func zag(_ node: Node? )
	{
		//Get the parent node 
		let parent: Node? = node!.parent;
		parent!.right = node!.left;
		if (parent!.right != nil)
		{
			//When add subtree not empty then change parent value
			parent!.right!.parent = parent;
		}
		// change parent node value
		node!.left = parent;
		node!.parent = parent!.parent;
		parent!.parent = node;
	}
	//zig zig rotation
	func zig_zig(_ node: Node? )
	{
		//Get the parent node 
		let parent: Node? = node!.parent;
		let grand_parent: Node? = node!.parent!.parent;
		parent!.left = node!.right;
		if (node!.right != nil)
		{
			//When add subtree not empty then change parent value
			node!.right!.parent = parent;
		}
		node!.right = parent;
		parent!.parent = node;
		grand_parent!.left = parent!.right;
		if (parent!.right != nil)
		{
			parent!.right!.parent = grand_parent;
		}
		parent!.right = grand_parent;
		node!.parent = grand_parent!.parent;
		if (grand_parent!.parent != nil)
		{
			if (grand_parent!.parent!.left != nil && grand_parent!.parent!.left === grand_parent)
			{
				grand_parent!.parent!.left = node;
			}
			else
			{
				grand_parent!.parent!.right = node;
			}
		}
		grand_parent!.parent = parent;
	}
	//zag_zag rotation
	func zag_zag(_ node: Node? )
	{
		//Get the parent node 
		let parent: Node? = node!.parent;
		let grand_parent: Node? = node!.parent!.parent;
		parent!.right = node!.left;
		if (node!.left != nil)
		{
			//When add subtree not empty then change parent value
			node!.left!.parent = parent;
		}
		node!.left = parent;
		node!.parent = grand_parent!.parent;
		if (grand_parent!.parent != nil)
		{
			if (grand_parent!.parent!.left != nil && grand_parent!.parent!.left === grand_parent)
			{
				grand_parent!.parent!.left = node;
			}
			else
			{
				grand_parent!.parent!.right = node;
			}
		}
		parent!.parent = node;
		grand_parent!.right = parent!.left;
		if (parent!.left != nil)
		{
			parent!.left!.parent = grand_parent;
		}
		parent!.left = grand_parent;
		grand_parent!.parent = parent;
	}
	// Zag zig rotation
	func zag_zig(_ node: Node? )
	{
		//Get the parent node 
		let parent: Node? = node!.parent;
		let grand_parent: Node? = node!.parent!.parent;
		parent!.left = node!.right;
		if (node!.right != nil)
		{
			//When add subtree not empty then change parent value
			node!.right!.parent = parent;
		}
		grand_parent!.right = node;
		node!.parent = grand_parent;
		node!.right = parent;
		parent!.parent = node;
	}
	// Zig zag rotation
	func zig_zag(_ node: Node? )
	{
		//Get the parent node 
		let parent: Node? = node!.parent;
		let grand_parent: Node? = node!.parent!.parent;
		parent!.right = node!.left;
		if (node!.left != nil)
		{
			//When add subtree not empty then change parent value
			node!.left!.parent = parent;
		}
		grand_parent!.left = node;
		node!.parent = grand_parent;
		node!.left = parent;
		parent!.parent = node;
	}
	// Check of the which rotation are required to given node as a root of tree.
	// Perform basic 6 rotation
	func check_rotation(_ node: Node? )
	{
		if (node!.parent != nil)
		{
			// Zig rotation condition
			if (node!.parent!.left != nil && node!.parent!.left === node && node!.parent!.parent == nil)
			{
				self.zig(node);
			}
			// Zag rotation condition
			else if (node!.parent!.right != nil && node!.parent!.right === node && node!.parent!.parent == nil)
			{
				self.zag(node);
			}
			// Zig Zig rotation condition 
			else if (node!.parent!.left != nil && node!.parent!.left === node && node!.parent!.parent!.left != nil && node!.parent!.parent!.left === node!.parent)
			{
				self.zig_zig(node);
			}
			//Zag Zag rotation condition
			else if (node!.parent!.right != nil && node!.parent!.right === node && node!.parent!.parent!.right != nil && node!.parent!.parent!.right === node!.parent)
			{
				self.zag_zag(node);
			}
			//Zig Zag rotation condition
			else if (node!.parent!.right != nil && node!.parent!.right === node && node!.parent!.parent != nil && node!.parent!.parent!.left != nil && node!.parent!.parent!.left === node!.parent)
			{
				self.zig_zag(node);
			}
			//Zag Zig rotation condition
			else if (node!.parent!.left != nil && node!.parent!.left === node && node!.parent!.parent != nil && node!.parent!.parent!.right != nil && node!.parent!.parent!.right === node!.parent)
			{
				self.zag_zig(node);
			}
			else
			{
				return;
			}
			self.check_rotation(node);
		}
	}
	//Create a new node and converting into splay tree
	func insert_node(_ data: Int)
	{
		// Get new node of tree
		let new_node: Node? = Node(data);
		var temp: Node? = nil;
		if (self.root == nil)
		{
			// When splay tree empty then this is first node
			self.root = new_node;
		}
		else
		{
			temp = self.root;
			//Insert new node at proper position this is similar to BST
			while (temp != nil)
			{
				//Check whether inserted value is greater than tree current node data
				if (data > temp!.data)
				{
					//if insert value are greater to current node value
					if (temp!.right == nil)
					{
						//If current node Right child is null. 
						//insert new node to this position
						temp!.right = new_node;
						new_node!.parent = temp;
						temp = nil;
					}
					else
					{
						//Visit right child
						temp = temp!.right;
					}
				}
				else
				{
					if (temp!.left == nil)
					{
						// If current node left child is null. 
						// insert new node to this position
						temp!.left = new_node;
						new_node!.parent = temp;
						temp = nil;
					}
					else
					{
						//Visit left child
						temp = temp!.left;
					}
				}
			}
			//make this newly node as root node of tree
			self.check_rotation(new_node);
		}
		self.root = new_node;
	}
	func pre_order(_ temp: Node? )
	{
		if (temp != nil)
		{
			print("  ", temp!.data, terminator: "");
			self.pre_order(temp!.left);
			self.pre_order(temp!.right);
		}
	}
	func in_order(_ temp: Node? )
	{
		if (temp != nil)
		{
			self.in_order(temp!.left);
			print("  ", temp!.data, terminator: "");
			self.in_order(temp!.right);
		}
	}
	func post_order(_ temp: Node? )
	{
		if (temp != nil)
		{
			self.post_order(temp!.left);
			self.post_order(temp!.right);
			print("  ", temp!.data, terminator: "");
		}
	}
	//This are handling the request to display tree elements
	func print_tree()
	{
		if (self.root == nil)
		{
			print("\n Empty Tree \n", terminator: "");
		}
		else
		{
			print("\nSplay Tree ", terminator: "");
			print("\nPreorder  :", terminator: "");
			self.pre_order(self.root);
			print("\nInorder   :", terminator: "");
			self.in_order(self.root);
			print("\nPostorder :", terminator: "");
			self.post_order(self.root);
		}
	}
}
func main()
{
	let obj: SplayTree = SplayTree();
	//Add tree node
	obj.insert_node(9);
	obj.insert_node(3);
	obj.insert_node(7);
	obj.insert_node(13);
	obj.insert_node(32);
	obj.insert_node(1);
	obj.insert_node(4);
	/*
			    Constructed Splay Tree
			    ----------------------

			      4
			    /    \
			   1      9
			    \    / \
			     3  7   32
			           /
			          13 
			*/
	obj.print_tree();
}
main();

Output

Splay Tree
Preorder  :   4   1   3   9   7   32   13
Inorder   :   1   3   4   7   9   13   32
Postorder :   3   1   7   13   32   9   4


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







© 2021, kalkicode.com, All rights reserved