Splay tree deletion

Here given code implementation process.

// C Program
// Splay tree node deletion
#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 make_root(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;
		}
		make_root(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
			make_root(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);
	}
}
//Delete a node in splay tree
void delete_node(struct Node **root, int value)
{
	if ( *root != NULL)
	{
		struct Node *node = *root;
		struct Node *right_side = NULL;
		struct Node *left_side = NULL;
		//First find deleted node in Splay tree
		while (node != NULL && node->data != value)
		{
			if (value > node->data)
			{
				node = node->right;
			}
			else
			{
				node = node->left;
			}
		}
		if (node != NULL)
		{
			printf("\n Before delete node [%d] :", value);
			print_tree( *root);
			//When deleted node are exist
			//Make root of this delete node 
			make_root(node);*root = node;
			if (node->left == NULL)
			{
				//When no left side subtree of root node
				*root = node->right;
			}
			else if (node->right == NULL)
			{
				//When no right side subtree of root node
				*root = node->left;
			}
			else
			{
				if (node->left != NULL)
				{
					node->left->parent = NULL;
				}
				if (node->right != NULL)
				{
					node->right->parent = NULL;
				}
				right_side = node->right;
				left_side = node->left;*root = NULL;
				node->right = NULL;
				node->left = NULL;
				free(node);
				node = left_side;
				//Find inorder predecessor
				while (node->right)
				{
					node = node->right;
				}
				make_root(node);
				node->right = right_side;
				right_side->parent = node;*root = node;
			}
			printf("\n After delete node [%d] :", value);
			print_tree( *root);
		}
		else
		{
			printf("\n\nDelete node %d are not exist\n", value);
		}
		if ( *root != NULL)
		{
			( *root)->parent = NULL;
		}
	}
}
/*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, 20);
	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   20
	         /  \
	        13   32
	*/
	//Test case
	delete_node( &root, 3);
	/*
	//After delete 3

	     1  
	      \  
	       4
	        \ 
	         9
	        / \
	       7   20
	          /  \
	         13   32
	*/
	delete_node( &root, 9);
	/*
	//After delete 9

	         7
	        / \
	       4   20
	      /   /  \
	     1   13   32
	*/
	delete_node( &root, 20);
	/*
	//After delete 20

	           13  
	          /  \ 
	         7    32
	        / 
	       4   
	      /     
	     1      
	*/
	delete_node( &root, 5);
	return 0;
}

Output

 Before delete node [3] :
Splay Tree
Preorder  :  4  1  3  9  7  20  13  32
Inorder   :  1  3  4  7  9  13  20  32
Postorder :  3  1  7  13  32  20  9  4
 After delete node [3] :
Splay Tree
Preorder  :  1  4  9  7  20  13  32
Inorder   :  1  4  7  9  13  20  32
Postorder :  7  13  32  20  9  4  1
 Before delete node [9] :
Splay Tree
Preorder  :  1  4  9  7  20  13  32
Inorder   :  1  4  7  9  13  20  32
Postorder :  7  13  32  20  9  4  1
 After delete node [9] :
Splay Tree
Preorder  :  7  4  1  20  13  32
Inorder   :  1  4  7  13  20  32
Postorder :  1  4  13  32  20  7
 Before delete node [20] :
Splay Tree
Preorder  :  7  4  1  20  13  32
Inorder   :  1  4  7  13  20  32
Postorder :  1  4  13  32  20  7
 After delete node [20] :
Splay Tree
Preorder  :  13  7  4  1  32
Inorder   :  1  4  7  13  32
Postorder :  1  4  7  32  13

Delete node 5 are not exist
// Java program
// Splay tree node deletion

