AVL Tree Implementation

← Back to Visualizer
// 1. Right Rotate (LL Case)
Node* rightRotate(Node *y) {
    Node *x = y->left;
    Node *T2 = x->right;
    x->right = y;
    y->left = T2;
    // Update heights
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
    return x;
}

// 2. Left Rotate (RR Case)
Node* leftRotate(Node *x) {
    Node *y = x->right;
    Node *T2 = y->left;
    y->left = x;
    x->right = T2;
    // Update heights
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;
    return y;
}

Left-Left (LL)

Inserted node is in the left subtree of the left child. Solution: Single Right Rotation.

Right-Right (RR)

Inserted node is in the right subtree of the right child. Solution: Single Left Rotation.

Left-Right (LR)

Left child's right subtree. Solution: Left-then-Right Rotation.

Right-Left (RL)

Right child's left subtree. Solution: Right-then-Left Rotation.