1
$\begingroup$

Suppose I am trying to construct a simple AVL tree:

enter image description here

Upon inserting 'B' the tree becomes imbalanced. How do I exactly know that I need a LR or RL rotation without making any guesses?

From what I heard is that if you insert at right side of tree and it becomes imbalanced then you need a LR rotation and vice-versa. I want to make sure that it is true.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? Have you seen en.wikipedia.org/wiki/Tree_rotation ? All cases are there. $\endgroup$
    – Evil
    Feb 16, 2017 at 0:06
  • $\begingroup$ You can refer 'cise.ufl.edu/~nemo/cop3530/AVL-Tree-Rotations.pdf' just see to it that the traversal of the tree before and after the rotation remains same. $\endgroup$
    – Akash Mahapatra
    Feb 16, 2017 at 5:00
  • $\begingroup$ There's no LR and RL cases there. Just tell me how do I know if the tree is right-left or left-right imbalanced. Thanks. $\endgroup$
    – Pierte
    Feb 16, 2017 at 7:50

1 Answer 1

Reset to default
3
$\begingroup$

In this case the tree is right-left unbalanced. That's because when you insert $B$ it causes the root node to become unbalanced. You can tell its right-left unbalanced from the path that goes from the newly inserted node to the root node i.e. $B$ is the right child of $A$ and $A$ is the left child of $C$. Therefore, it needs a left-right rotation.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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