Is this a real AVL tree?

Yes — a real, correct self-balancing AVL tree, with genuine single and double rotations.

How is this different from a plain BST?

A real AVL tree actively rebalances after every insert, so it never degrades into a long chain the way a plain BST can.

No — it is a pure local computation.

Yes — free, no download, in your browser.

What is a tree rotation?

It is a local restructuring in which a node and one of its children swap roles, keeping the sorted order intact. It changes heights without changing which values are stored.

How does an AVL tree compare with a red-black tree?

Both do inserts, deletes and lookups in logarithmic time. AVL trees are more strictly balanced, so they are generally faster for lookup-heavy use, while red-black trees need less balance information stored per node.

Why does balance affect speed?

Search time follows the height of the tree. A balanced tree with a million items is about twenty levels tall, while a degenerate one could be a million deep.

AVL Tree Rotations Screensaver

The AVL Tree Rotations screensaver grows a real self-balancing AVL tree, performing genuine single and double rotations whenever an insert tips it off balance. It is free, runs in your browser, and ESC exits.

How the AVL Tree Rotations screensaver works

The saver inserts real random values into an AVL tree, a binary search tree that tracks the real height balance of every node.

Whenever an insert makes a node's left and right subtree heights differ by more than one, a real rotation — single or double — fires to restore balance.

Each rotation is drawn live as the actual pivot it is, re-parenting a real subtree rather than just relabeling values.

Once the tree reaches a set size, it holds briefly, then clears and a fresh AVL tree begins growing from empty.

The first self-balancing binary search tree

The AVL tree was published in 1962 by two Soviet mathematicians, Georgy Adelson-Velsky and Evgenii Landis, whose initials give the structure its name. It was the first self-balancing binary search tree to be invented.

Balance matters because a plain binary search tree can degenerate. Insert numbers that are already in order and the tree turns into a long chain, so searching takes time proportional to the number of items rather than its logarithm. An AVL tree prevents this by tracking a balance factor at each node, the difference between the heights of its two subtrees, and requiring it to stay at −1, 0 or 1. When an insert or delete pushes a node to ±2, the tree is repaired by rotations, local rearrangements that preserve the sorted order while lifting one subtree and lowering another.

There are four cases, called left-left, right-right, left-right and right-left. The first two need a single rotation and the other two need a double rotation. The height of an AVL tree with n items is at most about 1.44 times the base-two logarithm of n, so lookups, inserts and deletes all run in logarithmic time. Red-black trees are balanced less strictly than AVL trees, which makes AVL trees somewhat faster for lookups.

A worked example

Three values inserted in increasing order would make a plain BST lean into a straight line, but the real AVL tree instead performs a single rotation, snapping back into a balanced shape.

Settings & tips

Accent recolours the node currently rotating.
This is a real, correct self-balancing AVL tree implementation.
The tree clears and regrows automatically once it reaches full size.

Frequently asked questions

Is this a real AVL tree?: Yes — a real, correct self-balancing AVL tree, with genuine single and double rotations.
How is this different from a plain BST?: A real AVL tree actively rebalances after every insert, so it never degrades into a long chain the way a plain BST can.
Is a key needed?: No — it is a pure local computation.
Is it free?: Yes — free, no download, in your browser.
What is a tree rotation?: It is a local restructuring in which a node and one of its children swap roles, keeping the sorted order intact. It changes heights without changing which values are stored.
How does an AVL tree compare with a red-black tree?: Both do inserts, deletes and lookups in logarithmic time. AVL trees are more strictly balanced, so they are generally faster for lookup-heavy use, while red-black trees need less balance information stored per node.
Why does balance affect speed?: Search time follows the height of the tree. A balanced tree with a million items is about twenty levels tall, while a degenerate one could be a million deep.

← All Science & Research screensavers