AVL tree with duplicate key

Here given code implementation process.

//C Program
//AVL tree with duplicate key
#include <stdio.h>

#include <stdlib.h>

//Avl tree node
struct Node
{
	//Data value of tree
	int key;
	//used to hold the height of current node
	int height;
	//Count occurrence nodes
	int occurrence;
	//Indicate left and right subtree
	struct Node *left;
	struct Node *right;
};
//Get the height of given node
int height(struct Node *node)
{
	if (node == NULL)
	{
		return 0;
	}
	return node->height;
}
//Get the max value of given two numbers
int max_height(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	else
	{
		return b;
	}
}
//Create a new Avl Tree node
struct Node *new_node(int key)
{
	//Create a tree node
	struct Node *node = (struct Node *) malloc(sizeof(struct Node));
	if (node != NULL)
	{
		//Set initial node values
		node->key = key;
		node->height = 1;
		node->left = NULL;
		node->right = NULL;
		node->occurrence = 1;
	}
	else
	{
		printf("\nMemory overflow");
	}
	return node;
}
// Perform the Right rotate operation
struct Node *right_rotate(struct Node *node)
{
	//Get left child node
	struct Node *left_node = node->left;
	//Get left node right subtree
	struct Node *right_subtree = left_node->right;
	//update the left and right subtree 
	left_node->right = node;
	node->left = right_subtree;
	//Change the height of modified node
	node->height = max_height(height(node->left), height(node->right)) + 1;
	left_node->height = max_height(height(left_node->left), height(left_node->right)) + 1;
	return left_node;
}
// Perform the Left Rotate operation
struct Node *left_rotate(struct Node *node)
{
	// Get right child node
	struct Node *right_node = node->right;
	//Get right node left subtree
	struct Node *left_subtree = right_node->left;
	//update the left and right subtree 
	right_node->left = node;
	node->right = left_subtree;
	//Change the height of modified node
	node->height = max_height(height(node->left), height(node->right)) + 1;
	right_node->height = max_height(height(right_node->left), height(right_node->right)) + 1;
	return right_node;
}
// Get the balance factor
int get_balance_factor(struct Node *node)
{
	if (node == NULL)
	{
		return 0;
	}
	return height(node->left) - height(node->right);
}
// Recursively, add a node in AVL tree
// Duplicate keys (key) are allowed
struct Node *add_node(struct Node *node, int key)
{
	if (node == NULL)
	{
		//return a new node
		return new_node(key);
	}
	if (key < node->key)
	{
		node->left = add_node(node->left, key);
	}
	else if (key > node->key)
	{
		node->right = add_node(node->right, key);
	}
	else
	{
		node->occurrence = node->occurrence + 1;
		//When given key key already exists
		return node;
	}
	// Change the height of current node
	node->height = 1 + max_height(height(node->left), height(node->right));
	//Get balance factor of a node
	int balance_factor = get_balance_factor(node);
	// RR Case
	if (balance_factor > 1 && key < node->left->key)
	{
		return right_rotate(node);
	}
	// LL Case 
	if (balance_factor < -1 && key > node->right->key)
	{
		return left_rotate(node);
	}
	// LR Case
	if (balance_factor > 1 && key > node->left->key)
	{
		node->left = left_rotate(node->left);
		return right_rotate(node);
	}
	// RL Case 
	if (balance_factor < -1 && key < node->right->key)
	{
		node->right = right_rotate(node->right);
		return left_rotate(node);
	}
	return node;
}
//Find the minimum node on left side
struct Node *min_key_node(struct Node *node)
{
	struct Node *result = node;
	while (result->left != NULL)
	{
		result = result->left;
	}
	return result;
}
// Delete given node key(key) in AVL tree
struct Node *delete_node(struct Node *root, int key)
{
	if (root == NULL)
	{
		return root;
	}
	//When deleted nodes are possible in left subtree
	if (key < root->key)
	{
		root->left = delete_node(root->left, key);
	}
	//  When deleted nodes are possible in right subtree
	else if (key > root->key)
	{
		root->right = delete_node(root->right, key);
	}
	else
	{
		if (root->occurrence > 1)
		{
			// When node exists more than once
			// Update the node occurrence
			root->occurrence = root->occurrence - 1;
			return root;
		}
		struct Node *temp = NULL;
		//When deleted node is current node (root)
		if ((root->left == NULL) || (root->right == NULL))
		{
			if (root->left != NULL)
			{
				//When left subtree are exists
				temp = root->left;
			}
			else if (root->right != NULL)
			{
				//When left subtree are exists
				temp = root->right;
			}
			if (temp == NULL)
			{
				// When delete leaf node
				// Get deleted node
				temp = root;
				//In this case set the current root node value to zero
				root = NULL;
			}
			else
			{
				// One child case 
				*root = *temp; // Copy the contents of 
				// the non-empty child 
			}
			//free the deleted node
			free(temp);
			temp = NULL;
		}
		else
		{
			//When left and right both subtree exists
			// Find inorder successor 
			temp = min_key_node(root->right);
			// Set new value to current node
			root->key = temp->key;
			// Delete smallest element in find node
			// Goal to delete leaf node
			root->right = delete_node(root->right, temp->key);
		}
	}
	// If the tree had only one node then return 
	if (root == NULL)
	{
		return root;
	}
	// set height of current node 
	root->height = 1 + max_height(height(root->left), height(root->right));
	// get balance factor
	int balance = get_balance_factor(root);
	// Transform into a balanced avl  tree 
	// 4 possible situation
	if (balance > 1 && get_balance_factor(root->left) >= 0)
	{
		return right_rotate(root);
	}
	if (balance > 1 && get_balance_factor(root->left) < 0)
	{
		root->left = left_rotate(root->left);
		return right_rotate(root);
	}
	if (balance < -1 && get_balance_factor(root->right) <= 0)
	{
		return left_rotate(root);
	}
	if (balance < -1 && get_balance_factor(root->right) > 0)
	{
		root->right = right_rotate(root->right);
		return left_rotate(root);
	}
	return root;
}
//Check that whether given key node is exist in given tree
int node_exist(struct Node *root, int key)
{
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		if (root->key == key)
		{
			//When node is exist
			return 1;
		}
		return (node_exist(root->left, key) || node_exist(root->right, key));
	}
}
// Print avl tree in preorder traversal
void preorder(struct Node *root)
{
	if (root != NULL)
	{
		printf(" %d(%d)", root->key, root->occurrence);
		preorder(root->left);
		preorder(root->right);
	}
}
//This is handling the request of deleted node in AVL
struct Node *delete_tree_node(struct Node *root, int key)
{
	if (node_exist(root, key) == 1)
	{
		printf("\n Before Delete node %d element \n", key);
		preorder(root);
		root = delete_node(root, key);
		printf("\n After Delete node %d element \n", key);
		preorder(root);
	}
	else
	{
		printf("\n Deleted node %d is not found  \n", key);
		preorder(root);
	}
	return root;
}
int main()
{
	struct Node *root = NULL;
	//add tree node
	root = add_node(root, 12);
	root = add_node(root, 7);
	root = add_node(root, 5);
	root = add_node(root, 19);
	root = add_node(root, 17);
	root = add_node(root, 13);
	root = add_node(root, 11);
	root = add_node(root, 3);
	root = add_node(root, 2);
	root = add_node(root, 7);
	/*
	    Resultant  AVL Tree
	    -----------------

	           12
	          /  \ 
	         /    \
	     (2)7      17
	       / \     / \
	      3   11  13  19
	     / \
	    2   5

	*/
	root = delete_tree_node(root, 7);
	/*
	   After delete node 7
	    -----------------

	           12
	          /  \ 
	         /    \
	     (1)7      17
	       / \     / \
	      3   11  13  19
	     / \
	    2   5
	*/
	root = delete_tree_node(root, 11);
	/*
    After delete node 11
    -----------------

             12
            /  \ 
           /    \
          7      17
         / \     / \
        3   11  13  19
       / \
      2   5

      //remove node

             12
            /  \ 
           /    \
          7      17
         /       / \
        3       13  19
       / \
      2   5

    //  Balance the AVL tree

             12
            /  \ 
           /    \
          3      17
         / \     / \
        2   7  13  19
           /
          5
  */
	return 0;
}

Output

 Before Delete node 7 element
 12(1) 7(2) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
 After Delete node 7 element
 12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
 Before Delete node 11 element
 12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
 After Delete node 11 element
 12(1) 3(1) 2(1) 7(1) 5(1) 17(1) 13(1) 19(1)
// Java program
// Avl tree node deletion

