Is the LL Rotation a single left Rotation or a single right Rotation?

Question

As this for example,

In this post, it says the LL Rotation is a single left Rotation. https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/

However, from the wiki of tree rotation, https://en.wikipedia.org/wiki/Tree_rotation, I think that is a single right Rotation?

What is more, I also see, https://www.codingeek.com/data-structure/avl-tree-introduction-to-rotations-and-its-implementation/. This says it is a RR Rotation and it is a single right Rotation?

I am confused for the different opinions. Can anyone tell me the truth for the above picture?

• Is it a LL Rotation?
• Is it a single left rotation or a single right rotation?

Answer 1

First of all, all the referenced websites agree that the depicted example represents a single right rotation.

You write:

As this for example, LL tree rotation

In this post, it says the LL Rotation is a single left Rotation https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/

Indeed, although there is no ambiguity for what the terms "left rotation" and "right rotation" mean, there seem to be two contradictory interpretations floating around for what "LL rotation" and "RR rotation" stand for.

However, from the wiki of tree rotation, https://en.wikipedia.org/wiki/Tree_rotation, I think that is a single right Rotation?

Well the Wikipedia article does not use the term "LL rotation". But it does also agree that the depicted example represents a right rotation. There is so far no ambiguity for the terms "left rotation" and "right rotation".

Can anyone tell me the truth for the above picture?

Like all those sites explain: it is a single right rotation.

LL, RR

The ambiguity arises in the use of the terms "LL rotation" and "RR rotation":

The acronyms "LL" and "RR" make more sense in describing the imbalance before any rotation is performed. The Wikipedia article categorises imbalanced trees in 4 categories (4 columns):

In each column you see the original state at the top, and then below it the result of the rotation(s) that should be performed to bring the tree in balance.

So for a tree in the Left Left case, we need a right rotation. And for a tree in the Right Right case we need a left rotation.

The following notes of an ICS course at University of California, Irvine, explain where the letters LL, RR, LR, RL come from:

The rotation is chosen considering the two links along the path below the node where the imbalance is, heading back down toward where you inserted a node. (If you were wondering where the names LL, RR, LR, and RL come from, this is the answer to that mystery.)

• If the two links are both to the left, perform an LL rotation rooted where the imbalance is.
• If the two links are both to the right, perform an RR rotation rooted where the imbalance is.
• If the first link is to the left and the second is to the right, perform an LR rotation rooted where the imbalance is.
• If the first link is to the right and the second is to the left, perform an RL rotation rooted where the imbalance is.

But I feel speaking of LL rotation can trigger confusion, as here we see that the double LL describes the imbalance of the original state, and does not describe the action. It would have been cleaner to speak of an LL state (or imbalance) and then name the resolving action a "right rotation". With that in mind, I think the Wikipedia article takes a good position, as it avoids the term "LL rotation".

This misunderstanding does not arise with LR and RL rotations. You can say that the initial state is LR (the imbalance was caused by giving a left leaf a right child), and you can also say that first a left rotation is needed, and then a right rotation. In both cases the abbreviation LR makes sense. So no ambiguity there.

Conclusion

The terms left rotation and right rotation are clear.

There are different traditions for which of these rotations to call an LL or RR rotation. In my opinion we should avoid talking about "LL rotation" or "RR rotation", as these letters do not describe the act of the rotation, but the initial state. It is better to speak of the "LL case" or "LL imbalance".

With those terms we can say:

• A tree with an LL imbalance needs a right rotation
• A tree with a RR imbalance needs a left rotation