AVL.c
// Recursive function to delete a node with given key
// from subtree with given root. It returns root of
// the modified subtree.

Recursive function to delete a node with given key
from subtree with given root. It returns root of
the modified subtree.
Recursive function to delete a node with given key from subtree with given root . It returns root of the modified subtree .
struct Node* deleteNode(struct Node* root, int key)
{
	if (root == NULL)
		return root;
	if (key < root->key)
		root->left = deleteNode(root->left, key);
	else if (key > root->key)
		root->right = deleteNode(root->right, key);
	else
	{
		if ((root->left == NULL) || (root->right == NULL))
		{
			struct Node *temp = root->left ? root->left :
				root->right;
			if (temp == NULL)
			{
				temp = root;
				root = NULL;
			}
			else 
				*root = *temp; 
			free(temp);
		}
		else
		{
			struct Node* temp = minValueNode(root->right);
			root->key = temp->key;
			root->right = deleteNode(root->right, temp->key);
		}
	}
	if (root == NULL)
		return root;
	root->height = 1 + maximum(height(root->left),
		height(root->right));
	int balance = getBalance(root);
	if (balance > 1 && getBalance(root->left) >= 0)
		return rightRotate(root);
	if (balance > 1 && getBalance(root->left) < 0)
	{
		root->left = leftRotate(root->left);
		return rightRotate(root);
	}
	if (balance < -1 && getBalance(root->right) <= 0)
		return leftRotate(root);
	if (balance < -1 && getBalance(root->right) > 0)
	{
		root->right = rightRotate(root->right);
		return leftRotate(root);
	}
	return root;
}
struct Node * deleteNode ( struct Node * root , int key ) { if ( root == NULL ) return root ; if ( key < root -> key ) root -> left = deleteNode ( root -> left , key ) ; else if ( key > root -> key ) root -> right = deleteNode ( root -> right , key ) ; else { if ( ( root -> left == NULL ) || ( root -> right == NULL ) ) { struct Node * temp = root -> left ? root -> left : root -> right ; if ( temp == NULL ) { temp = root ; root = NULL ; } else * root = * temp ; free ( temp ) ; } else { struct Node * temp = minValueNode ( root -> right ) ; root -> key = temp -> key ; root -> right = deleteNode ( root -> right , temp -> key ) ; } } if ( root == NULL ) return root ; root -> height = 1 + maximum ( height ( root -> left ) , height ( root -> right ) ) ; int balance = getBalance ( root ) ; if ( balance > 1 && getBalance ( root -> left ) >= 0 ) return rightRotate ( root ) ; if ( balance > 1 && getBalance ( root -> left ) < 0 ) { root -> left = leftRotate ( root -> left ) ; return rightRotate ( root ) ; } if ( balance < -1 && getBalance ( root -> right ) <= 0 ) return leftRotate ( root ) ; if ( balance < -1 && getBalance ( root -> right ) > 0 ) { root -> right = rightRotate ( root -> right ) ; return leftRotate ( root ) ; } return root ; }
Recursive function to delete a node with given key
from subtree with given root.
Recursive function to delete a node with given key from subtree with given root .
// STEP 1: PERFORM STANDARD BST DELETE
 // If the key to be deleted is smaller than the
 // root's key, then it lies in left subtree
 // If the key to be deleted is greater than the
 // root's key, then it lies in right subtree
 // if key is same as root's key, then This is
 // the node to be deleted
 // node with only one child or no child
 // No child case
 // One child case
 // Copy the contents of
 // the non-empty child
 // node with two children: Get the inorder
 // successor (smallest in the right subtree)
 // Copy the inorder successor's data to this node
 // Delete the inorder successor
 // If the tree had only one node then return
 // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
 // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to
 // check whether this node became unbalanced)
 // If this node becomes unbalanced, then there are 4 cases
 // Left Left Case
 // Left Right Case
 // Right Right Case
 // Right Left Case