//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 make_root(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;
			}
			make_root(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
			make_root(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);
		}
	}
	//Delete a node in splay tree
	public void delete_node(int value)
	{
		if (this.root != null)
		{
			Node node = this.root;
			Node right_side = null;
			Node left_side = null;
			//First find deleted node in Splay tree
			while (node != null && node.data != value)
			{
				if (value > node.data)
				{
					node = node.right;
				}
				else
				{
					node = node.left;
				}
			}
			if (node != null)
			{
				//When deleted node are exist
				System.out.print("\n Before delete node [" + value + "] :");
				print_tree();
				//Make root of this delete node 
				make_root(node);
				this.root = node;
				if (node.left == null)
				{
					//When no left side subtree of root node
					this.root = node.right;
				}
				else if (node.right == null)
				{
					//When no right side subtree of root node
					this.root = node.left;
				}
				else
				{
					if (node.left != null)
					{
						node.left.parent = null;
					}
					if (node.right != null)
					{
						node.right.parent = null;
					}
					right_side = node.right;
					left_side = node.left;
					this.root = null;
					//remove node
					node.right = null;
					node.left = null;
					node = left_side;
					//Find inorder predecessor
					while (node.right != null)
					{
						node = node.right;
					}
					make_root(node);
					node.right = right_side;
					right_side.parent = node;
					this.root = node;
				}
				System.out.print("\n After delete node [" + value + "] :");
				print_tree();
			}
			else
			{
				System.out.print("\n\nDelete node " + value + " are not exist\n");
			}
			if (this.root != null)
			{
				this.root.parent = null;
			}
		}
	}
	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(20);
		obj.insert_node(13);
		obj.insert_node(32);
		obj.insert_node(1);
		obj.insert_node(4);
		/*
		  Constructed Splay Tree
		  ----------------------

		    4
		  /    \
		 1      9
		  \    / \
		   3  7   20
		         /  \
		        13   32
		*/
		//Test case
		obj.delete_node(3);
		/*
		//After delete 3

		     1  
		      \  
		       4
		        \ 
		         9
		        / \
		       7   20
		          /  \
		         13   32
		*/
		obj.delete_node(9);
		/*
		//After delete 9

		         7
		        / \
		       4   20
		      /   /  \
		     1   13   32
		*/
		obj.delete_node(20);
		/*
		//After delete 20

		           13  
		          /  \ 
		         7    32
		        / 
		       4   
		      /     
		     1      
		*/
		obj.delete_node(5);
	}
}

Output

 Before delete node [3] :
Splay Tree
Preorder  :  4  1  3  9  7  20  13  32
Inorder   :  1  3  4  7  9  13  20  32
Postorder :  3  1  7  13  32  20  9  4
 After delete node [3] :
Splay Tree
Preorder  :  1  4  9  7  20  13  32
Inorder   :  1  4  7  9  13  20  32
Postorder :  7  13  32  20  9  4  1
 Before delete node [9] :
Splay Tree
Preorder  :  1  4  9  7  20  13  32
Inorder   :  1  4  7  9  13  20  32
Postorder :  7  13  32  20  9  4  1
 After delete node [9] :
Splay Tree
Preorder  :  7  4  1  20  13  32
Inorder   :  1  4  7  13  20  32
Postorder :  1  4  13  32  20  7
 Before delete node [20] :
Splay Tree
Preorder  :  7  4  1  20  13  32
Inorder   :  1  4  7  13  20  32
Postorder :  1  4  13  32  20  7
 After delete node [20] :
Splay Tree
Preorder  :  13  7  4  1  32
Inorder   :  1  4  7  13  32
Postorder :  1  4  7  32  13

Delete node 5 are not exist
//Include header file
#include <iostream>
using namespace std;

// C++ program
// Splay tree node deletion

//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 make_root(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->make_root(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->make_root(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);
		}
	}
	//Delete a node in splay tree
	void delete_node(int value)
	{
		if (this->root != NULL)
		{
			Node * node = this->root;
			Node * right_side = NULL;
			Node * left_side = NULL;
			//First find deleted node in Splay tree
			while (node != NULL && node->data != value)
			{
				if (value > node->data)
				{
					node = node->right;
				}
				else
				{
					node = node->left;
				}
			}
			if (node != NULL)
			{
				//When deleted node are exist
				cout << "\n Before delete node [" << value << "] :";
				this->print_tree();
				//Make root of this delete node 
				this->make_root(node);
				this->root = node;
				if (node->left == NULL)
				{
					//When no left side subtree of root node
					this->root = node->right;
				}
				else if (node->right == NULL)
				{
					//When no right side subtree of root node
					this->root = node->left;
				}
				else
				{
					if (node->left != NULL)
					{
						node->left->parent = NULL;
					}
					if (node->right != NULL)
					{
						node->right->parent = NULL;
					}
					right_side = node->right;
					left_side = node->left;
					this->root = NULL;
					//remove node
					node->right = NULL;
					node->left = NULL;
					node = left_side;
					//Find inorder predecessor
					while (node->right != NULL)
					{
						node = node->right;
					}
					this->make_root(node);
					node->right = right_side;
					right_side->parent = node;
					this->root = node;
				}
				cout << "\n After delete node [" << value << "] :";
				this->print_tree();
			}
			else
			{
				cout << "\n\nDelete node " << value << " are not exist\n";
			}
			if (this->root != NULL)
			{
				this->root->parent = NULL;
			}
		}
	}
};
int main()
{
	SplayTree obj = SplayTree();
	//Add tree node
	obj.insert_node(9);
	obj.insert_node(3);
	obj.insert_node(7);
	obj.insert_node(20);
	obj.insert_node(13);
	obj.insert_node(32);
	obj.insert_node(1);
	obj.insert_node(4);
	/*
			  Constructed Splay Tree
			  ----------------------

			    4
			  /    \
			 1      9
			  \    / \
			   3  7   20
			         /  \
			        13   32
			*/
	//Test case
	obj.delete_node(3);
	/*
			//After delete 3

			     1  
			      \  
			       4
			        \ 
			         9
			        / \
			       7   20
			          /  \
			         13   32
			*/
	obj.delete_node(9);
	/*
			//After delete 9

			         7
			        / \
			       4   20
			      /   /  \
			     1   13   32
			*/
	obj.delete_node(20);
	/*
			//After delete 20

			           13  
			          /  \ 
			         7    32
			        / 
			       4   
			      /     
			     1      
			*/
	obj.delete_node(5);
	return 0;
}

