AVL Tree Visualization

What is an AVL Tree?

An AVL Tree is a self-balancing Binary Search Tree named after inventors Adelson-Velsky and Landis. In an AVL tree, the heights of the left and right subtrees of any node differ by at most one. This balance property ensures that the tree maintains O(log n)height, guaranteeing efficient operations even in worst-case scenarios.

When an insertion or deletion violates the AVL property, the tree automatically performs rotations to restore balance. These rotations (single or double) restructure the tree while maintaining the BST ordering property, ensuring optimal performance for all operations.

Key Characteristics

Height Balanced: Left and right subtree heights differ by at most 1
Guaranteed O(log n): All operations maintain logarithmic time complexity
Self-Balancing: Automatic rotations maintain balance after insertions/deletions
Balance Factor: height(left) - height(right) must be -1, 0, or 1
Four Rotation Types: Left, Right, Left-Right, Right-Left rotations

Interactive AVL tree simulation. Insert values and watch automatic balancing with rotations. Height displayed next to each node.

Insert Value:

Actions:

Insert a value to create the root node and start building your AVL tree

How to Use

Step 1: Enter a number and click "Insert Node" to add it to the tree.

Step 2: The node will be inserted following BST rules, then the tree will automatically balance.

Step 3: Watch for rotation messages that appear when the tree rebalances itself.

Step 4: Each node shows its height value (h:n) to help understand balancing.

Note: Nodes with imbalanced subtrees would briefly show in yellow before rotation (though rotations happen automatically).

Rotation Types

Left-Left (LL): Single right rotation when left subtree of left child is taller.

Right-Right (RR): Single left rotation when right subtree of right child is taller.

Left-Right (LR): Left rotation on left child, then right rotation on node.

Right-Left (RL): Right rotation on right child, then left rotation on node.

Balance Factor: Calculated as height(left subtree) - height(right subtree).

AVL vs Regular BST

BST Worst Case: Can degenerate to O(n) when inserting sorted data.

AVL Guarantee: Always maintains O(log n) through automatic balancing.

Trade-off: AVL requires more rotations (overhead) but ensures consistent performance.

Use Cases: Databases, file systems, and applications requiring predictable performance.

Height Tracking: Each node stores its height for efficient balance factor calculation.

AVL Tree Operations

Insert: Standard BST insert, then update heights and rebalance up to root.

Delete: Standard BST delete, then update heights and rebalance up to root.

Search: Same as BST search - O(log n) guaranteed due to balance.

Rotation: Single or double rotation to restore balance factor to [-1, 0, 1].

Height Update: Recalculate height as 1 + max(left height, right height) after changes.

Balance Factor: Compute as left height minus right height; must be in [-1, 1].

Common AVL Tree Patterns

Identify Rotation Type: Check balance factor of node and its child to determine LL, RR, LR, or RL case.

Maintain Height: Always update height after any structural change; base case height is 0 for null.

Recursive Rebalancing: After insert/delete, check and fix balance on the way back up the recursion.

Augmented AVL: Store additional info like subtree size for order statistics in O(log n).

Range Queries: Leverage balanced structure for efficient range counting and sum queries.

Bulk Operations: Build balanced AVL from sorted array in O(n) using divide and conquer.

vs Red-Black: AVL is more strictly balanced; better for lookup-heavy workloads.

C++

Java

Python

/* AVL Tree implementation in C */
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value, height;
    struct Node *left, *right;
} Node;

int height(Node *n) { return n ? n->height : 0; }
int max(int a, int b) { return (a > b) ? a : b; }
int getBalance(Node *n) { return n ? height(n->left) - height(n->right) : 0; }

Node* createNode(int value) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->value = value;
    node->height = 1;
    node->left = node->right = NULL;
    return node;
}

Node* rightRotate(Node *y) {
    Node *x = y->left, *T2 = x->right;
    x->right = y; y->left = T2;
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;
    return x;
}

Node* leftRotate(Node *x) {
    Node *y = x->right, *T2 = y->left;
    y->left = x; x->right = T2;
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;
    return y;
}

Node* insert(Node* node, int value) {
    if (!node) return createNode(value);
    if (value < node->value)
        node->left = insert(node->left, value);
    else if (value > node->value)
        node->right = insert(node->right, value);
    else return node;

    node->height = 1 + max(height(node->left), height(node->right));
    int balance = getBalance(node);

    // Left Left Case
    if (balance > 1 && value < node->left->value)
        return rightRotate(node);
    // Right Right Case
    if (balance < -1 && value > node->right->value)
        return leftRotate(node);
    // Left Right Case
    if (balance > 1 && value > node->left->value) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    // Right Left Case
    if (balance < -1 && value < node->right->value) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}

int main() {
    Node *root = NULL;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30); // Triggers rotation
    printf("Root after insertions: %d\n", root->value);
    return 0;
}