AlgoViz: Interactive Algorithm Visualization Tool

AVL Tree

Category: Tree / Graph | Time: O(log n) | Space: O(log n)

Input Data

Visualization

Visual representation of the data structure

Enter tree data to start visualization.

Code Editor

The code is for reference. Editing it won't affect the visualization.

// AVL Tree insertion
function insert(node, key) {
    // 1. Perform standard BST insertion
    if (node == null) return new Node(key);
    if (key < node.key) node.left = insert(node.left, key);
    else if (key > node.key) node.right = insert(node.right, key);
    else return node;

    // 2. Update height of this ancestor node
    node.height = 1 + Math.max(height(node.left), height(node.right));

    // 3. Get the balance factor
    let balance = getBalance(node);

    // 4. If unbalanced, then perform rotations
    // Left Left Case
    if (balance > 1 && key < node.left.key) return rightRotate(node);
    // Right Right Case
    if (balance < -1 && key > node.right.key) return leftRotate(node);
    // Left Right Case
    if (balance > 1 && key > node.left.key) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }
    // Right Left Case
    if (balance < -1 && key < node.right.key) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }
    return node;
}

Frequently Asked Questions

About AVL Tree

What is an AVL Tree?

How does an AVL Tree maintain its balance?

What is a 'rotation' in an AVL Tree?

What is the time complexity of operations in an AVL Tree?

What are the four cases of unbalance that require rotations?

How does an AVL Tree compare to a Red-Black Tree?

What is the space complexity of an AVL Tree?

Is building an AVL Tree from a sorted list of n items efficient?

Are AVL trees used often in practice?

What is the 'balance factor'?

Where can I learn more?