Output

 Before delete node [3] :
Splay Tree
Preorder  :  4  1  3  9  7  20  13  32
Inorder   :  1  3  4  7  9  13  20  32
Postorder :  3  1  7  13  32  20  9  4
 After delete node [3] :
Splay Tree
Preorder  :  1  4  9  7  20  13  32
Inorder   :  1  4  7  9  13  20  32
Postorder :  7  13  32  20  9  4  1
 Before delete node [9] :
Splay Tree
Preorder  :  1  4  9  7  20  13  32
Inorder   :  1  4  7  9  13  20  32
Postorder :  7  13  32  20  9  4  1
 After delete node [9] :
Splay Tree
Preorder  :  7  4  1  20  13  32
Inorder   :  1  4  7  13  20  32
Postorder :  1  4  13  32  20  7
 Before delete node [20] :
Splay Tree
Preorder  :  7  4  1  20  13  32
Inorder   :  1  4  7  13  20  32
Postorder :  1  4  13  32  20  7
 After delete node [20] :
Splay Tree
Preorder  :  13  7  4  1  32
Inorder   :  1  4  7  13  32
Postorder :  1  4  7  32  13

Delete node 5 are not exist
//Include namespace system
using System;

// C# program
// Splay tree node deletion

//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 make_root(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;
			}
			make_root(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
			make_root(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);
		}
	}
	//Delete a node in splay tree
	public void delete_node(int value)
	{
		if (this.root != null)
		{
			Node node = this.root;
			Node right_side = null;
			Node left_side = null;
			//First find deleted node in Splay tree
			while (node != null && node.data != value)
			{
				if (value > node.data)
				{
					node = node.right;
				}
				else
				{
					node = node.left;
				}
			}
			if (node != null)
			{
				//When deleted node are exist
				Console.Write("\n Before delete node [" + value + "] :");
				print_tree();
				//Make root of this delete node 
				make_root(node);
				this.root = node;
				if (node.left == null)
				{
					//When no left side subtree of root node
					this.root = node.right;
				}
				else if (node.right == null)
				{
					//When no right side subtree of root node
					this.root = node.left;
				}
				else
				{
					if (node.left != null)
					{
						node.left.parent = null;
					}
					if (node.right != null)
					{
						node.right.parent = null;
					}
					right_side = node.right;
					left_side = node.left;
					this.root = null;
					//remove node
					node.right = null;
					node.left = null;
					node = left_side;
					//Find inorder predecessor
					while (node.right != null)
					{
						node = node.right;
					}
					make_root(node);
					node.right = right_side;
					right_side.parent = node;
					this.root = node;
				}
				Console.Write("\n After delete node [" + value + "] :");
				print_tree();
			}
			else
			{
				Console.Write("\n\nDelete node " + value + " are not exist\n");
			}
			if (this.root != null)
			{
				this.root.parent = null;
			}
		}
	}
	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(20);
		obj.insert_node(13);
		obj.insert_node(32);
		obj.insert_node(1);
		obj.insert_node(4);
		/*
				  Constructed Splay Tree
				  ----------------------

				    4
				  /    \
				 1      9
				  \    / \
				   3  7   20
				         /  \
				        13   32
				*/
		//Test case
		obj.delete_node(3);
		/*
				//After delete 3

				     1  
				      \  
				       4
				        \ 
				         9
				        / \
				       7   20
				          /  \
				         13   32
				*/
		obj.delete_node(9);
		/*
				//After delete 9

				         7
				        / \
				       4   20
				      /   /  \
				     1   13   32
				*/
		obj.delete_node(20);
		/*
				//After delete 20

				           13  
				          /  \ 
				         7    32
				        / 
				       4   
				      /     
				     1      
				*/
		obj.delete_node(5);
	}
}

Output

 Before delete node [3] :
Splay Tree
Preorder  :  4  1  3  9  7  20  13  32
Inorder   :  1  3  4  7  9  13  20  32
Postorder :  3  1  7  13  32  20  9  4
 After delete node [3] :
Splay Tree
Preorder  :  1  4  9  7  20  13  32
Inorder   :  1  4  7  9  13  20  32
Postorder :  7  13  32  20  9  4  1
 Before delete node [9] :
