avl-tree

How should an AVL tree be rotated if it is both a right-right case and right-left case?


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?

image of the unbalanced binary tree after the deletion


Solution

  • 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