CODEWITHSUNDEEP
algorithmbinary-search-treeavl-tree
attaboy182
attaboy182

Reputation: 2079

Avl tree left rotation & left-right rotation usage confusion

Assume we have the following structure:

        A
      /   \
     B     C
    / \
   D   E

Now, if C were to be removed, 

     A
    /
   B
  / \
 D   E

At this point, every algorithm that I looked into makes the following check: 

if (Balance-Factor(B)>=0) do **Left** rotation
else do **Left-Right** rotation;

But, why is it that this condition has to hold here? As in, if I were to do a Left-right rotation on the above tree, it seems as though I'd still be getting a balanced tree:

              E
             / \
            B   A
           /
          D

So, why is it that we have to only do a left rotation when even a right-left gives us a balanced tree for this scenario?

Upvotes: 1

Views: 1702

Answers (2)

ArgyrisSofroniou
ArgyrisSofroniou

Reputation: 122

The confusion stems from the namings they give to the rotations in most avl tutorials.

Namings: LL, RR, LR, RL

Cases : L, R, LL, RR, LR, RL

A possible reason why most avl tutorials exclude the namings for the single rotations is because the single rotations can use the LL and RR codes. Basically the 2 single rotation codes are part of their corresponding doubles.

In other words if the LL and RR codes are written properly, they can also be used for the single rotations.

In your example the case is a single rotation. An L rotation which uses the LL code. This is the reason you must not use the LR code.
Because the case is not even a double rotation to start with.

Proof:

      A
     / \
    B   G
   / \   \
  C   E   H
 /     \
D       F

Remove H:

      A
     / \
    B   G
   / \   
  C   E   
 /     \
D       F

With LR rotation:

      E
     / \
    B   A
   /   / \
  C   F   G
 /     
D           

Remains UnBalanced

With LL rotation:

      B
     / \
    C   A
   /   / \
  D   E   G
       \
        F

Is Balanced

Upvotes: 2

OneCricketeer
OneCricketeer

Reputation: 191701

The reason only a "left" rotation is required is because the balance factor at node A is the first node to meet the rebalance criteria.

Think of each subtree as a weight on a scale, where the "weight" of these weights is the "height" of the subtree.

After deletion, B, E, and D are balanced.

The right subtree of A has "weight" 0, and the left subtree has "weight" 2.

This difference is greater than 1, towards the left subtree. Since the left subtree is balanced, only a single rotation at A is required towards the right subtree.

Upvotes: 0

Related Questions