Splay Tree
Preorder  :  1  4  9  7  20  13  32
Inorder   :  1  4  7  9  13  20  32
Postorder :  7  13  32  20  9  4  1
 After delete node [9] :
Splay Tree
Preorder  :  7  4  1  20  13  32
Inorder   :  1  4  7  13  20  32
Postorder :  1  4  13  32  20  7
 Before delete node [20] :
Splay Tree
Preorder  :  7  4  1  20  13  32
Inorder   :  1  4  7  13  20  32
Postorder :  1  4  13  32  20  7
 After delete node [20] :
Splay Tree
Preorder  :  13  7  4  1  32
Inorder   :  1  4  7  13  32
Postorder :  1  4  7  32  13

Delete node 5 are not exist
<?php
// Php program
// Splay tree node deletion

//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 make_root($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->make_root($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->make_root($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);
		}
	}
	//Delete a node in splay tree
	public	function delete_node($value)
	{
		if ($this->root != null)
		{
			$node = $this->root;
			$right_side = null;
			$left_side = null;
			//First find deleted node in Splay tree
			while ($node != null && $node->data != $value)
			{
				if ($value > $node->data)
				{
					$node = $node->right;
				}
				else
				{
					$node = $node->left;
				}
			}
			if ($node != null)
			{
				//When deleted node are exist
				echo "\n Before delete node [". $value ."] :";
				$this->print_tree();
				//Make root of this delete node 
				$this->make_root($node);
				$this->root = $node;
				if ($node->left == null)
				{
					//When no left side subtree of root node
					$this->root = $node->right;
				}
				else if ($node->right == null)
				{
					//When no right side subtree of root node
					$this->root = $node->left;
				}
				else
				{
					if ($node->left != null)
					{
						$node->left->parent = null;
					}
					if ($node->right != null)
					{
						$node->right->parent = null;
					}
					$right_side = $node->right;
					$left_side = $node->left;
					$this->root = null;
					//remove node
					$node->right = null;
					$node->left = null;
					$node = $left_side;
					//Find inorder predecessor
					while ($node->right != null)
					{
						$node = $node->right;
					}
					$this->make_root($node);
					$node->right = $right_side;
					$right_side->parent = $node;
					$this->root = $node;
				}
				echo "\n After delete node [". $value ."] :";
				$this->print_tree();
			}
			else
			{
				echo "\n\nDelete node ". $value ." are not exist\n";
			}
			if ($this->root != null)
			{
				$this->root->parent = null;
			}
		}
	}
}

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

			    4
			  /    \
			 1      9
			  \    / \
			   3  7   20
			         /  \
			        13   32
			*/
	//Test case
	$obj->delete_node(3);
	/*
			//After delete 3

			     1  
			      \  
			       4
			        \ 
			         9
			        / \
			       7   20
			          /  \
			         13   32
			*/
	$obj->delete_node(9);
	/*
			//After delete 9

			         7
			        / \
			       4   20
			      /   /  \
			     1   13   32
			*/
	$obj->delete_node(20);
	/*
			//After delete 20

			           13  
			          /  \ 
			         7    32
			        / 
			       4   
			      /     
			     1      
			*/
	$obj->delete_node(5);
}
main();

Output

 Before delete node [3] :
Splay Tree
Preorder  :  4  1  3  9  7  20  13  32
Inorder   :  1  3  4  7  9  13  20  32
Postorder :  3  1  7  13  32  20  9  4
 After delete node [3] :
Splay Tree
Preorder  :  1  4  9  7  20  13  32
Inorder   :  1  4  7  9  13  20  32
Postorder :  7  13  32  20  9  4  1
 Before delete node [9] :
Splay Tree
Preorder  :  1  4  9  7  20  13  32
Inorder   :  1  4  7  9  13  20  32
Postorder :  7  13  32  20  9  4  1
 After delete node [9] :
Splay Tree
Preorder  :  7  4  1  20  13  32
Inorder   :  1  4  7  13  20  32
Postorder :  1  4  13  32  20  7
 Before delete node [20] :
Splay Tree
Preorder  :  7  4  1  20  13  32
Inorder   :  1  4  7  13  20  32
Postorder :  1  4  13  32  20  7
 After delete node [20] :
Splay Tree
Preorder  :  13  7  4  1  32
Inorder   :  1  4  7  13  32
Postorder :  1  4  7  32  13

Delete node 5 are not exist
// Node Js program
// Splay tree node deletion

