AVL Tree Visualization: Insert Your Own Keys

Press + and pick a key from 0 to 99 on the slider, or press Random for a new tree. The insertion plays step by step: every comparison on the way down, the new node, and every rotation that brings the tree back into balance. Here you can insert keys; deleting them, with the rotations that follow, is explained step by step in the VisiGrab app.

392635475564768491

Byte I inserted 20 keys and watched the tree spin around. Looked cool. No idea why it rotated.

Neo That’s what the app is for — every rotation, step by step, explained.

App StoreGoogle Play
QR code for VisiGrab on your phone
Scan to install

Neo and Byte are the hosts of our YouTube series — made entirely of pixels.

How to use this AVL visualizer

Press + and pick a key on the slider, then step through the insertion with →. The way down is the same as in a binary search tree: each node it passes gets a blue ring, the link it takes turns blue, and the comparison that chose the way is written on that link. A dotted line then shows where the new node goes, and the next step joins it to the tree.

If a node is now out of balance, it turns red with its balance factor above it, and everything outside its subtree fades. An orange arrow at a node shows the rotation about to happen there, and the next step turns the nodes. Once the tree is balanced again, every node shows its balance factor until the insertion ends. Levels draws and numbers the tree's levels. History lists the keys in the order they went in, to download and load again later: the same keys in the same order always build the same tree.

How does insertion in an AVL tree work?

It starts as in a binary search tree: the new key goes down from the root, left where it is smaller than a node and right where it is larger, and becomes a new leaf. Then the nodes on its way are checked, from the new leaf back up to the root. The lowest node whose balance factor has become 2 or −2 is rotated, and after that the whole tree is balanced again: an insertion needs at most one single or one double rotation. More in how an AVL tree works.

What do the numbers above the nodes mean?

Each is the node's balance factor: the height of its left subtree minus the height of its right subtree. In an AVL tree it is −1, 0 or 1 at every node, and 1 means the left side is one level taller. An insertion can make it 2 or −2 at nodes on the new key's way, and a rotation brings it back.

When does the tree rotate twice?

When the new key's way bends below the unbalanced node: left there and then right, or right and then left. One rotation would only bend it the other way, so the first rotation straightens the way at the child, and the second turns the unbalanced node. To see it, press Clear and insert 30, 10 and 20.