When deleting a node with two children in an AVL tree, which node is used as a replacement to maintain the AVL property?

When deleting a node with two children in an AVL tree, the node used as a replacement to maintain the AVL property is either the node with the highest value in the left subtree (in-order predecessor) or the node with the lowest value in the right subtree (in-order successor).

Here are the steps:

1. First, find the node to be deleted. If the node is found, there are three cases to consider:

   • Node to be deleted has no children: This is the simplest case; just delete the node.

   • Node to be deleted has only one child: Copy the child to the node and delete the child.

   • Node to be deleted has two children: Find in-order predecessor or in-order successor of the node. Copy contents of the in-order predecessor or in-order successor to the node and delete the in-order predecessor or in-order successor. Note that in-order predecessor is maximum in left subtree. In-order Successor is minimum in right subtree.

2. After deletion, the tree might not be balanced. The balance is broken only in ancestors of the deleted node. So balance the ancestors.

In AVL tree, after performing operations like insertions or deletions, it could be necessary to perform some rotations in order to keep the AVL property. The rotations can be: Left-Left rotation, Right-Right rotation, Left-Right rotation, and Right-Left rotation.