//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
	make_root(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.make_root(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.make_root(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);
		}
	}
	//Delete a node in splay tree
	delete_node(value)
	{
		if (this.root != null)
		{
			var node = this.root;
			var right_side = null;
			var left_side = null;
			//First find deleted node in Splay tree
			while (node != null && node.data != value)
			{
				if (value > node.data)
				{
					node = node.right;
				}
				else
				{
					node = node.left;
				}
			}
			if (node != null)
			{
				//When deleted node are exist
				process.stdout.write("\n Before delete node [" + value + "] :");
				this.print_tree();
				//Make root of this delete node 
				this.make_root(node);
				this.root = node;
				if (node.left == null)
				{
					//When no left side subtree of root node
					this.root = node.right;
				}
				else if (node.right == null)
				{
					//When no right side subtree of root node
					this.root = node.left;
				}
				else
				{
					if (node.left != null)
					{
						node.left.parent = null;
					}
					if (node.right != null)
					{
						node.right.parent = null;
					}
					right_side = node.right;
					left_side = node.left;
					this.root = null;
					//remove node
					node.right = null;
					node.left = null;
					node = left_side;
					//Find inorder predecessor
					while (node.right != null)
					{
						node = node.right;
					}
					this.make_root(node);
					node.right = right_side;
					right_side.parent = node;
					this.root = node;
				}
				process.stdout.write("\n After delete node [" + value + "] :");
				this.print_tree();
			}
			else
			{
				process.stdout.write("\n\nDelete node " + value + " are not exist\n");
			}
			if (this.root != null)
			{
				this.root.parent = null;
			}
		}
	}
}

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

			    4
			  /    \
			 1      9
			  \    / \
			   3  7   20
			         /  \
			        13   32
			*/
	//Test case
	obj.delete_node(3);
	/*
			//After delete 3

			     1  
			      \  
			       4
			        \ 
			         9
			        / \
			       7   20
			          /  \
			         13   32
			*/
	obj.delete_node(9);
	/*
			//After delete 9

			         7
			        / \
			       4   20
			      /   /  \
			     1   13   32
			*/
	obj.delete_node(20);
	/*
			//After delete 20

			           13  
			          /  \ 
			         7    32
			        / 
			       4   
			      /     
			     1      
			*/
	obj.delete_node(5);
}
main();

Output

 Before delete node [3] :
Splay Tree
Preorder  :  4  1  3  9  7  20  13  32
Inorder   :  1  3  4  7  9  13  20  32
Postorder :  3  1  7  13  32  20  9  4
 After delete node [3] :
Splay Tree
Preorder  :  1  4  9  7  20  13  32
Inorder   :  1  4  7  9  13  20  32
Postorder :  7  13  32  20  9  4  1
 Before delete node [9] :
Splay Tree
Preorder  :  1  4  9  7  20  13  32
Inorder   :  1  4  7  9  13  20  32
Postorder :  7  13  32  20  9  4  1
 After delete node [9] :
Splay Tree
Preorder  :  7  4  1  20  13  32
Inorder   :  1  4  7  13  20  32
Postorder :  1  4  13  32  20  7
 Before delete node [20] :
Splay Tree
Preorder  :  7  4  1  20  13  32
Inorder   :  1  4  7  13  20  32
Postorder :  1  4  13  32  20  7
 After delete node [20] :
Splay Tree
Preorder  :  13  7  4  1  32
Inorder   :  1  4  7  13  32
Postorder :  1  4  7  32  13

Delete node 5 are not exist
#  Python 3 program
#  Splay tree node deletion

# 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 make_root(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.make_root(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.make_root(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)
		
	
	# Delete a node in splay tree
	def delete_node(self, value) :
		if (self.root != None) :
			node = self.root
			right_side = None
			left_side = None
			# First find deleted node in Splay tree
			while (node != None and node.data != value) :
				if (value > node.data) :
					node = node.right
				else :
					node = node.left
				
			
			if (node != None) :
				# When deleted node are exist
				print("\n Before delete node [", value ,"] :", end = "")
				self.print_tree()
				# Make root of this delete node 
				self.make_root(node)
				self.root = node
				if (node.left == None) :
					# When no left side subtree of root node
					self.root = node.right
				
				elif(node.right == None) :
					# When no right side subtree of root node
					self.root = node.left
				else :
					if (node.left != None) :
						node.left.parent = None
					
					if (node.right != None) :
						node.right.parent = None
					
					right_side = node.right
					left_side = node.left
					self.root = None
					# remove node
					node.right = None
					node.left = None
					node = left_side
					# Find inorder predecessor
					while (node.right != None) :
						node = node.right
					
					self.make_root(node)
					node.right = right_side
					right_side.parent = node
					self.root = node
				
				print("\n After delete node [", value ,"] :", end = "")
				self.print_tree()
			else :
				print("\n\nDelete node ", value ," are not exist\n", end = "")
			
			if (self.root != None) :
				self.root.parent = None
			
		
	

