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, then the new node in its place. Here you can insert keys; deleting them, in all three cases, is explained step by step in the VisiGrab app.
Byte So the new key just walks down until it finds a free spot?
Neo Pretty much. And what happens when you delete one — that’s in the app.
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 →. It starts at the root and goes down one level per step: 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 last step joins it to the tree.
Levels draws and numbers the tree's levels; this simulator stops at six, and a key that would need a seventh is marked red on the slider. 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.
The new key is compared with the root. If it is smaller, it goes to the left child, if larger, to the right, and the same choice repeats at every node until there is no child on that side. There the key becomes a new leaf, and nothing else in the tree moves. More in how a binary search tree works.
A binary search tree keeps every key once, so this visualizer will not insert a key twice: on the slider its node turns yellow, and the line under the tree says the key is already there.
Its shape depends on the order the keys arrive in. Press Clear and insert 10, 20, 30, 40 and 50: each key is larger than all before it, so each goes right, and the tree turns into a chain with one key per level, as slow to search as a list. An AVL tree avoids this by rotating its nodes after an insertion: insert the same keys in the AVL tree visualizer.