enter image description here

As you can see in this tree its unbalanced at the root with a balanced factor of $-2$. You can also perform a Right left rotation or a Right Right rotation. Which do you have to pick in this case?

  • 1
    $\begingroup$ If you're following a certain algorithm, you have to pick what the algorithm specifies. Otherwise, I'm not sure what you mean by "have to". It's a free world. You don't have to do anything. If you're just looking for an operation that improves the balance factor, then you could just apply both and checks which of them works, if any. $\endgroup$ – Yuval Filmus Feb 27 '19 at 5:43
  • $\begingroup$ @Tinler How about a left rotation? $\endgroup$ – John L. Feb 27 '19 at 5:45

Apparently, you want to rebalance the AVL tree.

You can either do a simple left rotation or a right-left rotation.

I prefer not to mention right-right rotation since that term is misleading and ambiguous.

You can visualize what is happening. Go to AVL tree visualization, a page created by David Galles. Insert 2, 1, 4, 3, 5 in that order. Now look closely when you delete 1.
enter image description here

| cite | improve this answer | |

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.