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.
3.
B has balance factor -1 after deletion -- then perform a left-right
rotation
4.
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.
3.
B has balance factor +1 after deletion -- then perform a right-left
rotation
4.
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.
o
o
If B's left subtree height is smaller than B's right subtree height,
then perform a left-right rotation.
o
o
If B's left subtree height is equal to B's right subtree height,
then perform either rotation.
o
•
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.
o
o
If B's right subtree height is smaller than B's left subtree height,
then perform a right-left rotation.
o
o
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:
