Algorithm Guidecomplexity: O(log n)

AVL Tree

A self-balancing binary search tree that keeps the height difference of every node's left and right subtrees at most 1. After an insert or delete it restores balance with rotations, guaranteeing O(log n) at all times.

01AVL Tree

Explore How It Works

AVL tree. A self-balancing BST that restores balance with rotations whenever the left/right height difference exceeds 1 after an insert.

insert(20) · 20 > 10, so attach it as the right child. Still balanced.

insert(30) · it all leans right into a 10→20→30 chain. Node 10's balance factor is -2 — unbalanced!

Rotate left · pull the middle node 20 up and drop 10 to its left child.

Balance restored · height drops from 2 to 1. Keeping balance every time guarantees O(log n).

Live Python

1def insert(node, key):

2 if not node:

3 return Node(key)

4 if key < node.key:

5 node.left = insert(node.left, key)

6 else:

7 node.right = insert(node.right, key)

8 update_height(node)

9 bf = balance(node) # left height − right height

10 if bf < -1: # leans right

11 return rotate_left(node) # rebalance

12 if bf > 1:

13 return rotate_right(node)

14 return node

1 / 5

02 Understand It Simply

For Everyone

🔑How It Works

Keeps the height difference between a node's subtrees within one, restoring it by rotation whenever it slips, which bounds the height at O(log n).

💡In Plain Words

A BST that restores balance with a 'rotation' whenever the left/right height difference exceeds 1 after an insert or delete.

That guarantees O(log n) instead of degrading to a lopsided, slow tree.

📍Where It's Used

–Sorted data that needs frequent search
–database indexes

03 Python Implementation

A clean, readable reference implementation of the core logic of AVL Tree.

core_implementation.py

def height(n):
    return n.height if n else 0

def balance(n):
    return height(n.left) - height(n.right) if n else 0

def rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    update(y); update(x)
    return x

def insert(node, key):
    if not node:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    update(node)
    return rebalance(node)  # rotate if |balance| > 1

04 Frequently Asked Questions

FAQ

What is AVL Tree?+

What is the time complexity of AVL Tree?+

The time complexity of AVL Tree is O(log n). Follow the step-by-step visualization to see exactly why.

Where is AVL Tree used?+

Sorted data that needs frequent search, database indexes.

What's a simple analogy for AVL Tree?+

Keeps the height difference between a node's subtrees within one, restoring it by rotation whenever it slips, which bounds the height at O(log n).

→ Trees — see allRelated

🌳Tree Traversal

O(n)

🌳Segment Tree

Query/Update O(log n)

🌳Trie

O(m) (string length)