Please enable JavaScript.

Coggle requires JavaScript to display documents.

AVL Tree (What is an AVL Tree? (Motivation for being Balanced: Since most…

- - - - The 4 possible cases of Rotation:
        
        Left Left Rotation:
        (when bfactor(x) = +2 and bfactor(x.left) = 0 or +1
        
        Only need to invoke rightRotate(x)
        
        10/20/30 becomes 10/20\30. (10 -> 20 -> 30)
        becomes (10 -> 20 <- 30)
        
        How to visualize? Put a nail below root's node (in this case 30) and imagine you are pulling the entire string down the right side of the nail until root of left subtree (20 in this case) goes to top of the nail.
        
        Left Right Rotation:
        (when bfactor(x) = +2 and bfactor(x.left) = -1
        
        Need to invoke leftRotate(x.left);
        
        next invoke rightRotate(x);
        
        10 left child of 30. 20 right child of 10.
        
        Two-Step Rotation:
        
        First, fix nail at left child of root node and rotate such that right child of left subtree now becomes the left child of root. (Now you have a Left-Left Situation)
        
        Then, do the same rotation as done in LL Rotation.
        Note that this is still considered as one rotation, although it has 2 steps.
        
        Right Right Rotation:
        (when bfactor(x) = -2 and bfactor(x.right) = -1 or 0)
        
        Only need to invoke leftRotate(x);
        
        10\20\30 becomes 10/20\30
        
        How to visualize? Put a nail below root's node (10 in this case) and imagine you are pulling the entire string down the left side of the nail until root of rightsubtree (20 in this case) goes to top of the nail.
        
        Right Left Rotation:
        when bfactor(x) = - 2 and bfactor(x.right) = 1
        
        Need to invoke rightRotate(x.right)
        
        next invoke leftRotate(x);
        
        30 right child of 10, 20 left child of 30.
        
        Two-Step Rotation:
        
        Fix nail at right child of root node and rotate such that left child of right subtree now becomes right child of root. (Now you have a right-right situation)
        
        Then, do the same rotation as done in RR Rotation.
        Note that this is still considered as one rotation, although it has 2 steps.
- - - - Left Subtree of P
      - Right Subtree of P