//Avl tree node
class Node
{
	public int key;
	public int height;
	public int occurrence;
	public Node left;
	public Node right;
	public Node(int key)
	{
		//Set node value of avl tree
		this.key = key;
		this.height = 1;
		this.occurrence = 1;
		this.left = null;
		this.right = null;
	}
}
class AvlTree
{
	public Node root;
	public AvlTree()
	{
		this.root = null;
	}
	//Get the height of given node
	public int height(Node node)
	{
		if (node == null)
		{
			return 0;
		}
		return node.height;
	}
	//Get the max value of given two numbers
	public int max_height(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	public Node right_rotate(Node node)
	{
		//Get left child node
		Node left_node = node.left;
		//Get left node right subtree
		Node right_subtree = left_node.right;
		//update the left and right subtree 
		left_node.right = node;
		node.left = right_subtree;
		//Change the height of modified node
		node.height = max_height(height(node.left), height(node.right)) + 1;
		left_node.height = max_height(height(left_node.left), height(left_node.right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	public Node left_rotate(Node node)
	{
		// Get right child node
		Node right_node = node.right;
		//Get right node left subtree
		Node left_subtree = right_node.left;
		//update the left and right subtree 
		right_node.left = node;
		node.right = left_subtree;
		//Change the height of modified node
		node.height = max_height(height(node.left), height(node.right)) + 1;
		right_node.height = max_height(height(right_node.left), height(right_node.right)) + 1;
		return right_node;
	}
	// Get the balance factor
	public int get_balance_factor(Node node)
	{
		if (node == null)
		{
			return 0;
		}
		return height(node.left) - height(node.right);
	}
	// Recursively, add a node in AVL tree
	// Duplicate keys (key) are allowed
	public Node add_node(Node node, int key)
	{
		if (node == null)
		{
			//return a new node
			return new Node(key);
		}
		if (key < node.key)
		{
			node.left = add_node(node.left, key);
		}
		else if (key > node.key)
		{
			node.right = add_node(node.right, key);
		}
		else
		{
			//When given key already exists
			node.occurrence = node.occurrence + 1;
			return node;
		}
		// Change the height of current node
		node.height = 1 + max_height(height(node.left), height(node.right));
		//Get balance factor of a node
		int balance_factor = get_balance_factor(node);
		if (balance_factor > 1 && key < node.left.key)
		{
			return right_rotate(node);
		}
		if (balance_factor < -1 && key > node.right.key)
		{
			return left_rotate(node);
		}
		if (balance_factor > 1 && key > node.left.key)
		{
			node.left = left_rotate(node.left);
			return right_rotate(node);
		}
		if (balance_factor < -1 && key < node.right.key)
		{
			node.right = right_rotate(node.right);
			return left_rotate(node);
		}
		return node;
	}
	// Print avl tree in preorder traversal
	public void preorder(Node root)
	{
		if (root != null)
		{
			System.out.print("  " + root.key + "(" + root.occurrence + ")");
			preorder(root.left);
			preorder(root.right);
		}
	}
	//Find the minimum node on left side
	public Node min_key_node(Node node)
	{
		Node result = node;
		while (result.left != null)
		{
			result = result.left;
		}
		return result;
	}
	// Delete given node key(key) in AVL tree
	public Node delete_node(Node root, int key)
	{
		if (root == null)
		{
			return root;
		}
		//When deleted nodes are possible in left subtree
		if (key < root.key)
		{
			root.left = delete_node(root.left, key);
		}
		//  When deleted nodes are possible in right subtree
		else if (key > root.key)
		{
			root.right = delete_node(root.right, key);
		}
		else
		{
			if (root.occurrence > 1)
			{
				root.occurrence--;
				return root;
			}
			Node temp = null;
			//When deleted node is current node (root)
			if ((root.left == null) || (root.right == null))
			{
				if (root.left != null)
				{
					//When left subtree are exists
					temp = root.left;
				}
				else if (root.right != null)
				{
					//When left subtree are exists
					temp = root.right;
				}
				if (temp == null)
				{
					// When delete leaf node
					// Get deleted node
					temp = root;
					//In this case set the current root node value to zero
					root = null;
				}
				else
				{
					// One child case 
					root = temp;
				}
				//free the deleted node
				temp = null;
			}
			else
			{
				//When left and right both subtree exists
				// Find inorder successor 
				temp = min_key_node(root.right);
				// Set new value to current node
				root.key = temp.key;
				// Delete smallest element in find node
				// Goal to delete leaf node
				root.right = delete_node(root.right, temp.key);
			}
		}
		// If the tree had only one node then return 
		if (root == null)
		{
			return root;
		}
		// set height of current node 
		root.height = 1 + max_height(height(root.left), height(root.right));
		// get balance factor
		int balance = get_balance_factor(root);
		// Transform into a balanced avl  tree 
		// 4 possible situation
		if (balance > 1 && get_balance_factor(root.left) >= 0)
		{
			return right_rotate(root);
		}
		if (balance > 1 && get_balance_factor(root.left) < 0)
		{
			root.left = left_rotate(root.left);
			return right_rotate(root);
		}
		if (balance < -1 && get_balance_factor(root.right) <= 0)
		{
			return left_rotate(root);
		}
		if (balance < -1 && get_balance_factor(root.right) > 0)
		{
			root.right = right_rotate(root.right);
			return left_rotate(root);
		}
		return root;
	}
	//Check that whether given key node is exist in given tree
	public boolean node_exist(Node root, int key)
	{
		if (root == null)
		{
			return false;
		}
		else
		{
			if (root.key == key)
			{
				//When node is exist
				return true;
			}
			return (node_exist(root.left, key) || node_exist(root.right, key));
		}
	}
	//This is handling the request of deleted node in AVL
	public void delete_tree_node(int key)
	{
		if (this.root != null && node_exist(this.root, key) == true)
		{
			System.out.print("\n Before Delete node " + key + " element \n");
			preorder(this.root);
			this.root = delete_node(this.root, key);
			System.out.print("\n After Delete node " + key + " element \n");
			preorder(this.root);
		}
		else
		{
			System.out.print("\n Deleted node " + key + " is not found \n");
			preorder(this.root);
		}
	}
	public static void main(String[] args)
	{
		AvlTree obj = new AvlTree();
		//add tree node
		obj.root = obj.add_node(obj.root, 12);
		obj.root = obj.add_node(obj.root, 7);
		obj.root = obj.add_node(obj.root, 5);
		obj.root = obj.add_node(obj.root, 19);
		obj.root = obj.add_node(obj.root, 17);
		obj.root = obj.add_node(obj.root, 13);
		obj.root = obj.add_node(obj.root, 11);
		obj.root = obj.add_node(obj.root, 3);
		obj.root = obj.add_node(obj.root, 2);
		obj.root = obj.add_node(obj.root, 7);
		/*
		    Resultant  AVL Tree
		    -----------------

		           12
		          /  \ 
		         /    \
		     (2)7      17
		       / \     / \
		      3   11  13  19
		     / \
		    2   5

		*/
		obj.delete_tree_node(7);
		/*
		   After delete node 7
		    -----------------

		           12
		          /  \ 
		         /    \
		     (1)7      17
		       / \     / \
		      3   11  13  19
		     / \
		    2   5
		*/
		obj.delete_tree_node(11);
		/*
    After delete node 11
    -----------------

             12
            /  \ 
           /    \
          7      17
         / \     / \
        3   11  13  19
       / \
      2   5

      //remove node

             12
            /  \ 
           /    \
          7      17
         /       / \
        3       13  19
       / \
      2   5

    //  Balance the AVL tree

             12
            /  \ 
           /    \
          3      17
         / \     / \
        2   7  13  19
           /
          5
  */
		
	}
}

Output

 Before Delete node 7 element
  12(1)  7(2)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 After Delete node 7 element
  12(1)  7(1)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 Before Delete node 11 element
  12(1)  7(1)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 After Delete node 11 element
  12(1)  3(1)  2(1)  7(1)  5(1)  17(1)  13(1)  19(1)
//Include header file
#include <iostream>
using namespace std;
// C++ program
// Avl tree node deletion

//Avl tree node
class Node
{
	public: int key;
	int height;
	int occurrence;
	Node * left;
	Node * right;
	Node(int key)
	{
		//Set node value of avl tree
		this->key = key;
		this->height = 1;
		this->occurrence = 1;
		this->left = NULL;
		this->right = NULL;
	}
};
class AvlTree
{
	public: Node * root;
	AvlTree()
	{
		this->root = NULL;
	}
	//Get the height of given node
	int height(Node * node)
	{
		if (node == NULL)
		{
			return 0;
		}
		return node->height;
	}
	//Get the max value of given two numbers
	int max_height(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	Node * right_rotate(Node * node)
	{
		//Get left child node
		Node * left_node = node->left;
		//Get left node right subtree
		Node * right_subtree = left_node->right;
		//update the left and right subtree 
		left_node->right = node;
		node->left = right_subtree;
		//Change the height of modified node
		node->height = this->max_height(this->height(node->left), this->height(node->right)) + 1;
		left_node->height = this->max_height(this->height(left_node->left), this->height(left_node->right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	Node * left_rotate(Node * node)
	{
		// Get right child node
		Node * right_node = node->right;
		//Get right node left subtree
		Node * left_subtree = right_node->left;
		//update the left and right subtree 
		right_node->left = node;
		node->right = left_subtree;
		//Change the height of modified node
		node->height = this->max_height(this->height(node->left), this->height(node->right)) + 1;
		right_node->height = this->max_height(this->height(right_node->left), this->height(right_node->right)) + 1;
		return right_node;
	}
	// Get the balance factor
	int get_balance_factor(Node * node)
	{
		if (node == NULL)
		{
			return 0;
		}
		return this->height(node->left) - this->height(node->right);
	}
	// Recursively, add a node in AVL tree
	// Duplicate keys (key) are allowed
	Node * add_node(Node * node, int key)
	{
		if (node == NULL)
		{
			//return a new node
			return new Node(key);
		}
		if (key < node->key)
		{
			node->left = this->add_node(node->left, key);
		}
		else if (key > node->key)
		{
			node->right = this->add_node(node->right, key);
		}
		else
		{
			//When given key already exists
			node->occurrence = node->occurrence + 1;
			return node;
		}
		// Change the height of current node
		node->height = 1 + this->max_height(this->height(node->left), this->height(node->right));
		//Get balance factor of a node
		int balance_factor = this->get_balance_factor(node);
		if (balance_factor > 1 && key < node->left->key)
		{
			return this->right_rotate(node);
		}
		if (balance_factor < -1 && key > node->right->key)
		{
			return this->left_rotate(node);
		}
		if (balance_factor > 1 && key > node->left->key)
		{
			node->left = this->left_rotate(node->left);
			return this->right_rotate(node);
		}
		if (balance_factor < -1 && key < node->right->key)
		{
			node->right = this->right_rotate(node->right);
			return this->left_rotate(node);
		}
		return node;
	}
	// Print avl tree in preorder traversal
	void preorder(Node * root)
	{
		if (root != NULL)
		{
			cout << "  " << root->key << "(" << root->occurrence << ")";
			this->preorder(root->left);
			this->preorder(root->right);
		}
	}
	//Find the minimum node on left side
	Node * min_key_node(Node * node)
	{
		Node * result = node;
		while (result->left != NULL)
		{
			result = result->left;
		}
		return result;
	}
	// Delete given node key(key) in AVL tree
	Node * delete_node(Node * root, int key)
	{
		if (root == NULL)
		{
			return root;
		}
		//When deleted nodes are possible in left subtree
		if (key < root->key)
		{
			root->left = this->delete_node(root->left, key);
		}
		//  When deleted nodes are possible in right subtree
		else if (key > root->key)
		{
			root->right = this->delete_node(root->right, key);
		}
		else
		{
			if (root->occurrence > 1)
			{
				root->occurrence--;
				return root;
			}
			Node * temp = NULL;
			//When deleted node is current node (root)
			if ((root->left == NULL) || (root->right == NULL))
			{
				if (root->left != NULL)
				{
					//When left subtree are exists
					temp = root->left;
				}
				else if (root->right != NULL)
				{
					//When left subtree are exists
					temp = root->right;
				}
				if (temp == NULL)
				{
					// When delete leaf node
					// Get deleted node
					temp = root;
					//In this case set the current root node value to zero
					root = NULL;
				}
				else
				{
					// One child case 
					root = temp;
				}
				//free the deleted node
				temp = NULL;
			}
			else
			{
				//When left and right both subtree exists
				// Find inorder successor 
				temp = this->min_key_node(root->right);
				// Set new value to current node
				root->key = temp->key;
				// Delete smallest element in find node
				// Goal to delete leaf node
				root->right = this->delete_node(root->right, temp->key);
			}
		}
		// If the tree had only one node then return 
		if (root == NULL)
		{
			return root;
		}
		// set height of current node 
		root->height = 1 + this->max_height(this->height(root->left), this->height(root->right));
		// get balance factor
		int balance = this->get_balance_factor(root);
		// Transform into a balanced avl  tree 
		// 4 possible situation
		if (balance > 1 && this->get_balance_factor(root->left) >= 0)
		{
			return this->right_rotate(root);
		}
		if (balance > 1 && this->get_balance_factor(root->left) < 0)
		{
			root->left = this->left_rotate(root->left);
			return this->right_rotate(root);
		}
		if (balance < -1 && this->get_balance_factor(root->right) <= 0)
		{
			return this->left_rotate(root);
		}
		if (balance < -1 && this->get_balance_factor(root->right) > 0)
		{
			root->right = this->right_rotate(root->right);
			return this->left_rotate(root);
		}
		return root;
	}
	//Check that whether given key node is exist in given tree
	bool node_exist(Node * root, int key)
	{
		if (root == NULL)
		{
			return false;
		}
		else
		{
			if (root->key == key)
			{
				//When node is exist
				return true;
			}
			return (this->node_exist(root->left, key) || this->node_exist(root->right, key));
		}
	}
	//This is handling the request of deleted node in AVL
	void delete_tree_node(int key)
	{
		if (this->root != NULL && this->node_exist(this->root, key) == true)
		{
			cout << "\n Before Delete node " << key << " element \n";
			this->preorder(this->root);
			this->root = this->delete_node(this->root, key);
			cout << "\n After Delete node " << key << " element \n";
			this->preorder(this->root);
		}
		else
		{
			cout << "\n Deleted node " << key << " is not found \n";
			this->preorder(this->root);
		}
	}
};
int main()
{
	AvlTree obj = AvlTree();
	//add tree node
	obj.root = obj.add_node(obj.root, 12);
	obj.root = obj.add_node(obj.root, 7);
	obj.root = obj.add_node(obj.root, 5);
	obj.root = obj.add_node(obj.root, 19);
	obj.root = obj.add_node(obj.root, 17);
	obj.root = obj.add_node(obj.root, 13);
	obj.root = obj.add_node(obj.root, 11);
	obj.root = obj.add_node(obj.root, 3);
	obj.root = obj.add_node(obj.root, 2);
	obj.root = obj.add_node(obj.root, 7);
	/*
			    Resultant  AVL Tree
			    -----------------

			           12
			          /  \ 
			         /    \
			     (2)7      17
			       / \     / \
			      3   11  13  19
			     / \
			    2   5

			*/
	obj.delete_tree_node(7);
	/*
			   After delete node 7
			    -----------------

			           12
			          /  \ 
			         /    \
			     (1)7      17
			       / \     / \
			      3   11  13  19
			     / \
			    2   5
			*/
	obj.delete_tree_node(11);
	/*
	    After delete node 11
	    -----------------

	             12
	            /  \ 
	           /    \
	          7      17
	         / \     / \
	        3   11  13  19
	       / \
	      2   5

	      //remove node

	             12
	            /  \ 
	           /    \
	          7      17
	         /       / \
	        3       13  19
	       / \
	      2   5

	    //  Balance the AVL tree

	             12
	            /  \ 
	           /    \
	          3      17
	         / \     / \
	        2   7  13  19
	           /
	          5
	  */
	return 0;
	return 0;
}

Output

 Before Delete node 7 element
  12(1)  7(2)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 After Delete node 7 element
  12(1)  7(1)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 Before Delete node 11 element
  12(1)  7(1)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 After Delete node 11 element
  12(1)  3(1)  2(1)  7(1)  5(1)  17(1)  13(1)  19(1)
//Include namespace system
using System;

// C# program
// Avl tree node deletion

//Avl tree node
class Node
{
	public int key;
	public int height;
	public int occurrence;
	public Node left;
	public Node right;
	public Node(int key)
	{
		//Set node value of avl tree
		this.key = key;
		this.height = 1;
		this.occurrence = 1;
		this.left = null;
		this.right = null;
	}
}
class AvlTree
{
	public Node root;
	public AvlTree()
	{
		this.root = null;
	}
	//Get the height of given node
	public int height(Node node)
	{
		if (node == null)
		{
			return 0;
		}
		return node.height;
	}
	//Get the max value of given two numbers
	public int max_height(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	public Node right_rotate(Node node)
	{
		//Get left child node
		Node left_node = node.left;
		//Get left node right subtree
		Node right_subtree = left_node.right;
		//update the left and right subtree 
		left_node.right = node;
		node.left = right_subtree;
		//Change the height of modified node
		node.height = max_height(height(node.left), height(node.right)) + 1;
		left_node.height = max_height(height(left_node.left), height(left_node.right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	public Node left_rotate(Node node)
	{
		// Get right child node
		Node right_node = node.right;
		//Get right node left subtree
		Node left_subtree = right_node.left;
		//update the left and right subtree 
		right_node.left = node;
		node.right = left_subtree;
		//Change the height of modified node
		node.height = max_height(height(node.left), height(node.right)) + 1;
		right_node.height = max_height(height(right_node.left), height(right_node.right)) + 1;
		return right_node;
	}
	// Get the balance factor
	public int get_balance_factor(Node node)
	{
		if (node == null)
		{
			return 0;
		}
		return height(node.left) - height(node.right);
	}
	// Recursively, add a node in AVL tree
	// Duplicate keys (key) are allowed
	public Node add_node(Node node, int key)
	{
		if (node == null)
		{
			//return a new node
			return new Node(key);
		}
		if (key < node.key)
		{
			node.left = add_node(node.left, key);
		}
		else if (key > node.key)
		{
			node.right = add_node(node.right, key);
		}
		else
		{
			//When given key already exists
			node.occurrence = node.occurrence + 1;
			return node;
		}
		// Change the height of current node
		node.height = 1 + max_height(height(node.left), height(node.right));
		//Get balance factor of a node
		int balance_factor = get_balance_factor(node);
		if (balance_factor > 1 && key < node.left.key)
		{
			return right_rotate(node);
		}
		if (balance_factor < -1 && key > node.right.key)
		{
			return left_rotate(node);
		}
		if (balance_factor > 1 && key > node.left.key)
		{
			node.left = left_rotate(node.left);
			return right_rotate(node);
		}
		if (balance_factor < -1 && key < node.right.key)
		{
			node.right = right_rotate(node.right);
			return left_rotate(node);
		}
		return node;
	}
	// Print avl tree in preorder traversal
	public void preorder(Node root)
	{
		if (root != null)
		{
			Console.Write("  " + root.key + "(" + root.occurrence + ")");
			preorder(root.left);
			preorder(root.right);
		}
	}
	//Find the minimum node on left side
	public Node min_key_node(Node node)
	{
		Node result = node;
		while (result.left != null)
		{
			result = result.left;
		}
		return result;
	}
	// Delete given node key(key) in AVL tree
	public Node delete_node(Node root, int key)
	{
		if (root == null)
		{
			return root;
		}
		//When deleted nodes are possible in left subtree
		if (key < root.key)
		{
			root.left = delete_node(root.left, key);
		}
		//  When deleted nodes are possible in right subtree
		else if (key > root.key)
		{
			root.right = delete_node(root.right, key);
		}
		else
		{
			if (root.occurrence > 1)
			{
				root.occurrence--;
				return root;
			}
			Node temp = null;
			//When deleted node is current node (root)
			if ((root.left == null) || (root.right == null))
			{
				if (root.left != null)
				{
					//When left subtree are exists
					temp = root.left;
				}
				else if (root.right != null)
				{
					//When left subtree are exists
					temp = root.right;
				}
				if (temp == null)
				{
					// When delete leaf node
					// Get deleted node
					temp = root;
					//In this case set the current root node value to zero
					root = null;
				}
				else
				{
					// One child case 
					root = temp;
				}
				//free the deleted node
				temp = null;
			}
			else
			{
				//When left and right both subtree exists
				// Find inorder successor 
				temp = min_key_node(root.right);
				// Set new value to current node
				root.key = temp.key;
				// Delete smallest element in find node
				// Goal to delete leaf node
				root.right = delete_node(root.right, temp.key);
			}
		}
		// If the tree had only one node then return 
		if (root == null)
		{
			return root;
		}
		// set height of current node 
		root.height = 1 + max_height(height(root.left), height(root.right));
		// get balance factor
		int balance = get_balance_factor(root);
		// Transform into a balanced avl  tree 
		// 4 possible situation
		if (balance > 1 && get_balance_factor(root.left) >= 0)
		{
			return right_rotate(root);
		}
		if (balance > 1 && get_balance_factor(root.left) < 0)
		{
			root.left = left_rotate(root.left);
			return right_rotate(root);
		}
		if (balance < -1 && get_balance_factor(root.right) <= 0)
		{
			return left_rotate(root);
		}
		if (balance < -1 && get_balance_factor(root.right) > 0)
		{
			root.right = right_rotate(root.right);
			return left_rotate(root);
		}
		return root;
	}
	//Check that whether given key node is exist in given tree
	public Boolean node_exist(Node root, int key)
	{
		if (root == null)
		{
			return false;
		}
		else
		{
			if (root.key == key)
			{
				//When node is exist
				return true;
			}
			return (node_exist(root.left, key) || node_exist(root.right, key));
		}
	}
	//This is handling the request of deleted node in AVL
	public void delete_tree_node(int key)
	{
		if (this.root != null && node_exist(this.root, key) == true)
		{
			Console.Write("\n Before Delete node " + key + " element \n");
			preorder(this.root);
			this.root = delete_node(this.root, key);
			Console.Write("\n After Delete node " + key + " element \n");
			preorder(this.root);
		}
		else
		{
			Console.Write("\n Deleted node " + key + " is not found \n");
			preorder(this.root);
		}
	}
	public static void Main(String[] args)
	{
		AvlTree obj = new AvlTree();
		//add tree node
		obj.root = obj.add_node(obj.root, 12);
		obj.root = obj.add_node(obj.root, 7);
		obj.root = obj.add_node(obj.root, 5);
		obj.root = obj.add_node(obj.root, 19);
		obj.root = obj.add_node(obj.root, 17);
		obj.root = obj.add_node(obj.root, 13);
		obj.root = obj.add_node(obj.root, 11);
		obj.root = obj.add_node(obj.root, 3);
		obj.root = obj.add_node(obj.root, 2);
		obj.root = obj.add_node(obj.root, 7);
		/*
				    Resultant  AVL Tree
				    -----------------

				           12
				          /  \ 
				         /    \
				     (2)7      17
				       / \     / \
				      3   11  13  19
				     / \
				    2   5

				*/
		obj.delete_tree_node(7);
		/*
				   After delete node 7
				    -----------------

				           12
				          /  \ 
				         /    \
				     (1)7      17
				       / \     / \
				      3   11  13  19
				     / \
				    2   5
				*/
		obj.delete_tree_node(11);
		/*
		    After delete node 11
		    -----------------

		             12
		            /  \ 
		           /    \
		          7      17
		         / \     / \
		        3   11  13  19
		       / \
		      2   5

		      //remove node

		             12
		            /  \ 
		           /    \
		          7      17
		         /       / \
		        3       13  19
		       / \
		      2   5

		    //  Balance the AVL tree

		             12
		            /  \ 
		           /    \
		          3      17
		         / \     / \
		        2   7  13  19
		           /
		          5
		  */
		
	}
}

Output

 Before Delete node 7 element
  12(1)  7(2)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 After Delete node 7 element
  12(1)  7(1)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 Before Delete node 11 element
  12(1)  7(1)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 After Delete node 11 element
  12(1)  3(1)  2(1)  7(1)  5(1)  17(1)  13(1)  19(1)
<?php
// Php program
// Avl tree node deletion

//Avl tree node
class Node
{
	public $key;
	public $height;
	public $occurrence;
	public $left;
	public $right;

	function __construct($key)
	{
		//Set node value of avl tree
		$this->key = $key;
		$this->height = 1;
		$this->occurrence = 1;
		$this->left = null;
		$this->right = null;
	}
}
class AvlTree
{
	public $root;

	function __construct()
	{
		$this->root = null;
	}
	//Get the height of given node
	public	function height($node)
	{
		if ($node == null)
		{
			return 0;
		}
		return $node->height;
	}
	//Get the max value of given two numbers
	public	function max_height($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		else
		{
			return $b;
		}
	}
	// Perform the Right rotate operation
	public	function right_rotate($node)
	{
		//Get left child node
		$left_node = $node->left;
		//Get left node right subtree
		$right_subtree = $left_node->right;
		//update the left and right subtree 
		$left_node->right = $node;
		$node->left = $right_subtree;
		//Change the height of modified node
		$node->height = $this->max_height($this->height($node->left), $this->height($node->right)) + 1;
		$left_node->height = $this->max_height($this->height($left_node->left), $this->height($left_node->right)) + 1;
		return $left_node;
	}
	// Perform the Left Rotate operation
	public	function left_rotate($node)
	{
		// Get right child node
		$right_node = $node->right;
		//Get right node left subtree
		$left_subtree = $right_node->left;
		//update the left and right subtree 
		$right_node->left = $node;
		$node->right = $left_subtree;
		//Change the height of modified node
		$node->height = $this->max_height($this->height($node->left), $this->height($node->right)) + 1;
		$right_node->height = $this->max_height($this->height($right_node->left), $this->height($right_node->right)) + 1;
		return $right_node;
	}
	// Get the balance factor
	public	function get_balance_factor($node)
	{
		if ($node == null)
		{
			return 0;
		}
		return $this->height($node->left) - $this->height($node->right);
	}
	// Recursively, add a node in AVL tree
	// Duplicate keys (key) are allowed
	public	function add_node($node, $key)
	{
		if ($node == null)
		{
			//return a new node
			return new Node($key);
		}
		if ($key < $node->key)
		{
			$node->left = $this->add_node($node->left, $key);
		}
		else if ($key > $node->key)
		{
			$node->right = $this->add_node($node->right, $key);
		}
		else
		{
			//When given key already exists
			$node->occurrence = $node->occurrence + 1;
			return $node;
		}
		// Change the height of current node
		$node->height = 1 + $this->max_height($this->height($node->left), $this->height($node->right));
		//Get balance factor of a node
		$balance_factor = $this->get_balance_factor($node);
		if ($balance_factor > 1 && $key < $node->left->key)
		{
			return $this->right_rotate($node);
		}
		if ($balance_factor < -1 && $key > $node->right->key)
		{
			return $this->left_rotate($node);
		}
		if ($balance_factor > 1 && $key > $node->left->key)
		{
			$node->left = $this->left_rotate($node->left);
			return $this->right_rotate($node);
		}
		if ($balance_factor < -1 && $key < $node->right->key)
		{
			$node->right = $this->right_rotate($node->right);
			return $this->left_rotate($node);
		}
		return $node;
	}
	// Print avl tree in preorder traversal
	public	function preorder($root)
	{
		if ($root != null)
		{
			echo "  ". $root->key ."(". $root->occurrence .")";
			$this->preorder($root->left);
			$this->preorder($root->right);
		}
	}
	//Find the minimum node on left side
	public	function min_key_node($node)
	{
		$result = $node;
		while ($result->left != null)
		{
			$result = $result->left;
		}
		return $result;
	}
	// Delete given node key(key) in AVL tree
	public	function delete_node($root, $key)
	{
		if ($root == null)
		{
			return $root;
		}
		//When deleted nodes are possible in left subtree
		if ($key < $root->key)
		{
			$root->left = $this->delete_node($root->left, $key);
		}
		//  When deleted nodes are possible in right subtree
		else if ($key > $root->key)
		{
			$root->right = $this->delete_node($root->right, $key);
		}
		else
		{
			if ($root->occurrence > 1)
			{
				$root->occurrence--;
				return $root;
			}
			$temp = null;
			//When deleted node is current node (root)
			if (($root->left == null) || ($root->right == null))
			{
				if ($root->left != null)
				{
					//When left subtree are exists
					$temp = $root->left;
				}
				else if ($root->right != null)
				{
					//When left subtree are exists
					$temp = $root->right;
				}
				if ($temp == null)
				{
					// When delete leaf node
					// Get deleted node
					$temp = $root;
					//In this case set the current root node value to zero
					$root = null;
				}
				else
				{
					// One child case 
					$root = $temp;
				}
				//free the deleted node
				$temp = null;
			}
			else
			{
				//When left and right both subtree exists
				// Find inorder successor 
				$temp = $this->min_key_node($root->right);
				// Set new value to current node
				$root->key = $temp->key;
				// Delete smallest element in find node
				// Goal to delete leaf node
				$root->right = $this->delete_node($root->right, $temp->key);
			}
		}
		// If the tree had only one node then return 
		if ($root == null)
		{
			return $root;
		}
		// set height of current node 
		$root->height = 1 + $this->max_height($this->height($root->left), $this->height($root->right));
		// get balance factor
		$balance = $this->get_balance_factor($root);
		// Transform into a balanced avl  tree 
		// 4 possible situation
		if ($balance > 1 && $this->get_balance_factor($root->left) >= 0)
		{
			return $this->right_rotate($root);
		}
		if ($balance > 1 && $this->get_balance_factor($root->left) < 0)
		{
			$root->left = $this->left_rotate($root->left);
			return $this->right_rotate($root);
		}
		if ($balance < -1 && $this->get_balance_factor($root->right) <= 0)
		{
			return $this->left_rotate($root);
		}
		if ($balance < -1 && $this->get_balance_factor($root->right) > 0)
		{
			$root->right = $this->right_rotate($root->right);
			return $this->left_rotate($root);
		}
		return $root;
	}
	//Check that whether given key node is exist in given tree
	public	function node_exist($root, $key)
	{
		if ($root == null)
		{
			return false;
		}
		else
		{
			if ($root->key == $key)
			{
				//When node is exist
				return true;
			}
			return ($this->node_exist($root->left, $key) || $this->node_exist($root->right, $key));
		}
	}
	//This is handling the request of deleted node in AVL
	public	function delete_tree_node($key)
	{
		if ($this->root != null && $this->node_exist($this->root, $key) == true)
		{
			echo "\n Before Delete node ". $key ." element \n";
			$this->preorder($this->root);
			$this->root = $this->delete_node($this->root, $key);
			echo "\n After Delete node ". $key ." element \n";
			$this->preorder($this->root);
		}
		else
		{
			echo "\n Deleted node ". $key ." is not found \n";
			$this->preorder($this->root);
		}
	}
}

function main()
{
	$obj = new AvlTree();
	//add tree node
	$obj->root = $obj->add_node($obj->root, 12);
	$obj->root = $obj->add_node($obj->root, 7);
	$obj->root = $obj->add_node($obj->root, 5);
	$obj->root = $obj->add_node($obj->root, 19);
	$obj->root = $obj->add_node($obj->root, 17);
	$obj->root = $obj->add_node($obj->root, 13);
	$obj->root = $obj->add_node($obj->root, 11);
	$obj->root = $obj->add_node($obj->root, 3);
	$obj->root = $obj->add_node($obj->root, 2);
	$obj->root = $obj->add_node($obj->root, 7);
	/*
			    Resultant  AVL Tree
			    -----------------

			           12
			          /  \ 
			         /    \
			     (2)7      17
			       / \     / \
			      3   11  13  19
			     / \
			    2   5

			*/
	$obj->delete_tree_node(7);
	/*
			   After delete node 7
			    -----------------

			           12
			          /  \ 
			         /    \
			     (1)7      17
			       / \     / \
			      3   11  13  19
			     / \
			    2   5
			*/
	$obj->delete_tree_node(11);
	/*
	    After delete node 11
	    -----------------

	             12
	            /  \ 
	           /    \
	          7      17
	         / \     / \
	        3   11  13  19
	       / \
	      2   5

	      //remove node

	             12
	            /  \ 
	           /    \
	          7      17
	         /       / \
	        3       13  19
	       / \
	      2   5

	    //  Balance the AVL tree

	             12
	            /  \ 
	           /    \
	          3      17
	         / \     / \
	        2   7  13  19
	           /
	          5
	  */
}
main();

Output

 Before Delete node 7 element
  12(1)  7(2)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 After Delete node 7 element
  12(1)  7(1)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 Before Delete node 11 element
  12(1)  7(1)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 After Delete node 11 element
  12(1)  3(1)  2(1)  7(1)  5(1)  17(1)  13(1)  19(1)
// Node Js program
// Avl tree node deletion

//Avl tree node
class Node
{
	constructor(key)
	{
		//Set node value of avl tree
		this.key = key;
		this.height = 1;
		this.occurrence = 1;
		this.left = null;
		this.right = null;
	}
}
class AvlTree
{
	constructor()
	{
		this.root = null;
	}
	//Get the height of given node
	height(node)
	{
		if (node == null)
		{
			return 0;
		}
		return node.height;
	}
	//Get the max value of given two numbers
	max_height(a, b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	right_rotate(node)
	{
		//Get left child node
		var left_node = node.left;
		//Get left node right subtree
		var right_subtree = left_node.right;
		//update the left and right subtree 
		left_node.right = node;
		node.left = right_subtree;
		//Change the height of modified node
		node.height = this.max_height(this.height(node.left), this.height(node.right)) + 1;
		left_node.height = this.max_height(this.height(left_node.left), this.height(left_node.right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	left_rotate(node)
	{
		// Get right child node
		var right_node = node.right;
		//Get right node left subtree
		var left_subtree = right_node.left;
		//update the left and right subtree 
		right_node.left = node;
		node.right = left_subtree;
		//Change the height of modified node
		node.height = this.max_height(this.height(node.left), this.height(node.right)) + 1;
		right_node.height = this.max_height(this.height(right_node.left), this.height(right_node.right)) + 1;
		return right_node;
	}
	// Get the balance factor
	get_balance_factor(node)
	{
		if (node == null)
		{
			return 0;
		}
		return this.height(node.left) - this.height(node.right);
	}
	// Recursively, add a node in AVL tree
	// Duplicate keys (key) are allowed
	add_node(node, key)
	{
		if (node == null)
		{
			//return a new node
			return new Node(key);
		}
		if (key < node.key)
		{
			node.left = this.add_node(node.left, key);
		}
		else if (key > node.key)
		{
			node.right = this.add_node(node.right, key);
		}
		else
		{
			//When given key already exists
			node.occurrence = node.occurrence + 1;
			return node;
		}
		// Change the height of current node
		node.height = 1 + this.max_height(this.height(node.left), this.height(node.right));
		//Get balance factor of a node
		var balance_factor = this.get_balance_factor(node);
		if (balance_factor > 1 && key < node.left.key)
		{
			return this.right_rotate(node);
		}
		if (balance_factor < -1 && key > node.right.key)
		{
			return this.left_rotate(node);
		}
		if (balance_factor > 1 && key > node.left.key)
		{
			node.left = this.left_rotate(node.left);
			return this.right_rotate(node);
		}
		if (balance_factor < -1 && key < node.right.key)
		{
			node.right = this.right_rotate(node.right);
			return this.left_rotate(node);
		}
		return node;
	}
	// Print avl tree in preorder traversal
	preorder(root)
	{
		if (root != null)
		{
			process.stdout.write("  " + root.key + "(" + root.occurrence + ")");
			this.preorder(root.left);
			this.preorder(root.right);
		}
	}
	//Find the minimum node on left side
	min_key_node(node)
	{
		var result = node;
		while (result.left != null)
		{
			result = result.left;
		}
		return result;
	}
	// Delete given node key(key) in AVL tree
	delete_node(root, key)
	{
		if (root == null)
		{
			return root;
		}
		//When deleted nodes are possible in left subtree
		if (key < root.key)
		{
			root.left = this.delete_node(root.left, key);
		}
		//  When deleted nodes are possible in right subtree
		else if (key > root.key)
		{
			root.right = this.delete_node(root.right, key);
		}
		else
		{
			if (root.occurrence > 1)
			{
				root.occurrence--;
				return root;
			}
			var temp = null;
			//When deleted node is current node (root)
			if ((root.left == null) || (root.right == null))
			{
				if (root.left != null)
				{
					//When left subtree are exists
					temp = root.left;
				}
				else if (root.right != null)
				{
					//When left subtree are exists
					temp = root.right;
				}
				if (temp == null)
				{
					// When delete leaf node
					// Get deleted node
					temp = root;
					//In this case set the current root node value to zero
					root = null;
				}
				else
				{
					// One child case 
					root = temp;
				}
				//free the deleted node
				temp = null;
			}
			else
			{
				//When left and right both subtree exists
				// Find inorder successor 
				temp = this.min_key_node(root.right);
				// Set new value to current node
				root.key = temp.key;
				// Delete smallest element in find node
				// Goal to delete leaf node
				root.right = this.delete_node(root.right, temp.key);
			}
		}
		// If the tree had only one node then return 
		if (root == null)
		{
			return root;
		}
		// set height of current node 
		root.height = 1 + this.max_height(this.height(root.left), this.height(root.right));
		// get balance factor
		var balance = this.get_balance_factor(root);
		// Transform into a balanced avl  tree 
		// 4 possible situation
		if (balance > 1 && this.get_balance_factor(root.left) >= 0)
		{
			return this.right_rotate(root);
		}
		if (balance > 1 && this.get_balance_factor(root.left) < 0)
		{
			root.left = this.left_rotate(root.left);
			return this.right_rotate(root);
		}
		if (balance < -1 && this.get_balance_factor(root.right) <= 0)
		{
			return this.left_rotate(root);
		}
		if (balance < -1 && this.get_balance_factor(root.right) > 0)
		{
			root.right = this.right_rotate(root.right);
			return this.left_rotate(root);
		}
		return root;
	}
	//Check that whether given key node is exist in given tree
	node_exist(root, key)
	{
		if (root == null)
		{
			return false;
		}
		else
		{
			if (root.key == key)
			{
				//When node is exist
				return true;
			}
			return (this.node_exist(root.left, key) || this.node_exist(root.right, key));
		}
	}
	//This is handling the request of deleted node in AVL
	delete_tree_node(key)
	{
		if (this.root != null && this.node_exist(this.root, key) == true)
		{
			process.stdout.write("\n Before Delete node " + key + " element \n");
			this.preorder(this.root);
			this.root = this.delete_node(this.root, key);
			process.stdout.write("\n After Delete node " + key + " element \n");
			this.preorder(this.root);
		}
		else
		{
			process.stdout.write("\n Deleted node " + key + " is not found \n");
			this.preorder(this.root);
		}
	}
}

function main()
{
	var obj = new AvlTree();
	//add tree node
	obj.root = obj.add_node(obj.root, 12);
	obj.root = obj.add_node(obj.root, 7);
	obj.root = obj.add_node(obj.root, 5);
	obj.root = obj.add_node(obj.root, 19);
	obj.root = obj.add_node(obj.root, 17);
	obj.root = obj.add_node(obj.root, 13);
	obj.root = obj.add_node(obj.root, 11);
	obj.root = obj.add_node(obj.root, 3);
	obj.root = obj.add_node(obj.root, 2);
	obj.root = obj.add_node(obj.root, 7);
	/*
			    Resultant  AVL Tree
			    -----------------

			           12
			          /  \ 
			         /    \
			     (2)7      17
			       / \     / \
			      3   11  13  19
			     / \
			    2   5

			*/
	obj.delete_tree_node(7);
	/*
			   After delete node 7
			    -----------------

			           12
			          /  \ 
			         /    \
			     (1)7      17
			       / \     / \
			      3   11  13  19
			     / \
			    2   5
			*/
	obj.delete_tree_node(11);
	/*
	    After delete node 11
	    -----------------

	             12
	            /  \ 
	           /    \
	          7      17
	         / \     / \
	        3   11  13  19
	       / \
	      2   5

	      //remove node

	             12
	            /  \ 
	           /    \
	          7      17
	         /       / \
	        3       13  19
	       / \
	      2   5

	    //  Balance the AVL tree

	             12
	            /  \ 
	           /    \
	          3      17
	         / \     / \
	        2   7  13  19
	           /
	          5
	  */
	
}
main();

Output

 Before Delete node 7 element
  12(1)  7(2)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 After Delete node 7 element
  12(1)  7(1)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 Before Delete node 11 element
  12(1)  7(1)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 After Delete node 11 element
  12(1)  3(1)  2(1)  7(1)  5(1)  17(1)  13(1)  19(1)
#  Python 3 program
#  Avl tree node deletion

# Avl tree node
class Node :
	
	def __init__(self, key) :
		# Set node value of avl tree
		self.key = key
		self.height = 1
		self.occurrence = 1
		self.left = None
		self.right = None
	

class AvlTree :
	
	def __init__(self) :
		self.root = None
	
	# Get the height of given node
	def height(self, node) :
		if (node == None) :
			return 0
		
		return node.height
	
	# Get the max value of given two numbers
	def max_height(self, a, b) :
		if (a > b) :
			return a
		else :
			return b
		
	
	#  Perform the Right rotate operation
	def right_rotate(self, node) :
		# Get left child node
		left_node = node.left
		# Get left node right subtree
		right_subtree = left_node.right
		# update the left and right subtree 
		left_node.right = node
		node.left = right_subtree
		# Change the height of modified node
		node.height = self.max_height(self.height(node.left), self.height(node.right)) + 1
		left_node.height = self.max_height(self.height(left_node.left), self.height(left_node.right)) + 1
		return left_node
	
	#  Perform the Left Rotate operation
	def left_rotate(self, node) :
		#  Get right child node
		right_node = node.right
		# Get right node left subtree
		left_subtree = right_node.left
		# update the left and right subtree 
		right_node.left = node
		node.right = left_subtree
		# Change the height of modified node
		node.height = self.max_height(self.height(node.left), self.height(node.right)) + 1
		right_node.height = self.max_height(self.height(right_node.left), self.height(right_node.right)) + 1
		return right_node
	
	#  Get the balance factor
	def get_balance_factor(self, node) :
		if (node == None) :
			return 0
		
		return self.height(node.left) - self.height(node.right)
	
	#  Recursively, add a node in AVL tree
	#  Duplicate keys (key) are allowed
	def add_node(self, node, key) :
		if (node == None) :
			# return a new node
			return Node(key)
		
		if (key < node.key) :
			node.left = self.add_node(node.left, key)
		
		elif(key > node.key) :
			node.right = self.add_node(node.right, key)
		else :
			# When given key already exists
			node.occurrence = node.occurrence + 1
			return node
		
		#  Change the height of current node
		node.height = 1 + self.max_height(self.height(node.left), self.height(node.right))
		# Get balance factor of a node
		balance_factor = self.get_balance_factor(node)
		if (balance_factor > 1 and key < node.left.key) :
			return self.right_rotate(node)
		
		if (balance_factor < -1 and key > node.right.key) :
			return self.left_rotate(node)
		
		if (balance_factor > 1 and key > node.left.key) :
			node.left = self.left_rotate(node.left)
			return self.right_rotate(node)
		
		if (balance_factor < -1 and key < node.right.key) :
			node.right = self.right_rotate(node.right)
			return self.left_rotate(node)
		
		return node
	
	#  Print avl tree in preorder traversal
	def preorder(self, root) :
		if (root != None) :
			print(" {0}({1}) ".format(root.key , root.occurrence ), end = "")
			self.preorder(root.left)
			self.preorder(root.right)
		
	
	# Find the minimum node on left side
	def min_key_node(self, node) :
		result = node
		while (result.left != None) :
			result = result.left
		
		return result
	
	#  Delete given node key(key) in AVL tree
	def delete_node(self, root, key) :
		if (root == None) :
			return root
		
		# When deleted nodes are possible in left subtree
		if (key < root.key) :
			root.left = self.delete_node(root.left, key)
		
		#   When deleted nodes are possible in right subtree
		elif(key > root.key) :
			root.right = self.delete_node(root.right, key)
		else :
			if (root.occurrence > 1) :
				root.occurrence -= 1
				return root
			
			temp = None
			# When deleted node is current node (root)
			if ((root.left == None) or(root.right == None)) :
				if (root.left != None) :
					# When left subtree are exists
					temp = root.left
				
				elif(root.right != None) :
					# When left subtree are exists
					temp = root.right
				
				if (temp == None) :
					#  When delete leaf node
					#  Get deleted node
					temp = root
					# In this case set the current root node value to zero
					root = None
				else :
					#  One child case 
					root = temp
				
				# free the deleted node
				temp = None
			else :
				# When left and right both subtree exists
				#  Find inorder successor 
				temp = self.min_key_node(root.right)
				#  Set new value to current node
				root.key = temp.key
				#  Delete smallest element in find node
				#  Goal to delete leaf node
				root.right = self.delete_node(root.right, temp.key)
			
		
		#  If the tree had only one node then return 
		if (root == None) :
			return root
		
		#  set height of current node 
		root.height = 1 + self.max_height(self.height(root.left), self.height(root.right))
		#  get balance factor
		balance = self.get_balance_factor(root)
		#  Transform into a balanced avl  tree 
		#  4 possible situation
		if (balance > 1 and self.get_balance_factor(root.left) >= 0) :
			return self.right_rotate(root)
		
		if (balance > 1 and self.get_balance_factor(root.left) < 0) :
			root.left = self.left_rotate(root.left)
			return self.right_rotate(root)
		
		if (balance < -1 and self.get_balance_factor(root.right) <= 0) :
			return self.left_rotate(root)
		
		if (balance < -1 and self.get_balance_factor(root.right) > 0) :
			root.right = self.right_rotate(root.right)
			return self.left_rotate(root)
		
		return root
	
	# Check that whether given key node is exist in given tree
	def node_exist(self, root, key) :
		if (root == None) :
			return False
		else :
			if (root.key == key) :
				# When node is exist
				return True
			
			return (self.node_exist(root.left, key) or self.node_exist(root.right, key))
		
	
	# This is handling the request of deleted node in AVL
	def delete_tree_node(self, key) :
		if (self.root != None and self.node_exist(self.root, key) == True) :
			print("\n Before Delete node ", key ," element \n", end = "")
			self.preorder(self.root)
			self.root = self.delete_node(self.root, key)
			print("\n After Delete node ", key ," element \n", end = "")
			self.preorder(self.root)
		else :
			print("\n Deleted node ", key ," is not found \n", end = "")
			self.preorder(self.root)
		
	

def main() :
	obj = AvlTree()
	# add tree node
	obj.root = obj.add_node(obj.root, 12)
	obj.root = obj.add_node(obj.root, 7)
	obj.root = obj.add_node(obj.root, 5)
	obj.root = obj.add_node(obj.root, 19)
	obj.root = obj.add_node(obj.root, 17)
	obj.root = obj.add_node(obj.root, 13)
	obj.root = obj.add_node(obj.root, 11)
	obj.root = obj.add_node(obj.root, 3)
	obj.root = obj.add_node(obj.root, 2)
	obj.root = obj.add_node(obj.root, 7)
	# 
	# 		    Resultant  AVL Tree
	# 		    -----------------
	# 		           12
	# 		          /  \ 
	# 		         /    \
	# 		     (2)7      17
	# 		       / \     / \
	# 		      3   11  13  19
	# 		     / \
	# 		    2   5
	# 		
	
	obj.delete_tree_node(7)
	# 
	# 		   After delete node 7
	# 		    -----------------
	# 		           12
	# 		          /  \ 
	# 		         /    \
	# 		     (1)7      17
	# 		       / \     / \
	# 		      3   11  13  19
	# 		     / \
	# 		    2   5
	# 		
	
	obj.delete_tree_node(11)
	# 
	#     After delete node 11
	#     -----------------
	#              12
	#             /  \ 
	#            /    \
	#           7      17
	#          / \     / \
	#         3   11  13  19
	#        / \
	#       2   5
	#       //remove node
	#              12
	#             /  \ 
	#            /    \
	#           7      17
	#          /       / \
	#         3       13  19
	#        / \
	#       2   5
	#     //  Balance the AVL tree
	#              12
	#             /  \ 
	#            /    \
	#           3      17
	#          / \     / \
	#         2   7  13  19
	#            /
	#           5
	#   
	
	return 0

if __name__ == "__main__": main()

Output

 Before Delete node  7  element
 12(1)  7(2)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 After Delete node  7  element
 12(1)  7(1)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 Before Delete node  11  element
 12(1)  7(1)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 After Delete node  11  element
 12(1)  3(1)  2(1)  7(1)  5(1)  17(1)  13(1)  19(1)
#  Ruby program
#  Avl tree node deletion

# Avl tree node
class Node 

	# Define the accessor and reader of class Node  
	attr_reader :key, :height, :occurrence, :left, :right
	attr_accessor :key, :height, :occurrence, :left, :right


	
	def initialize(key)
	
		# Set node value of avl tree
		self.key = key
		self.height = 1
		self.occurrence = 1
		self.left = nil
		self.right = nil
	end
end
class AvlTree 

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


	
	def initialize()
	
		self.root = nil
	end
	# Get the height of given node
	def height(node)
	
		if (node == nil)
		
			return 0
		end
		return node.height
	end
	# Get the max value of given two numbers
	def max_height(a, b)
	
		if (a > b)
		
			return a
		else
		
			return b
		end
	end
	#  Perform the Right rotate operation
	def right_rotate(node)
	
		# Get left child node
		left_node = node.left
		# Get left node right subtree
		right_subtree = left_node.right
		# update the left and right subtree 
		left_node.right = node
		node.left = right_subtree
		# Change the height of modified node
		node.height = self.max_height(self.height(node.left), self.height(node.right)) + 1
		left_node.height = self.max_height(self.height(left_node.left), self.height(left_node.right)) + 1
		return left_node
	end
	#  Perform the Left Rotate operation
	def left_rotate(node)
	
		#  Get right child node
		right_node = node.right
		# Get right node left subtree
		left_subtree = right_node.left
		# update the left and right subtree 
		right_node.left = node
		node.right = left_subtree
		# Change the height of modified node
		node.height = self.max_height(self.height(node.left), self.height(node.right)) + 1
		right_node.height = self.max_height(self.height(right_node.left), self.height(right_node.right)) + 1
		return right_node
	end
	#  Get the balance factor
	def get_balance_factor(node)
	
		if (node == nil)
		
			return 0
		end
		return self.height(node.left) - self.height(node.right)
	end
	#  Recursively, add a node in AVL tree
	#  Duplicate keys (key) are allowed
	def add_node(node, key)
	
		if (node == nil)
		
			# return a new node
			return Node.new(key)
		end
		if (key < node.key)
		
			node.left = self.add_node(node.left, key)
		elsif(key > node.key)
		
			node.right = self.add_node(node.right, key)
		else
		
			# When given key already exists
			node.occurrence = node.occurrence + 1
			return node
		end
		#  Change the height of current node
		node.height = 1 + self.max_height(self.height(node.left), self.height(node.right))
		# Get balance factor of a node
		balance_factor = self.get_balance_factor(node)
		if (balance_factor > 1 && key < node.left.key)
		
			return self.right_rotate(node)
		end
		if (balance_factor < -1 && key > node.right.key)
		
			return self.left_rotate(node)
		end
		if (balance_factor > 1 && key > node.left.key)
		
			node.left = self.left_rotate(node.left)
			return self.right_rotate(node)
		end
		if (balance_factor < -1 && key < node.right.key)
		
			node.right = self.right_rotate(node.right)
			return self.left_rotate(node)
		end
		return node
	end
	#  Print avl tree in preorder traversal
	def preorder(root)
	
		if (root != nil)
		
			print("  ", root.key ,"(", root.occurrence ,")")
			self.preorder(root.left)
			self.preorder(root.right)
		end
	end
	# Find the minimum node on left side
	def min_key_node(node)
	
		result = node
		while (result.left != nil)
		
			result = result.left
		end
		return result
	end
	#  Delete given node key(key) in AVL tree
	def delete_node(root, key)
	
		if (root == nil)
		
			return root
		end
		# When deleted nodes are possible in left subtree
		if (key < root.key)
			root.left = self.delete_node(root.left, key)
		#   When deleted nodes are possible in right subtree
		elsif(key > root.key)
		
			root.right = self.delete_node(root.right, key)
		else
		
			if (root.occurrence > 1)
			
				root.occurrence -= 1
				return root
			end
			temp = nil
			# When deleted node is current node (root)
			if ((root.left == nil) || (root.right == nil))
			
				if (root.left != nil)
				
					# When left subtree are exists
					temp = root.left
				elsif(root.right != nil)
				
					# When left subtree are exists
					temp = root.right
				end
				if (temp == nil)
				
					#  When delete leaf node
					#  Get deleted node
					temp = root
					# In this case set the current root node value to zero
					root = nil
				else
				
					#  One child case 
					root = temp
				end
				# free the deleted node
				temp = nil
			else
			
				# When left and right both subtree exists
				#  Find inorder successor 
				temp = self.min_key_node(root.right)
				#  Set new value to current node
				root.key = temp.key
				#  Delete smallest element in find node
				#  Goal to delete leaf node
				root.right = self.delete_node(root.right, temp.key)
			end
		end
		#  If the tree had only one node then return 
		if (root == nil)
		
			return root
		end
		#  set height of current node 
		root.height = 1 + self.max_height(self.height(root.left), self.height(root.right))
		#  get balance factor
		balance = self.get_balance_factor(root)
		#  Transform into a balanced avl  tree 
		#  4 possible situation
		if (balance > 1 && self.get_balance_factor(root.left) >= 0)
		
			return self.right_rotate(root)
		end
		if (balance > 1 && self.get_balance_factor(root.left) < 0)
		
			root.left = self.left_rotate(root.left)
			return self.right_rotate(root)
		end
		if (balance < -1 && self.get_balance_factor(root.right) <= 0)
		
			return self.left_rotate(root)
		end
		if (balance < -1 && self.get_balance_factor(root.right) > 0)
		
			root.right = self.right_rotate(root.right)
			return self.left_rotate(root)
		end
		return root
	end
	# Check that whether given key node is exist in given tree
	def node_exist(root, key)
	
		if (root == nil)
		
			return false
		else
		
			if (root.key == key)
			
				# When node is exist
				return true
			end
			return (self.node_exist(root.left, key) || self.node_exist(root.right, key))
		end
	end
	# This is handling the request of deleted node in AVL
	def delete_tree_node(key)
	
		if (self.root != nil && self.node_exist(self.root, key) == true)
		
			print("\n Before Delete node ", key ," element \n")
			self.preorder(self.root)
			self.root = self.delete_node(self.root, key)
			print("\n After Delete node ", key ," element \n")
			self.preorder(self.root)
		else
		
			print("\n Deleted node ", key ," is not found \n")
			self.preorder(self.root)
		end
	end
end
def main()

	obj = AvlTree.new()
	# add tree node
	obj.root = obj.add_node(obj.root, 12)
	obj.root = obj.add_node(obj.root, 7)
	obj.root = obj.add_node(obj.root, 5)
	obj.root = obj.add_node(obj.root, 19)
	obj.root = obj.add_node(obj.root, 17)
	obj.root = obj.add_node(obj.root, 13)
	obj.root = obj.add_node(obj.root, 11)
	obj.root = obj.add_node(obj.root, 3)
	obj.root = obj.add_node(obj.root, 2)
	obj.root = obj.add_node(obj.root, 7)
	# 
	# 		    Resultant  AVL Tree
	# 		    -----------------
	# 		           12
	# 		          /  \ 
	# 		         /    \
	# 		     (2)7      17
	# 		       / \     / \
	# 		      3   11  13  19
	# 		     / \
	# 		    2   5
	# 		
	
	obj.delete_tree_node(7)
	# 
	# 		   After delete node 7
	# 		    -----------------
	# 		           12
	# 		          /  \ 
	# 		         /    \
	# 		     (1)7      17
	# 		       / \     / \
	# 		      3   11  13  19
	# 		     / \
	# 		    2   5
	# 		
	
	obj.delete_tree_node(11)
	# 
	#     After delete node 11
	#     -----------------
	#              12
	#             /  \ 
	#            /    \
	#           7      17
	#          / \     / \
	#         3   11  13  19
	#        / \
	#       2   5
	#       //remove node
	#              12
	#             /  \ 
	#            /    \
	#           7      17
	#          /       / \
	#         3       13  19
	#        / \
	#       2   5
	#     //  Balance the AVL tree
	#              12
	#             /  \ 
	#            /    \
	#           3      17
	#          / \     / \
	#         2   7  13  19
	#            /
	#           5
	#   
end
main()

Output

 Before Delete node 7 element 
  12(1)  7(2)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 After Delete node 7 element 
  12(1)  7(1)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 Before Delete node 11 element 
  12(1)  7(1)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 After Delete node 11 element 
  12(1)  3(1)  2(1)  7(1)  5(1)  17(1)  13(1)  19(1)
// Scala program
// Avl tree node deletion
//Avl tree node
class Node(var key: Int,
	var height: Int,
		var occurrence: Int,
			var left: Node,
				var right: Node)
{
	def this(key: Int)
	{
		this(key, 1, 1, null, null);
	}
}
class AvlTree(var root: Node)
{
	def this()
	{
		this(null);
	}
	//Get the height of given node
	def height(node: Node): Int = {
		if (node == null)
		{
			return 0;
		}
		return node.height;
	}
	//Get the max value of given two numbers
	def max_height(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	def right_rotate(node: Node): Node = {
		//Get left child node
		var left_node: Node = node.left;
		//Get left node right subtree
		var right_subtree: Node = left_node.right;
		//update the left and right subtree 
		left_node.right = node;
		node.left = right_subtree;
		//Change the height of modified node
		node.height = max_height(height(node.left), height(node.right)) + 1;
		left_node.height = max_height(height(left_node.left), height(left_node.right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	def left_rotate(node: Node): Node = {
		// Get right child node
		var right_node: Node = node.right;
		//Get right node left subtree
		var left_subtree: Node = right_node.left;
		//update the left and right subtree 
		right_node.left = node;
		node.right = left_subtree;
		//Change the height of modified node
		node.height = max_height(height(node.left), height(node.right)) + 1;
		right_node.height = max_height(height(right_node.left), height(right_node.right)) + 1;
		return right_node;
	}
	// Get the balance factor
	def get_balance_factor(node: Node): Int = {
		if (node == null)
		{
			return 0;
		}
		return height(node.left) - height(node.right);
	}
	// Recursively, add a node in AVL tree
	// Duplicate keys (key) are allowed
	def add_node(node: Node, key: Int): Node = {
		if (node == null)
		{
			//return a new node
			return new Node(key);
		}
		if (key < node.key)
		{
			node.left = add_node(node.left, key);
		}
		else if (key > node.key)
		{
			node.right = add_node(node.right, key);
		}
		else
		{
			//When given key already exists
			node.occurrence = node.occurrence + 1;
			return node;
		}
		// Change the height of current node
		node.height = 1 + max_height(height(node.left), height(node.right));
		//Get balance factor of a node
		var balance_factor: Int = get_balance_factor(node);
		if (balance_factor > 1 && key < node.left.key)
		{
			return right_rotate(node);
		}
		if (balance_factor < -1 && key > node.right.key)
		{
			return left_rotate(node);
		}
		if (balance_factor > 1 && key > node.left.key)
		{
			node.left = left_rotate(node.left);
			return right_rotate(node);
		}
		if (balance_factor < -1 && key < node.right.key)
		{
			node.right = right_rotate(node.right);
			return left_rotate(node);
		}
		return node;
	}
	// Print avl tree in preorder traversal
	def preorder(root: Node): Unit = {
		if (root != null)
		{
			print("  " + root.key + "(" + root.occurrence + ")");
			preorder(root.left);
			preorder(root.right);
		}
	}
	//Find the minimum node on left side
	def min_key_node(node: Node): Node = {
		var result: Node = node;
		while (result.left != null)
		{
			result = result.left;
		}
		return result;
	}
	// Delete given node key(data) in AVL tree
	def delete_node(head: Node, key: Int): Node = {
      	var root = head;
		if (root == null)
		{
			return root;
		}
		//When deleted nodes are possible in left subtree
		if (key < root.key)
		{
			root.left = delete_node(root.left, key);
		}
		//  When deleted nodes are possible in right subtree
		else if (key > root.key)
		{
			root.right = delete_node(root.right, key);
		}
		else
		{
			if (root.occurrence > 1)
			{
				root.occurrence -= 1;
				return root;
			}
			var temp: Node = null;
			//When deleted node is current node (root)
			if ((root.left == null) || (root.right == null))
			{
				if (root.left != null)
				{
					//When left subtree are exists
					temp = root.left;
				}
				else if (root.right != null)
				{
					//When left subtree are exists
					temp = root.right;
				}
				if (temp == null)
				{
					// When delete leaf node
					// Get deleted node
					temp = root;
					//In this case set the current root node value to zero
					root = null;
				}
				else
				{
					// One child case 
					root = temp;
				}
				//free the deleted node
				temp = null;
			}
			else
			{
				//When left and right both subtree exists
				// Find inorder successor 
				temp = min_key_node(root.right);
				// Set new value to current node
				root.key = temp.key;
				// Delete smallest element in find node
				// Goal to delete leaf node
				root.right = delete_node(root.right, temp.key);
			}
		}
		// If the tree had only one node then return 
		if (root == null)
		{
			return root;
		}
		// set height of current node 
		root.height = 1 + max_height(height(root.left), height(root.right));
		// get balance factor
		var balance: Int = get_balance_factor(root);
		// Transform into a balanced avl  tree 
		// 4 possible situation
		if (balance > 1 && get_balance_factor(root.left) >= 0)
		{
			return right_rotate(root);
		}
		if (balance > 1 && get_balance_factor(root.left) < 0)
		{
			root.left = left_rotate(root.left);
			return right_rotate(root);
		}
		if (balance < -1 && get_balance_factor(root.right) <= 0)
		{
			return left_rotate(root);
		}
		if (balance < -1 && get_balance_factor(root.right) > 0)
		{
			root.right = right_rotate(root.right);
			return left_rotate(root);
		}
		return root;
	}
	//Check that whether given key node is exist in given tree
	def node_exist(root: Node, key: Int): Boolean = {
		if (root == null)
		{
			return false;
		}
		else
		{
			if (root.key == key)
			{
				//When node is exist
				return true;
			}
			return (node_exist(root.left, key) || node_exist(root.right, key));
		}
	}
	//This is handling the request of deleted node in AVL
	def delete_tree_node(key: Int): Unit = {
		if (this.root != null && node_exist(this.root, key) == true)
		{
			print("\n Before Delete node " + key + " element \n");
			preorder(this.root);
			this.root = delete_node(this.root, key);
			print("\n After Delete node " + key + " element \n");
			preorder(this.root);
		}
		else
		{
			print("\n Deleted node " + key + " is not found \n");
			preorder(this.root);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: AvlTree = new AvlTree();
		//add tree node
		obj.root = obj.add_node(obj.root, 12);
		obj.root = obj.add_node(obj.root, 7);
		obj.root = obj.add_node(obj.root, 5);
		obj.root = obj.add_node(obj.root, 19);
		obj.root = obj.add_node(obj.root, 17);
		obj.root = obj.add_node(obj.root, 13);
		obj.root = obj.add_node(obj.root, 11);
		obj.root = obj.add_node(obj.root, 3);
		obj.root = obj.add_node(obj.root, 2);
		obj.root = obj.add_node(obj.root, 7);
		/*
				    Resultant  AVL Tree
				    -----------------

				           12
				          /  \ 
				         /    \
				     (2)7      17
				       / \     / \
				      3   11  13  19
				     / \
				    2   5

				*/
		obj.delete_tree_node(7);
		/*
				   After delete node 7
				    -----------------

				           12
				          /  \ 
				         /    \
				     (1)7      17
				       / \     / \
				      3   11  13  19
				     / \
				    2   5
				*/
		obj.delete_tree_node(11);
		/*
		    After delete node 11
		    -----------------

		             12
		            /  \ 
		           /    \
		          7      17
		         / \     / \
		        3   11  13  19
		       / \
		      2   5

		      //remove node

		             12
		            /  \ 
		           /    \
		          7      17
		         /       / \
		        3       13  19
		       / \
		      2   5

		    //  Balance the AVL tree

		             12
		            /  \ 
		           /    \
		          3      17
		         / \     / \
		        2   7  13  19
		           /
		          5
		  */
	}
}

Output

 Before Delete node 7 element
  12(1)  7(2)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 After Delete node 7 element
  12(1)  7(1)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 Before Delete node 11 element
  12(1)  7(1)  3(1)  2(1)  5(1)  11(1)  17(1)  13(1)  19(1)
 After Delete node 11 element
  12(1)  3(1)  2(1)  7(1)  5(1)  17(1)  13(1)  19(1)
// Swift program
// Avl tree node deletion

//Avl tree node
class Node
{
	var key: Int;
	var height: Int;
	var occurrence: Int;
	var left: Node? ;
	var right: Node? ;
	init(_ key: Int)
	{
		//Set node value of avl tree
		self.key = key;
		self.height = 1;
		self.occurrence = 1;
		self.left = nil;
		self.right = nil;
	}
}
class AvlTree
{
	var root: Node? ;
	init()
	{
		self.root = nil;
	}
	//Get the height of given node
	func height(_ node: Node? ) -> Int
	{
		if (node == nil)
		{
			return 0;
		}
		return node!.height;
	}
	//Get the max value of given two numbers
	func max_height(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	func right_rotate(_ node: Node? ) -> Node?
	{
		//Get left child node
		let left_node: Node? = node!.left;
		//Get left node right subtree
		let right_subtree: Node? = left_node!.right;
		//update the left and right subtree 
		left_node!.right = node;node!.left = right_subtree;
		//Change the height of modified node
		node!.height = self.max_height(self.height(node!.left), self.height(node!.right)) + 1;left_node!.height = self.max_height(self.height(left_node!.left), self.height(left_node!.right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	func left_rotate(_ node: Node? ) -> Node?
	{
		// Get right child node
		let right_node: Node? = node!.right;
		//Get right node left subtree
		let left_subtree: Node? = right_node!.left;
		//update the left and right subtree 
		right_node!.left = node;node!.right = left_subtree;
		//Change the height of modified node
		node!.height = self.max_height(self.height(node!.left), self.height(node!.right)) + 1;right_node!.height = self.max_height(self.height(right_node!.left), self.height(right_node!.right)) + 1;
		return right_node;
	}
	// Get the balance factor
	func get_balance_factor(_ node: Node? ) -> Int
	{
		if (node == nil)
		{
			return 0;
		}
		return self.height(node!.left) - self.height(node!.right);
	}
	// Recursively, add a node in AVL tree
	// Duplicate keys (key) are allowed
	func add_node(_ node: Node? , _ key : Int) -> Node?
	{
		if (node == nil)
		{
			//return a new node
			return Node(key);
		}
		if (key < node!.key)
		{
			node!.left = self.add_node(node!.left, key);
		}
		else if (key > node!.key)
		{
			node!.right = self.add_node(node!.right, key);
		}
		else
		{
			//When given key already exists
			node!.occurrence = node!.occurrence + 1;
			return node;
		}
		// Change the height of current node
		node!.height = 1 + self.max_height(self.height(node!.left), self.height(node!.right));
		//Get balance factor of a node
		let balance_factor: Int = self.get_balance_factor(node);
		if (balance_factor > 1 && key < node!.left!.key)
		{
			return self.right_rotate(node);
		}
		if (balance_factor < -1 && key > node!.right!.key)
		{
			return self.left_rotate(node);
		}
		if (balance_factor > 1 && key > node!.left!.key)
		{
			node!.left = self.left_rotate(node!.left);
			return self.right_rotate(node);
		}
		if (balance_factor < -1 && key < node!.right!.key)
		{
			node!.right = self.right_rotate(node!.right);
			return self.left_rotate(node);
		}
		return node;
	}
	// Print avl tree in preorder traversal
	func preorder(_ root: Node? )
	{
		if (root != nil)
		{
			print(" \(root!.key)(\(root!.occurrence))", terminator: "");
			self.preorder(root!.left);
			self.preorder(root!.right);
		}
	}
	//Find the minimum node on left side
	func min_key_node(_ node: Node? ) -> Node?
	{
		var result: Node? = node;
		while (result!.left != nil)
		{
			result = result!.left;
		}
		return result;
	}
	// Delete given node key(key) in AVL tree
	func delete_node(_ head: Node? , _ key : Int) -> Node?
	{
      	var root = head;
		if (root == nil)
		{
			return root;
		}
		//When deleted nodes are possible in left subtree
		if (key < root!.key)
		{
			root!.left = self.delete_node(root!.left, key);
		}
		//  When deleted nodes are possible in right subtree
		else if (key > root!.key)
		{
			root!.right = self.delete_node(root!.right, key);
		}
		else
		{
			if (root!.occurrence > 1)
			{
				root!.occurrence -= 1;
				return root;
			}
			var temp: Node? = nil;
			//When deleted node is current node (root)
			if ((root!.left == nil) || (root!.right == nil))
			{
				if (root!.left != nil)
				{
					//When left subtree are exists
					temp = root!.left;
				}
				else if (root!.right != nil)
				{
					//When left subtree are exists
					temp = root!.right;
				}
				if (temp == nil)
				{
					// When delete leaf node
					// Get deleted node
					temp = root;
					//In this case set the current root node value to zero
					root = nil;
				}
				else
				{
					// One child case 
					root = temp;
				}
				//free the deleted node
				temp = nil;
			}
			else
			{
				//When left and right both subtree exists
				// Find inorder successor 
				temp = self.min_key_node(root!.right);
				// Set new value to current node
				root!.key = temp!.key;
				// Delete smallest element in find node
				// Goal to delete leaf node
				root!.right = self.delete_node(root!.right, temp!.key);
			}
		}
		// If the tree had only one node then return 
		if (root == nil)
		{
			return root;
		}
		// set height of current node 
		root!.height = 1 + self.max_height(self.height(root!.left), self.height(root!.right));
		// get balance factor
		let balance: Int = self.get_balance_factor(root);
		// Transform into a balanced avl  tree 
		// 4 possible situation
		if (balance > 1 && self.get_balance_factor(root!.left) >= 0)
		{
			return self.right_rotate(root);
		}
		if (balance > 1 && self.get_balance_factor(root!.left) < 0)
		{
			root!.left = self.left_rotate(root!.left);
			return self.right_rotate(root);
		}
		if (balance < -1 && self.get_balance_factor(root!.right) <= 0)
		{
			return self.left_rotate(root);
		}
		if (balance < -1 && self.get_balance_factor(root!.right) > 0)
		{
			root!.right = self.right_rotate(root!.right);
			return self.left_rotate(root);
		}
		return root;
	}
	//Check that whether given key node is exist in given tree
	func node_exist(_ root: Node? , _ key : Int) -> Bool
	{
		if (root == nil)
		{
			return false;
		}
		else
		{
			if (root!.key == key)
			{
				//When node is exist
				return true;
			}
			return (self.node_exist(root!.left, key) || self.node_exist(root!.right, key));
		}
	}
	//This is handling the request of deleted node in AVL
	func delete_tree_node(_ key: Int)
	{
		if (self.root != nil && self.node_exist(self.root, key) == true)
		{
			print("\n Before Delete node ", key ," element \n", terminator: "");
			self.preorder(self.root);
			self.root = self.delete_node(self.root, key);
			print("\n After Delete node ", key ," element \n", terminator: "");
			self.preorder(self.root);
		}
		else
		{
			print("\n Deleted node ", key ," is not found \n", terminator: "");
			self.preorder(self.root);
		}
	}
}
func main()
{
	let obj: AvlTree = AvlTree();
	//add tree node
	obj.root = obj.add_node(obj.root, 12);
	obj.root = obj.add_node(obj.root, 7);
	obj.root = obj.add_node(obj.root, 5);
	obj.root = obj.add_node(obj.root, 19);
	obj.root = obj.add_node(obj.root, 17);
	obj.root = obj.add_node(obj.root, 13);
	obj.root = obj.add_node(obj.root, 11);
	obj.root = obj.add_node(obj.root, 3);
	obj.root = obj.add_node(obj.root, 2);
	obj.root = obj.add_node(obj.root, 7);
	/*
			    Resultant  AVL Tree
			    -----------------

			           12
			          /  \ 
			         /    \
			     (2)7      17
			       / \     / \
			      3   11  13  19
			     / \
			    2   5

			*/
	obj.delete_tree_node(7);
	/*
			   After delete node 7
			    -----------------

			           12
			          /  \ 
			         /    \
			     (1)7      17
			       / \     / \
			      3   11  13  19
			     / \
			    2   5
			*/
	obj.delete_tree_node(11);
	/*
	    After delete node 11
	    -----------------

	             12
	            /  \ 
	           /    \
	          7      17
	         / \     / \
	        3   11  13  19
	       / \
	      2   5

	      //remove node

	             12
	            /  \ 
	           /    \
	          7      17
	         /       / \
	        3       13  19
	       / \
	      2   5

	    //  Balance the AVL tree

	             12
	            /  \ 
	           /    \
	          3      17
	         / \     / \
	        2   7  13  19
	           /
	          5
	  */
}
main();

Output

 Before Delete node  7  element
 12(1) 7(2) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
 After Delete node  7  element
 12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
 Before Delete node  11  element
 12(1) 7(1) 3(1) 2(1) 5(1) 11(1) 17(1) 13(1) 19(1)
 After Delete node  11  element
 12(1) 3(1) 2(1) 7(1) 5(1) 17(1) 13(1) 19(1)


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