AVL Tree

An AVL tree is a self-balancing binary search tree where the difference in heights between the left and right subtrees (called the balance factor) is at most 1 for every node.

• Empty Node is -1
• BF = Left Subtree - Right Subtree

Rotations (When a new Node is added)

• LL → if added to the LEFT of the LEFT CHILD (Rotate clockwise)
• RR → if added to the RIGHT of the RIGHT CHILD (Rotate anticlockwise)
• LR → LEFT child has the RIGHT CHILD Added (anticlockwise(right rotate) at child then clockwise(left rotate) with root)
• RL → RIGHT Child has a LEFT child added (clockwise(left rotate) at the child then anticlockwise(right rotate) with root)

LL Rotations (Clockwise)

Right Child becomes the left child after LL rotation     
         *        *
        /          \
       /     =>     \
      /\            /\

Simple LL Rotation

Before LL Rotation:              After LL Rotation:

        3                             2
       /                             / \
      2                             1   3
     /
    1

Full LL rotation

Before LL Rotation:              After LL Rotation:

        Root                          X
        /                           /   \
       X                           Y     Root
      / \                         / \    /
     Y   XR                      YL  YR XR
    / \
   YL  YR

RR Rotations (Anticlockwise)

Simple RR rotation

Right Child becomes the left child after RR rotation

      Before RR Rotation:              After RR Rotation:
        1                               2 (new Root)
         \                            /   \
          2                          1     3
           \
            3

Right Child becomes the left child after RR rotation
    *                  *       
     \                /           
      \     =>       /          
      /\            /\

Full RR Rotation

Before RR Rotation:       After RR Rotation:

Root                          X (new Root)
   \                        /    \
    X                    Root     Y
   / \                      \    /  \
 XL    Y                    XL  YL  YR
     /  \
   YL    YR

LR Rotation

Right rotation at the Left Child, then Left rotation at the root

Before Rotation:    Right Rotation at Left Child:     Left Rotation at Root:

    3                       3                                    2 (new root)
   /                       /                                   /    \
  1                       2 (new root of subtree)             1      3
   \                     / 
    2                   1

public AVLNode leftRightRotate(AVLNode root) {
    root.setLeft(rightRotate(root.getLeft()));
    return leftRotate(root);
}

RL Rotation

RIGHT Child has a LEFT child added (clockwise(left rotate)) at the child then anticlockwise(right rotate) with root)

Before Rotation:     After Left Rotation at 3:      After Right Rotation at 1:

    1                        1                              2
     \                        \                           /   \
      3                        2                        1      3
     /                          \
    2                            3

 public static AVLNode rightLeftRotate(AVLNode root) {
    root.setLeft(leftRotate(root.getRight()));
    return rightRotate(root);
}