AVL Tree Visualizer

Visualize AVL insertion, balance factors, and tree rotations with animated rebalancing, playback controls, and structural metrics.

Current status: Ready. Insert a value or generate a new example to begin.
Balance-factor playground

AVL Tree Visualizer

Watch every comparison, height update, and rotation that keeps the tree within a balance factor of −1 to +1.

AVL operations

Choose a value, then watch every repair step

ready

Press Enter to insert the entered value.

Tree setup

Ready. Insert a value or generate a new example to begin.
BF = 0
BF = ±1
|BF| > 1 (unbalanced!)
Rotation pivot
11031+133-153091-193094+1
Nodes: 7Critical BF: 0Drag to pan · scroll to zoom

Visual Legend

10
Balanced: Balance Factor is 0.
10
Slightly Heavy: Balance Factor is -1 or 1.
10
Critical: BF is >1 or <-1. Trigger Rotation.
10
Active/Path: Nodes being visited or compared.

Waiting for Action...

Select an operation above (Insert, Delete, or Search) to see how the tree structure changes and how rotations are triggered.

What is an AVL Tree?

An AVL Tree (named after Adelson-Velsky and Landis) was the first self-balancing Binary Search Tree (BST) to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. If at any time they differ by more than one, rebalancing is performed to restore this property.

This self-balancing property ensures that the tree height remains O(log n), guaranteeing efficient Search, Insert, and Delete operations even in the worst case (unlike a standard BST which can degenerate into a linked list).

Time Complexity

  • SearchO(log n)
  • InsertO(log n)
  • DeleteO(log n)
  • Space ComplexityO(n)

Balancing Rotations

  • Balance Factor (BF)Calculated as Height(Left) - Height(Right). Valid values are -1, 0, 1.
  • Single RotationsLeft (LL) and Right (RR) rotations fix simple imbalances.
  • Double RotationsLeft-Right (LR) and Right-Left (RL) rotations fix complex "dog-leg" imbalances.

Concept guide

Review the mental model, tradeoffs, and practical use cases after you experiment.

AVL Tree Complete Info Card

Self-BalancingHeight-Balanced

The AVL Tree is a self-balancing BST that maintains strict height balance through rotations. Guarantees O(log n) operations by ensuring the height difference between left and right subtrees (balance factor) never exceeds 1. Ideal for lookup-intensive applications.

AVL Properties

Search Complexity

Guaranteed height balance

O(log n)

Insert/Delete (Worst)

Self-balancing property

O(log n)

Space Complexity

Node storage + balance factors

O(n)

Balance Factor

Height difference constraint

±1

Rotation Types

LL, RR, LR, RL

4

Height Guarantee

Strict balance bound

1.44 log(n)

Balancing Operations

1

Insert/Delete: Standard BST operation

2

Update height of ancestor nodes

3

Check balance factors bottom-up

4

Perform rotations if imbalance > ±1

5

Maintain balance through rotations

Comparison with Other Trees

StructureAdvantagesTrade-offs
Red-Black TreeFewer rotationsLess strict balance
Splay TreeSelf-optimizingNo height guarantee
B-TreeDisk optimizationComplex implementation
TreapProbabilistic balanceRandom priority management
Scapegoat TreeNo balance factorsRebuild operations

Optimal Use Cases

  • •Real-time systems requiring predictable performance
  • •Lookup-intensive applications
  • •Scenarios needing worst-case guarantees

When to Avoid

  • •Write-heavy workloads
  • •Memory-constrained environments
  • •When approximate balance suffices
Pro Tip: Prefer AVL Trees over Red-Black Trees when faster lookups are critical. Use Red-Black Trees when insertions/deletions are more frequent and strict balance is less important.
Strict BalanceGuaranteed O(log n)Rotation Operations