AVL Tree Operations

Visualize self-balancing binary search tree with automatic rotations.

AVL Tree Selection

Choose from predefined examples or create your own AVL tree

Predefined Examples

Custom AVL Tree

Operation

Operation Type

Value

Value between 1 and 999

Playback Controls

Playback Speed: 1000ms

Empty AVL Tree - Insert a value to begin

Empty tree

No nodes to display

Current Operation

Current AVL Tree State

Values: []

Node Count: 0

Tree Type: Always Balanced (AVL)

Reference implementation of AVL Tree Operations. Select a language tab to view and copy the code.

AVLNode* insert(AVLNode* root, int val) {
    if (!root) return newAVLNode(val);  // create leaf
    if (val < root->val)
        root->left  = insert(root->left,  val); // go left
    else if (val > root->val)
        root->right = insert(root->right, val); // go right

    // Update height
    root->height = 1 + max(height(root->left), height(root->right));

    int balance = height(root->left) - height(root->right);

    if (balance > 1  && val < root->left->val)  return rotateRight(root); // LL
    if (balance < -1 && val > root->right->val) return rotateLeft(root);  // RR
    if (balance > 1  && val > root->left->val)  {                         // LR
        root->left = rotateLeft(root->left); return rotateRight(root);
    }
    if (balance < -1 && val < root->right->val) {                         // RL
        root->right = rotateRight(root->right); return rotateLeft(root);
    }
    return root;
}
AVLNode* search(AVLNode* root, int val) {
    if (!root)             return NULL; // not found
    if (val == root->val)  return root; // found
    if (val < root->val)   return search(root->left,  val);
    return search(root->right, val);
}

AVLNode* insert(AVLNode* root, int val) {
    if (!root) return new AVLNode(val); // create leaf
    if (val < root->val)
        root->left  = insert(root->left,  val); // go left
    else if (val > root->val)
        root->right = insert(root->right, val); // go right

    // Update height
    root->height = 1 + std::max(height(root->left), height(root->right));

    int balance = height(root->left) - height(root->right);

    if (balance > 1  && val < root->left->val)  return rotateRight(root); // LL
    if (balance < -1 && val > root->right->val) return rotateLeft(root);  // RR
    if (balance > 1  && val > root->left->val)  {                         // LR
        root->left = rotateLeft(root->left); return rotateRight(root);
    }
    if (balance < -1 && val < root->right->val) {                         // RL
        root->right = rotateRight(root->right); return rotateLeft(root);
    }
    return root;
}
AVLNode* search(AVLNode* root, int val) {
    if (!root)             return nullptr; // not found
    if (val == root->val)  return root;    // found
    if (val < root->val)   return search(root->left,  val);
    return search(root->right, val);
}

AVLNode insert(AVLNode root, int val) {
    if (root == null) return new AVLNode(val); // create leaf
    if (val < root.val)
        root.left  = insert(root.left,  val);  // go left
    else if (val > root.val)
        root.right = insert(root.right, val);  // go right

    // Update height
    root.height = 1 + Math.max(height(root.left), height(root.right));

    int balance = height(root.left) - height(root.right);

    if (balance > 1  && val < root.left.val)  return rotateRight(root); // LL
    if (balance < -1 && val > root.right.val) return rotateLeft(root);  // RR
    if (balance > 1  && val > root.left.val)  {                         // LR
        root.left = rotateLeft(root.left); return rotateRight(root);
    }
    if (balance < -1 && val < root.right.val) {                         // RL
        root.right = rotateRight(root.right); return rotateLeft(root);
    }
    return root;
}
AVLNode search(AVLNode root, int val) {
    if (root == null)   return null;    // not found
    if (val == root.val) return root;   // found
    if (val < root.val)  return search(root.left,  val);
    return search(root.right, val);
}

def avl_insert(root, val):
    if root is None:
        return AVLNode(val)             # create leaf
    if val < root.val:
        root.left  = avl_insert(root.left,  val)  # go left
    elif val > root.val:
        root.right = avl_insert(root.right, val)  # go right

    # Update height of current node
    root.height = 1 + max(height(root.left), height(root.right))

    # Balance factor: left_height - right_height
    balance = height(root.left) - height(root.right)

    # LL case — right rotation
    if balance > 1 and val < root.left.val:
        return rotate_right(root)
    # RR case — left rotation
    if balance < -1 and val > root.right.val:
        return rotate_left(root)
    # LR case — left then right rotation
    if balance > 1 and val > root.left.val:
        root.left = rotate_left(root.left)
        return rotate_right(root)
    # RL case — right then left rotation
    if balance < -1 and val < root.right.val:
        root.right = rotate_right(root.right)
        return rotate_left(root)
    return root

def avl_search(root, val):
    if root is None:   return None      # not found
    if val == root.val: return root     # found
    if val < root.val:
        return avl_search(root.left,  val)
    return avl_search(root.right, val)

function avlInsert(root, val) {
  if (!root) return new AVLNode(val);   // create leaf
  if (val < root.val)
    root.left  = avlInsert(root.left,  val); // go left
  else if (val > root.val)
    root.right = avlInsert(root.right, val); // go right

  // Update height
  root.height = 1 + Math.max(height(root.left), height(root.right));

  const balance = height(root.left) - height(root.right);

  if (balance > 1  && val < root.left.val)  return rotateRight(root);  // LL
  if (balance < -1 && val > root.right.val) return rotateLeft(root);   // RR
  if (balance > 1  && val > root.left.val)  {                          // LR
    root.left = rotateLeft(root.left); return rotateRight(root);
  }
  if (balance < -1 && val < root.right.val) {                          // RL
    root.right = rotateRight(root.right); return rotateLeft(root);
  }
  return root;
}
function avlSearch(root, val) {
  if (!root)            return null;    // not found
  if (val === root.val) return root;    // found
  if (val < root.val)   return avlSearch(root.left,  val);
  return avlSearch(root.right, val);
}

Python — Code Walkthrough

Standard BST insert first
if val < root.val: root.left = avl_insert(root.left, val)
AVL insert starts exactly like BST insert: recurse left if smaller, right if larger. Balancing only happens on the way back up the recursion.
Height update after recursion
root.height = 1 + max(height(root.left), height(root.right))
Height is recomputed bottom-up as the recursion unwinds. height() returns -1 for None so a single node gets height 0.
Balance factor
balance = height(root.left) - height(root.right)
Balance factor = left height - right height. Valid AVL range is [-1, 0, 1]. A factor outside this range triggers a rotation.
Four rotation cases
LL: rotate_right | RR: rotate_left | LR: rotate_left then rotate_right | RL: rotate_right then rotate_left
LL and RR are single rotations. LR and RL are double rotations — first fix the child, then fix the root — because the imbalance is "zigzag".