How to Use the AVL Tree Visualizer
Enter an integer and select Insert to add it to the tree. The visualizer places the value according to binary search tree rules, updates the height and balance factor of each affected node, and automatically performs a rotation when the tree becomes unbalanced.
Use Delete to remove an existing value, Search to follow the comparison path to a node, Random Tree to create a sample AVL tree, or Clear Tree to start again. You can also load one of the LL, RR, LR, or RL examples to see a specific rotation in action.
Steps to Get Started:
- Enter a whole number in the input box.
- Select Insert, Delete, or Search.
- Watch the highlighted traversal path in the canvas.
- Check each node’s height and balance factor badges.
- Observe the structural rotation when a balance factor becomes less than -1 or greater than 1.
What This AVL Visualization Shows
This interactive AVL tree visualization is designed to show more than the final tree. It helps you follow how an AVL operation changes the structure step by step.
- Binary search tree insertion paths (highlighted dynamically)
- AVL tree deletion and rebalancing routines
- Node heights and balance factors updated in real-time
- LL, RR, LR, and RL rotations
- Search traversal paths from root to leaf
- Automatic balancing after updates
- A visual, non-shifting operation log terminal
- Example rotation sequences
Try the Four AVL Tree Rotations
An AVL tree uses four rotation cases. Load the examples below to see why the imbalance occurs and how the tree is repaired. You can trigger these examples directly using the buttons in the visualizer panel.
LL Rotation (Left-Left Case)
Insert 30, 20, and 10. Node 30 becomes left-heavy because the new value was added to the left subtree of its left child. A single right rotation makes 20 the new root of the subtree.
RR Rotation (Right-Right Case)
Insert 10, 20, and 30. Node 10 becomes right-heavy because the new value was added to the right subtree of its right child. A single left rotation makes 20 the new root of the subtree.
LR Rotation (Left-Right Case)
Insert 30, 10, and 20. The new value is added to the right subtree of the left child. The tree performs a left rotation on node 10 followed by a right rotation on node 30.
RL Rotation (Right-Left Case)
Insert 10, 30, and 20. The new value is added to the left subtree of the right child. The tree performs a right rotation on node 30 followed by a left rotation on node 10.
What Is an AVL Tree?
An AVL tree is a self-balancing binary search tree. It was named after Georgy Adelson-Velsky and Evgenii Landis, who introduced the data structure in 1962.
Like a standard binary search tree, values smaller than a node are stored in its left subtree and larger values are stored in its right subtree. The difference is that an AVL tree continually checks its height balance after insertions and deletions.
For every node, the heights of the left and right subtrees may differ by no more than one. When that condition is broken, the AVL tree uses one or two rotations to restore balance.
Because its height stays logarithmic, searching, inserting, and deleting values take O(log n) time in the worst case.
AVL Tree Balance Factor
The balance factor tells us whether a node is balanced, left-heavy, or right-heavy.
Using this formula, we classify each node as:
- Balance factor -1: right-heavy but balanced
- Balance factor 0: perfectly balanced at that node
- Balance factor +1: left-heavy but balanced
- Balance factor less than -1: right-heavy and requires rebalancing
- Balance factor greater than +1: left-heavy and requires rebalancing
AVL Tree Operations and Time Complexity
| Operation | Average Time | Worst-Case Time |
|---|---|---|
| Search | O(log n) | O(log n) |
| Insertion | O(log n) | O(log n) |
| Deletion | O(log n) | O(log n) |
| Traversal | O(n) | O(n) |
AVL trees maintain logarithmic height by rebalancing after updates. A search follows the same comparison process as a binary search tree. Insertion and deletion may additionally update heights and perform rotations while returning toward the root.
Traversal visits every node, so inorder, preorder, and postorder traversals take O(n) time.
AVL Tree vs. Ordinary Binary Search Tree
An ordinary binary search tree can become skewed when values are inserted in sorted order. In the worst case, it can behave like a linked list and require O(n) time for a search.
An AVL tree prevents this problem by maintaining a strict height-balance rule. That produces more predictable O(log n) search, insertion, and deletion performance.
AVL Tree vs. Red-Black Tree
| Feature | AVL Tree | Red-Black Tree |
|---|---|---|
| Balance rule | Stricter height balance | Less strict color-based balance |
| Search paths | Often shorter | May be slightly taller |
| Update rotations | May rebalance more frequently | Often fewer rotations |
| Typical strength | Lookup-heavy workloads | Update-heavy workloads |
| Worst-case search | O(log n) | O(log n) |
Both AVL trees and red-black trees are self-balancing binary search trees. Neither structure is universally faster in every real application. AVL trees maintain stricter balance, while red-black trees generally allow more flexibility during updates. The better choice depends on the implementation and workload.