def main() :
	obj = SplayTree()
	# Add tree node
	obj.insert_node(9)
	obj.insert_node(3)
	obj.insert_node(7)
	obj.insert_node(20)
	obj.insert_node(13)
	obj.insert_node(32)
	obj.insert_node(1)
	obj.insert_node(4)
	# 
	# 		  Constructed Splay Tree
	# 		  ----------------------
	# 		    4
	# 		  /    \
	# 		 1      9
	# 		  \    / \
	# 		   3  7   20
	# 		         /  \
	# 		        13   32
	# 		
	
	# Test case
	obj.delete_node(3)
	# 
	# 		//After delete 3
	# 		     1  
	# 		      \  
	# 		       4
	# 		        \ 
	# 		         9
	# 		        / \
	# 		       7   20
	# 		          /  \
	# 		         13   32
	# 		
	
	obj.delete_node(9)
	# 
	# 		//After delete 9
	# 		         7
	# 		        / \
	# 		       4   20
	# 		      /   /  \
	# 		     1   13   32
	# 		
	
	obj.delete_node(20)
	# 
	# 		//After delete 20
	# 		           13  
	# 		          /  \ 
	# 		         7    32
	# 		        / 
	# 		       4   
	# 		      /     
	# 		     1      
	# 		
	
	obj.delete_node(5)

if __name__ == "__main__": main()

Output

 Before delete node [ 3 ] :
Splay Tree
Preorder  :   4   1   3   9   7   20   13   32
Inorder   :   1   3   4   7   9   13   20   32
Postorder :   3   1   7   13   32   20   9   4
 After delete node [ 3 ] :
Splay Tree
Preorder  :   1   4   9   7   20   13   32
Inorder   :   1   4   7   9   13   20   32
Postorder :   7   13   32   20   9   4   1
 Before delete node [ 9 ] :
Splay Tree
Preorder  :   1   4   9   7   20   13   32
Inorder   :   1   4   7   9   13   20   32
Postorder :   7   13   32   20   9   4   1
 After delete node [ 9 ] :
Splay Tree
Preorder  :   7   4   1   20   13   32
Inorder   :   1   4   7   13   20   32
Postorder :   1   4   13   32   20   7
 Before delete node [ 20 ] :
Splay Tree
Preorder  :   7   4   1   20   13   32
Inorder   :   1   4   7   13   20   32
Postorder :   1   4   13   32   20   7
 After delete node [ 20 ] :
Splay Tree
Preorder  :   13   7   4   1   32
Inorder   :   1   4   7   13   32
Postorder :   1   4   7   32   13

Delete node  5  are not exist
#  Ruby program
#  Splay tree node deletion

# 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 make_root(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.make_root(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.make_root(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
	# Delete a node in splay tree
	def delete_node(value)
	
		if (self.root != nil)
		
			node = self.root
			right_side = nil
			left_side = nil
			# First find deleted node in Splay tree
			while (node != nil && node.data != value)
			
				if (value > node.data)
				
					node = node.right
				else
				
					node = node.left
				end
			end
			if (node != nil)
			
				# When deleted node are exist
				print("\n Before delete node [", value ,"] :")
				self.print_tree()
				# Make root of this delete node 
				self.make_root(node)
				self.root = node
				if (node.left == nil)
				
					# When no left side subtree of root node
					self.root = node.right
				elsif(node.right == nil)
				
					# When no right side subtree of root node
					self.root = node.left
				else
				
					if (node.left != nil)
					
						node.left.parent = nil
					end
					if (node.right != nil)
					
						node.right.parent = nil
					end
					right_side = node.right
					left_side = node.left
					self.root = nil
					# remove node
					node.right = nil
					node.left = nil
					node = left_side
					# Find inorder predecessor
					while (node.right != nil)
					
						node = node.right
					end
					self.make_root(node)
					node.right = right_side
					right_side.parent = node
					self.root = node
				end
				print("\n After delete node [", value ,"] :")
				self.print_tree()
			else
			
				print("\n\nDelete node ", value ," are not exist\n")
			end
			if (self.root != nil)
			
				self.root.parent = nil
			end
		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(20)
	obj.insert_node(13)
	obj.insert_node(32)
	obj.insert_node(1)
	obj.insert_node(4)
	# 
	# 		  Constructed Splay Tree
	# 		  ----------------------
	# 		    4
	# 		  /    \
	# 		 1      9
	# 		  \    / \
	# 		   3  7   20
	# 		         /  \
	# 		        13   32
	# 		
	
	# Test case
	obj.delete_node(3)
	# 
	# 		//After delete 3
	# 		     1  
	# 		      \  
	# 		       4
	# 		        \ 
	# 		         9
	# 		        / \
	# 		       7   20
	# 		          /  \
	# 		         13   32
	# 		
	
	obj.delete_node(9)
	# 
	# 		//After delete 9
	# 		         7
	# 		        / \
	# 		       4   20
	# 		      /   /  \
	# 		     1   13   32
	# 		
	
	obj.delete_node(20)
	# 
	# 		//After delete 20
	# 		           13  
	# 		          /  \ 
	# 		         7    32
	# 		        / 
	# 		       4   
	# 		      /     
	# 		     1      
	# 		
	
	obj.delete_node(5)
