AVL Trees continued

Deletion from an AVL Search Tree

As with insertions, a node is deleted using the standard inorder successor (predecessor) logic for binary search trees. But, just like insertion, deletion can cause an imbalance, which will need to be fixed by applying one of the four rotations.

For example, assume the following tree:

Now suppose that the nodes 15 and 12 are deleted. The resulting tree is:

Delete 15 using INORDER SUCCESSOR logic:

Delete 12 using INORDER SUCCESSOR logic:

If we identify the parent of the actual node that was deleted, then:

• If the left child was deleted, the balance factor at the parent decreased by 1.
• If the right child was deleted, the balance factor at the parent increased by 1.

The change in balance factor can move up the tree from the deleted node's parent all the way to the root. Therefore, it's possible that a node's balance factor could become +2 or -2. If this happens, then balance needs to be restored.

Let A be the node where balance must be restored. If the deleted node was in A's right subtree, then let B be the root of A's left subtree. Then:

1. B has balance factor 0 or +1 after deletion -- then perform a single right rotation

2. B has balance factor -1 after deletion -- then perform a left-right rotation

If the deleted node was in A's left subtree, then let B be the root of A's right subtree. Then:

1. B has balance factor 0 or -1 after deletion -- then perform a single left rotation

2. B has balance factor +1 after deletion -- then perform a right-left rotation

Delete 9 from the tree.

Unlike insertions, one rotation may not be enough to restore balance to the tree. If this is the case, then locate the next node where the balance factor is "bad" (call this A):

• If A's balance factor is positive, then let B be A's left child

• If B's left subtree height is larger than B's right subtree height, then perform a single right rotation.

• If B's left subtree height is smaller than B's right subtree height, then perform a left-right rotation.

• If B's left subtree height is equal to B's right subtree height, then perform either rotation.

• If A's balance factor is negative, then let B be A's right child

• If B's right subtree height is larger than B's left subtree height, then perform a single left rotation.

• If B's right subtree height is smaller than B's left subtree height, then perform a right-left rotation.

• If B's right subtree height is equal to B's left subtree height, then perform either rotation.

What type of rotation should be performed to fix the imbalance?

A single left rotation with the highlighted nodes

OR a right-left rotation with the highlighted nodes

Result after the single left rotation:

Result after the right-left rotation: