dev/avl_tries.cpp
Node *AVLDeleteNode(Node *root, int key)
{

	// STEP 1: PERFORM STANDARD BST DELETE
	if (root == NULL)
		return root;

	// If the key to be deleted is smaller
	// than the root's key, then it lies
	// in left subtree
	if (key < root->key)
		root->left = AVLDeleteNode(root->left, key);

	// If the key to be deleted is greater
	// than the root's key, then it lies
	// in right subtree
	else if (key > root->key)
		root->right = AVLDeleteNode(root->right, key);

	// if key is same as root's key, then
	// This is the node to be deleted
	else
	{
		// node with only one child or no child
		if ((root->left == NULL) ||
			(root->right == NULL))
		{
			Node *temp = root->left ? root->left : root->right;

			// No child case
			if (temp == NULL)
			{
				temp = root;
				root = NULL;
			}
			else			   // One child case
				*root = *temp; // Copy the contents of
							   // the non-empty child
			free(temp);
		}
		else
		{
			// node with two children: Get the inorder
			// successor (smallest in the right subtree)
			Node *temp = minValueNode(root->right);

			// Copy the inorder successor's
			// data to this node
			root->key = temp->key;

			// Delete the inorder successor
			root->right = AVLDeleteNode(root->right,
									 temp->key);
		}
	}

	// If the tree had only one node
	// then return
	if (root == NULL)
		return root;

	// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
	root->height = 1 + max(height(root->left),
						   height(root->right));

	// STEP 3: GET THE BALANCE FACTOR OF
	// THIS NODE (to check whether this
	// node became unbalanced)
	int balance = AVLgetbalance(root);

	// If this node becomes unbalanced,
	// then there are 4 cases

	// Left Left Case
	if (balance > 1 &&
		AVLgetbalance(root->left) >= 0)
		return rightRotate(root);

	// Left Right Case
	if (balance > 1 &&
		AVLgetbalance(root->left) < 0)
	{
		root->left = leftRotate(root->left);
		return rightRotate(root);
	}

	// Right Right Case
	if (balance < -1 &&
		AVLgetbalance(root->right) <= 0)
		return leftRotate(root);

	// Right Left Case
	if (balance < -1 &&
		AVLgetbalance(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. 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 .
Node *AVLDeleteNode(Node *root, int key)
{
	if (root == NULL)
		return root;
	if (key < root->key)
		root->left = AVLDeleteNode(root->left, key);
	else if (key > root->key)
		root->right = AVLDeleteNode(root->right, key);
	else
	{
		if ((root->left == NULL) ||
			(root->right == NULL))
		{
			Node *temp = root->left ? root->left : root->right;
			if (temp == NULL)
			{
				temp = root;
				root = NULL;
			}
			else			   
				*root = *temp; 
			free(temp);
		}
		else
		{
			Node *temp = minValueNode(root->right);
			root->key = temp->key;
			root->right = AVLDeleteNode(root->right,
									 temp->key);
		}
	}
	if (root == NULL)
		return root;
	root->height = 1 + max(height(root->left),
						   height(root->right));
	int balance = AVLgetbalance(root);
	if (balance > 1 &&
		AVLgetbalance(root->left) >= 0)
		return rightRotate(root);
	if (balance > 1 &&
		AVLgetbalance(root->left) < 0)
	{
		root->left = leftRotate(root->left);
		return rightRotate(root);
	}
	if (balance < -1 &&
		AVLgetbalance(root->right) <= 0)
		return leftRotate(root);
	if (balance < -1 &&
		AVLgetbalance(root->right) > 0)
	{
		root->right = rightRotate(root->right);
		return leftRotate(root);
	}
	return root;
}
Node * AVLDeleteNode ( Node * root , int key ) { if ( root == NULL ) return root ; if ( key < root -> key ) root -> left = AVLDeleteNode ( root -> left , key ) ; else if ( key > root -> key ) root -> right = AVLDeleteNode ( root -> right , key ) ; else { if ( ( root -> left == NULL ) || ( root -> right == NULL ) ) { Node * temp = root -> left ? root -> left : root -> right ; if ( temp == NULL ) { temp = root ; root = NULL ; } else * root = * temp ; free ( temp ) ; } else { Node * temp = minValueNode ( root -> right ) ; root -> key = temp -> key ; root -> right = AVLDeleteNode ( root -> right , temp -> key ) ; } } if ( root == NULL ) return root ; root -> height = 1 + max ( height ( root -> left ) , height ( root -> right ) ) ; int balance = AVLgetbalance ( root ) ; if ( balance > 1 && AVLgetbalance ( root -> left ) >= 0 ) return rightRotate ( root ) ; if ( balance > 1 && AVLgetbalance ( root -> left ) < 0 ) { root -> left = leftRotate ( root -> left ) ; return rightRotate ( root ) ; } if ( balance < -1 && AVLgetbalance ( root -> right ) <= 0 ) return leftRotate ( root ) ; if ( balance < -1 && AVLgetbalance ( 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