end
main()

Output

 Before delete node [3] :
Splay Tree 
Preorder  :  4  1  3  9  7  20  13  32
Inorder   :  1  3  4  7  9  13  20  32
Postorder :  3  1  7  13  32  20  9  4
 After delete node [3] :
Splay Tree 
Preorder  :  1  4  9  7  20  13  32
Inorder   :  1  4  7  9  13  20  32
Postorder :  7  13  32  20  9  4  1
 Before delete node [9] :
Splay Tree 
Preorder  :  1  4  9  7  20  13  32
Inorder   :  1  4  7  9  13  20  32
Postorder :  7  13  32  20  9  4  1
 After delete node [9] :
Splay Tree 
Preorder  :  7  4  1  20  13  32
Inorder   :  1  4  7  13  20  32
Postorder :  1  4  13  32  20  7
 Before delete node [20] :
Splay Tree 
Preorder  :  7  4  1  20  13  32
Inorder   :  1  4  7  13  20  32
Postorder :  1  4  13  32  20  7
 After delete node [20] :
Splay Tree 
Preorder  :  13  7  4  1  32
Inorder   :  1  4  7  13  32
Postorder :  1  4  7  32  13

Delete node 5 are not exist
// Scala program
// Splay tree node deletion
//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 make_root(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;
			}
			make_root(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
			make_root(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);
		}
	}
	//Delete a node in splay tree
	def delete_node(value: Int): Unit = {
		if (this.root != null)
		{
			var node: Node = this.root;
			var right_side: Node = null;
			var left_side: Node = null;
			//First find deleted node in Splay tree
			while (node != null && node.data != value)
			{
				if (value > node.data)
				{
					node = node.right;
				}
				else
				{
					node = node.left;
				}
			}
			if (node != null)
			{
				//When deleted node are exist
				print("\n Before delete node [" + value + "] :");
				print_tree();
				//Make root of this delete node 
				make_root(node);
				this.root = node;
				if (node.left == null)
				{
					//When no left side subtree of root node
					this.root = node.right;
				}
				else if (node.right == null)
				{
					//When no right side subtree of root node
					this.root = node.left;
				}
				else
				{
					if (node.left != null)
					{
						node.left.parent = null;
					}
					if (node.right != null)
					{
						node.right.parent = null;
					}
					right_side = node.right;
					left_side = node.left;
					this.root = null;
					//remove node
					node.right = null;
					node.left = null;
					node = left_side;
					//Find inorder predecessor
					while (node.right != null)
					{
						node = node.right;
					}
					make_root(node);
					node.right = right_side;
					right_side.parent = node;
					this.root = node;
				}
				print("\n After delete node [" + value + "] :");
				print_tree();
			}
			else
			{
				print("\n\nDelete node " + value + " are not exist\n");
			}
			if (this.root != null)
			{
				this.root.parent = null;
			}
		}
	}
}
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(20);
		obj.insert_node(13);
		obj.insert_node(32);
		obj.insert_node(1);
		obj.insert_node(4);
		/*
				  Constructed Splay Tree
				  ----------------------

				    4
				  /    \
				 1      9
				  \    / \
				   3  7   20
				         /  \
				        13   32
				*/
		//Test case
		obj.delete_node(3);
		/*
				//After delete 3

				     1  
				      \  
				       4
				        \ 
				         9
				        / \
				       7   20
				          /  \
				         13   32
				*/
		obj.delete_node(9);
		/*
				//After delete 9

				         7
				        / \
				       4   20
				      /   /  \
				     1   13   32
				*/
		obj.delete_node(20);
		/*
				//After delete 20

				           13  
				          /  \ 
				         7    32
				        / 
				       4   
				      /     
				     1      
				*/
		obj.delete_node(5);
	}
}

Output

 Before delete node [3] :
Splay Tree
Preorder  :  4  1  3  9  7  20  13  32
Inorder   :  1  3  4  7  9  13  20  32
Postorder :  3  1  7  13  32  20  9  4
 After delete node [3] :
Splay Tree
Preorder  :  1  4  9  7  20  13  32
Inorder   :  1  4  7  9  13  20  32
Postorder :  7  13  32  20  9  4  1
 Before delete node [9] :
Splay Tree
Preorder  :  1  4  9  7  20  13  32
Inorder   :  1  4  7  9  13  20  32
Postorder :  7  13  32  20  9  4  1
 After delete node [9] :
