Page 142 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS
P. 142

Unit 6: Binary Search Tree and AVL Trees





          To fix this, we must perform a left rotation, rooted at A.  This is done in the following steps:  Notes
          b becomes the new root.
          a takes ownership of b’s left child as its right child, or in this case, null.
          b takes ownership of a as its left child.
          The tree now looks like this:
            b
           / \

          a   c

          Right Rotation (RR)

          A right rotation is a mirror of the left rotation operation described above.  Imagine we have this
          situation:
              c

             /
            b
           /
          a


          To fix this, we will perform a single right rotation, rooted at C.  This is done in the following
          steps:
          b becomes the new root.

          c takes ownership of b’s right child, as its left child. In this case, that value is null.
          b takes ownership of c, as it’s right child.
          The resulting tree:
            b
           / \
          a   c


          Left-Right Rotation (LR) or “Double left”


          Sometimes a single left rotation is not sufficient to balance an unbalanced tree.  Take this
          situation:
          a
           \

            c
          Perfect. It’s balanced.  Let’s insert ‘b’.
          a
           \
            c





                                           LOVELY PROFESSIONAL UNIVERSITY                                   137
   137   138   139   140   141   142   143   144   145   146   147