ABC Tools

Data Structure Visualizer, Explained

After reading this you will know why the seven classic data structures balance, rehash, and flatten the way they do, and you will be able to predict each animation step before it plays.

What these seven structures actually solve

Every data structure here answers one question: given a pile of keys, how fast can you find, insert, or delete one? The naive answer is a plain array or linked list, where a search scans every element. With 1,000,000 keys that is 1,000,000 comparisons in the worst case. The structures in this tool cut that to about 20 comparisons or fewer, because they organize keys instead of storing them in arrival order.

The hook is a binary search tree. Insert the keys 50, 30, 70, 20, 40 and the tree branches: 30 goes left of 50, 70 goes right, 20 and 40 hang off 30. A search for 40 touches 3 nodes (50, 30, 40) instead of scanning 5. That is the whole idea, repeated with different guarantees: a plain BST can degrade to a line, an AVL tree and a red-black tree refuse to, a heap keeps only the extreme element cheap, a hash table skips ordering entirely, a trie shares prefixes, and union-find tracks which keys belong to the same group.

When each one fits, and when it does not

Pick by the operations you need most.

Binary search tree
Teaching baseline. Good when keys arrive randomly, terrible when they arrive sorted: inserting 1, 2, 3, 4, 5 in order builds a chain of depth 5, so search is O(n), not O(log n).
AVL tree
Strictly balanced. Height stays within 1.44 times \log_2 n, so lookups are fast, but inserts and deletes may rotate often. Choose it when reads dominate.
Red-black tree
Loosely balanced, height up to 2\log_2(n+1). Fewer rotations per write than AVL, so it wins when writes are frequent. This is what std::map and Java's TreeMap use.
Min-heap
Only the minimum is cheap: O(1) to peek, O(log n) to remove. Use it for priority queues. Do not use it to search for an arbitrary key, which costs O(n).
Hash table
Average O(1) lookup with no ordering. Use it when you never need keys in sorted order and can tolerate the occasional rehash pause.
Trie
Prefix queries and autocomplete. Storing cat, car, card shares the ca path, so a prefix search for car follows 3 edges.
Union-find
Grouping and connectivity. It answers "are these two in the same set?" in near-constant time, but it cannot enumerate a set's members.

The balance math that keeps trees short

A binary tree with n nodes has height somewhere between \log_2(n+1) (perfectly balanced) and n (a chain). Search cost equals height, so balance is the whole game. The AVL invariant is the strictest rule the tool enforces:

|h(\text{left}) - h(\text{right})| \le 1

Here h(\text{left}) and h(\text{right}) are the heights of a node's two subtrees, and the balance factor is their difference. Whenever an insert or delete pushes any node's balance factor to \pm 2, the AVL tree rotates to restore the rule. The four rotation cases are named by the path to the offending node: LL, LR, RL, RR. The tool labels each one as it fires.

The red-black tree relaxes this into five color rules that together guarantee no root-to-leaf path is more than twice as long as any other. That looser bound is why red-black trees rotate less. The practical difference: to insert one key, an AVL tree may do up to 2 rotations, a red-black tree at most 3, but red-black recoloring often fixes a violation with 0 rotations, just color flips.

The hash table load factor and the cost of amortized O(1)

A hash table stores n keys in m buckets. The load factor is the ratio:

\alpha = \frac{n}{m}

With chaining, the expected number of keys per bucket is \alpha, so an average lookup touches 1 + \alpha slots. At \alpha = 0.75 that is 1.75 slots per lookup, still effectively constant. Let \alpha climb to 5 and every lookup averages 6 slots, which is no longer fast.

This tool doubles m the moment \alpha passes 0.75, then rehashes every key one step at a time. That single rehash of n keys costs O(n). Spread across the n cheap inserts that preceded it, the average per insert stays O(1). Watching the rehash play out is the point: the "amortized" in "amortized O(1)" is a real pause you can see.

Linear probing degrades faster than chaining as \alpha rises. At \alpha = 0.9 the expected probes for an unsuccessful search under linear probing is about \frac{1}{2}(1 + \frac{1}{(1-\alpha)^2}) = 50.5, versus 1.9 for chaining. Keep probing tables below \alpha = 0.7.

A worked example you can reproduce

Building the default AVL tree

Load the tool's defaults and insert the keys in this order: 50, 30, 70, 20, 40, 10. Here is what the AVL tree does at each step.

  1. Insert 50. It becomes the root. Height 1, balance factor 0.
  2. Insert 30. Goes left of 50. No violation.
  3. Insert 70. Goes right of 50. Tree is perfectly balanced, height 2.
  4. Insert 20. Goes left of 30. Still balanced: 50 has left height 2, right height 1, balance factor 1.
  5. Insert 40. Goes right of 30. Node 30 now has both children, tree stays balanced.
  6. Insert 10. Goes left of 20. Now node 50 has left subtree height 3, right subtree height 1, balance factor 2. The path to the new node went left-left, so this is an LL case. A single right rotation at 50 fixes it: 30 becomes the root, 50 becomes 30's right child.