Splay Tree
Preorder  :  7  4  1  20  13  32
Inorder   :  1  4  7  13  20  32
Postorder :  1  4  13  32  20  7
 Before delete node [20] :
Splay Tree
Preorder  :  7  4  1  20  13  32
Inorder   :  1  4  7  13  20  32
Postorder :  1  4  13  32  20  7
 After delete node [20] :
Splay Tree
Preorder  :  13  7  4  1  32
Inorder   :  1  4  7  13  32
Postorder :  1  4  7  32  13

Delete node 5 are not exist
// Swift program
// Splay tree node deletion

//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 make_root(_ 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.make_root(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.make_root(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);
		}
	}
	//Delete a node in splay tree
	func delete_node(_ value: Int)
	{
		if (self.root != nil)
		{
			var node: Node? = self.root;
			var right_side: Node? = nil;
			var left_side: Node? = nil;
			//First find deleted node in Splay tree
			while (node != nil && node!.data != value)
			{
				if (value > node!.data)
				{
					node = node!.right;
				}
				else
				{
					node = node!.left;
				}
			}
			if (node != nil)
			{
				//When deleted node are exist
				print("\n Before delete node [", value ,"] :", terminator: "");
				self.print_tree();
				//Make root of this delete node 
				self.make_root(node);
				self.root = node;
				if (node!.left == nil)
				{
					//When no left side subtree of root node
					self.root = node!.right;
				}
				else if (node!.right == nil)
				{
					//When no right side subtree of root node
					self.root = node!.left;
				}
				else
				{
					if (node!.left != nil)
					{
						node!.left!.parent = nil;
					}
					if (node!.right != nil)
					{
						node!.right!.parent = nil;
					}
					right_side = node!.right;
					left_side = node!.left;
					self.root = nil;
					//remove node
					node!.right = nil;
					node!.left = nil;
					node = left_side;
					//Find inorder predecessor
					while (node!.right != nil)
					{
						node = node!.right;
					}
					self.make_root(node);
					node!.right = right_side;
					right_side!.parent = node;
					self.root = node;
				}
				print("\n After delete node [", value ,"] :", terminator: "");
				self.print_tree();
			}
			else
			{
				print("\n\nDelete node ", value ," are not exist\n", terminator: "");
			}
			if (self.root != nil)
			{
				self.root!.parent = nil;
			}
		}
	}
}
func main()
{
	let obj: SplayTree = SplayTree();
	//Add tree node
	obj.insert_node(9);
	obj.insert_node(3);
	obj.insert_node(7);
	obj.insert_node(20);
	obj.insert_node(13);
	obj.insert_node(32);
	obj.insert_node(1);
	obj.insert_node(4);
	/*
			  Constructed Splay Tree
			  ----------------------

			    4
			  /    \
			 1      9
			  \    / \
			   3  7   20
			         /  \
			        13   32
			*/
	//Test case
	obj.delete_node(3);
	/*
			//After delete 3

			     1  
			      \  
			       4
			        \ 
			         9
			        / \
			       7   20
			          /  \
			         13   32
			*/
	obj.delete_node(9);
	/*
			//After delete 9

			         7
			        / \
			       4   20
			      /   /  \
			     1   13   32
			*/
	obj.delete_node(20);
	/*
			//After delete 20

			           13  
			          /  \ 
			         7    32
			        / 
			       4   
			      /     
			     1      
			*/
	obj.delete_node(5);
}
main();

Output

 Before delete node [ 3 ] :
Splay Tree
Preorder  :   4   1   3   9   7   20   13   32
Inorder   :   1   3   4   7   9   13   20   32
Postorder :   3   1   7   13   32   20   9   4
 After delete node [ 3 ] :
Splay Tree
Preorder  :   1   4   9   7   20   13   32
Inorder   :   1   4   7   9   13   20   32
Postorder :   7   13   32   20   9   4   1
 Before delete node [ 9 ] :
Splay Tree
Preorder  :   1   4   9   7   20   13   32
Inorder   :   1   4   7   9   13   20   32
Postorder :   7   13   32   20   9   4   1
 After delete node [ 9 ] :
Splay Tree
Preorder  :   7   4   1   20   13   32
Inorder   :   1   4   7   13   20   32
Postorder :   1   4   13   32   20   7
 Before delete node [ 20 ] :
Splay Tree
Preorder  :   7   4   1   20   13   32
Inorder   :   1   4   7   13   20   32
Postorder :   1   4   13   32   20   7
 After delete node [ 20 ] :
Splay Tree
Preorder  :   13   7   4   1   32
Inorder   :   1   4   7   13   32
Postorder :   1   4   7   32   13

Delete node  5  are not exist

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