VISUALISERS · FOUNDATIONS
AVL tree visualiser
The AVL tree answers what does keeping it balanced actually buy?
PLAIN TREE HEIGHT
5
AVL TREE HEIGHT
3
5 values, in this insertion order: the plain tree stands 5 levels tall, the AVL tree 3. Inserting 50 unbalanced the AVL tree, so it rotated: right-right, rotated left.
Each press of “Add values in order” appends a short run of ascending values, so the plain tree gains a level per value while the AVL tree rotates and stays close to log n. Three presses fill the figure at twelve values; after that the control reports that it is full instead of inserting, and Reset starts the sequence again.
What a rotation actually does
After every insert the tree checks one thing: does any node now have one side more than a level taller than the other? If so, that node is rotated — its subtrees are re-hung so the taller side gives a level back.
Which way it turns depends on where the new value landed. Two levels down the same side, left-left or right-right, is one turn against that side. Down one side and back the other, left-right or right-left, needs two: the lower node is turned first to make the imbalance straight, then the upper one is turned as before.
That is the whole difference between the two trees above. Both hold the same values in the same order; only one of them pays a few pointer swaps per insert to keep its height near the minimum.
Want an explanation to go with the picture? Find a guided starting point →