2
$\begingroup$

For AVL-Tree there exists the following Rotations for Balancing:

  • Left Rotation
  • Right Rotation
  • Left-Right Rotation
  • Right-Left Rotation

My Question is about the Naming for the Double-Rotations. Sometimes a Left-Right Rotation is defined as a Left-Rotation followed by a Right-Rotation. This is for me the logical case. Sometimes a Left-Right Rotation is defined as a Right-Rotation followed by a Left-Rotation.

Is there a reason for this different definitions? I think it is only a Exchange of the terms - but why?

$\endgroup$
2
$\begingroup$

I would say they are just personal preferences without any particular naming rules or standard attached. Just as you said, it is only a exchange of the terms. There is negligible if any other difference.

The logical choice for me is also letting Left-Right Rotation be the Left-Rotation followed by a Right-Rotation.

However, a few people might prefer to recognize Left-Right Rotation as primarily a Left-Rotation (the larger rotation) with a Right-Rotation before it (as a delta operation). In this way, both Left-Rotation and Left-Right-Rotation moves the (larger) right subtree to the left.

In case you might think this is the whole story, here is more naming confusion and conflict. People may even differ on which tree rotation should be called Left-Rotation and which one should be called Right-Rotation! Not only with AVL trees, but possibly also with other kinds of binary search trees that use rotations to maintain balance. Here is an excerpt from the wikipedia item for tree rotation.

In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations.

There exists an inconsistency in different descriptions as to the definition of the direction of rotations. Some say that the direction of rotation reflects the direction that a node is moving upon rotation (a left child rotating into its parent's location is a right rotation) while others say that the direction of rotation reflects which subtree is rotating (a left subtree rotating into its parent's location is a left rotation, the opposite of the former). This article takes the approach of the directional movement of the rotating node.

So, should we take some action to make it more consistent? Probably not necessarily. As far as I have experienced and as far as I have checked[1][2][3][4][5], the approach taken by Wikipedia, which calls the rotation in the counterclockwise direction left rotation and which calls the left rotation followed by right rotation left-right rotation is far more popular. I will stick to that approach myself. I would recommend you stick to that approach, which you are comfortable with as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.