Before the rotation the tree had depth 4 on its left side. After the LL rotation the whole tree has height 3, and a search for any of the 6 keys touches at most 3 nodes. Step backward once in the tool to see the unbalanced state, then forward to watch the rotation reattach the subtrees.

As the load factor rises from 0.10 to 0.95, expected probes for an unsuccessful lookup grow slowly under chaining (from about 1.1 to 1.95) but explode under linear probing (from about 1.1 to 200.5). The two curves stay close until roughly 0.7, then linear probing turns sharply upward.

Reading the animations correctly

Colors and labels carry the meaning. In the red-black view, red and black are the invariant, not decoration: a red node may never have a red child, and every root-to-leaf path must cross the same number of black nodes. When you delete and the tool marks a node "double-black," it is showing the CLRS fix-up in progress, resolving one of four cases before the tree is legal again.

In union-find, watch the height. Union by rank attaches the shorter tree under the taller one, so combining two trees of height 2 gives height 3 at most. Then the first find on a deep node triggers path compression: every node on the lookup path is reparented straight to the root. A chain of 5 nodes collapses to depth 1 in a single find. Combined, these two tricks give an amortized cost per operation of O(\alpha(n)), where \alpha(n) is the inverse Ackermann function, below 5 for any n you could ever store.

Balanced trees keep height near 20 to 40. A BST fed sorted keys degrades to a chain of 1,000,000, the disaster balance prevents.

Common mistakes

The mistakes below show up constantly when people first work with these structures.

  • Inserting sorted keys into a plain BST. The tree becomes a linked list. Search goes from O(log n) to O(n). If your keys arrive in order, use AVL or red-black.
  • Treating a heap as a search tree. A min-heap only orders parent below children, not left below right. Finding an arbitrary key still scans O(n) nodes.
  • Letting a probing hash table fill up. Past \alpha = 0.9, linear probing clusters and every insert scans dozens of slots. Resize early.
  • Forgetting the rehash pause. Amortized O(1) does not mean every insert is fast. The one that triggers the doubling is O(n). In a latency-sensitive path that single insert can blow your p99.

When a rotation or fix-up plays too fast, step backward and forward one snapshot at a time. Each operation is stored as a list of frames, so you can inspect the exact moment a balance factor hit \pm 2 or a path compressed.

Related tools

The rehash pause connects directly to the Tail Latency & Autoscaling Simulator, where one slow operation drags p99 upward. Hashing keys onto a ring instead of into buckets is the subject of the Consistent Hashing Ring, which shows why adding a server moves only 1/N of the keys. For a probabilistic set that trades exactness for space, see the Bloom Filter Playground. If eviction interests you more than insertion, the Cache Replacement Simulator animates LRU, LFU and friends on any access sequence.

Frequently asked questions

Why choose a red-black tree over an AVL tree?

Red-black trees rotate less on writes. An AVL insert may cost up to 2 rotations and a delete up to \log n rotations, while a red-black insert needs at most 3 rotations and a delete at most 3. If your workload writes often, red-black wins. If it reads far more than it writes, AVL's tighter height (1.44 vs 2.0 times \log_2 n) gives slightly faster lookups.

What load factor should a hash table use?

For chaining, 0.75 is a standard threshold and the default here. For open addressing like linear probing, stay below 0.7, because probe counts grow with \frac{1}{(1-\alpha)^2} and become severe past 0.9.

Is path compression alone enough for union-find?

Path compression alone gives amortized O(\log n) per operation. Adding union by rank drops that to near-constant O(\alpha(n)). This tool uses both, so you can watch a tall tree flatten and stay flat.

Does anything I type leave my browser?

No. Every structure is built and animated locally in your browser. Nothing you paste is sent anywhere.

Why does the demo tree rotate on the sixth insert but not the fifth?

After inserting 50, 30, 70, 20, 40 the root's balance factor is still 1, inside the AVL limit. Inserting 10 pushes it to 2, which violates the invariant and triggers the single LL rotation described in the worked example.

Try it yourself in the tool

Related tools

Bloom Filter Playground

Add items, watch bits light up, measure the false positive rate.

Cache Replacement Simulator

Animate FIFO, LRU, LFU, CLOCK, ARC and Bélády's OPT on any access sequence.

Consistent Hashing Ring

See why adding a server moves 1/N of the keys, not all of them.

Digital Logic Gate Simulator

Build circuits from gates and flip-flops, wire them up, and watch the signals flow live.

Git Branching Sandbox

Type git commands and watch the commit DAG, branches and HEAD move — with levels, remotes, undo, and merge-vs-rebase contrast.

IEEE-754 Floating Point Explorer

Flip the bits of a float and see why 0.1 + 0.2 ≠ 0.3.