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.

$\endgroup$
  • 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 '17 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 '17 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 '17 at 7:50
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.

$\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.