The AVL tree in the following figure is generated by removing a leaf node in subtree T0.
After the node has been deleted, the tree becomes unbalanced.
Should I regard the below condition as a Right-Right case or a Right-Left case?
It is a Right-Right case, because node 𝑦's balance factor is not negative (it is zero).
Wikipedia's section on AVL rebalancing lists these possibilities, but realise that the nodes are labelled differently:
Let X be the node that has a (temporary) balance factor of −2 or +2. Its left or right subtree was modified. Let Z be the higher child [...]
- Right Right ⟹ Z is a right child of its parent X and BF(Z) ≥ 0
- [...]
- Right Left ⟹ Z is a right child of its parent X and BF(Z) < 0
Using that labelling for your tree, you would picture it like this:
____44____ BF(X): 2
/ X \
17 __62__ BF(Z): 0
/ \ / Z \
10 21 __50_ 78
/ \ / \
48 54 72 88
/ \ / \ / \
45 49 52 56 81 92
So we are in the first (i.e. Right Right) case.
Wikipedia continues with the action to take:
And the rebalancing is performed differently:
- Right Right ⟹ X is rebalanced with a simple rotation
rotate_Left
This simple rotation will give this tree:
____62____
/ Z \
__44__ 78
/ X \ / \
17 __50_ 72 88
/ \ / \ / \
10 21 48 54 81 92
/ \ / \
45 49 52 56