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.
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.
Neo and Byte are the hosts of our YouTube series — made entirely of pixels.
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.
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.
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 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.