Trees that balance themselves

Lean to one side and it slows down

Earlier we learned a tree finds things fast
by halving the search down its branches.
Each step down from top to bottom
cuts the range to look at in half.
But what happens if you insert values
only in order, smallest first?
Every new value clings to one side,
so the branches never split
and stretch into one long line.

Insert values one by one. It grows long on one side into nearly a line, and the steps to find shoot up.

A tree stretched into one line
really has almost no branching.
Going down does not cut the range in half;
it shaves off just one each time.
Then, to find a value at the far end,
you must count one by one from start to finish.
The tree we built to find things fast
has instead become slow.
Like this, there is no point in using a tree.

Keep both sides about the same depth

Even with the very same values,
shaping it well changes the story.
Instead of piling onto one side,
put a middle value on top,
smaller values to the left, larger to the right,
splitting the branches to both sides.
Then each step down from the top
really does cut the range in half.
A tree with both sides at similar depth like this
is called a balanced tree.

Same values either way. Tap the skewed tree and the balanced tree to compare depth. Which reaches the bottom sooner?

With the same count,
the balanced tree is far shallower.
Shallow means fewer steps to the bottom,
which means finding is fast.
But even if it starts well balanced,
as you keep inserting and removing values
one side can slowly grow heavier.
We cannot rebuild it by hand each time,
so the tree should fix itself, right?

Rebalance with a rotation

When one side gets heavy,
the tree shifts the nodes' seats a little.
It lifts a node from the heavy side up
and lowers the one that was on top by one step.
Then the weight piled on one side
splits to both sides and balances again.
This re-seating
is called a rotation.
It keeps the ordering rule intact
and only straightens the shape.

This tree is heavy on the right. Tap rotate. The middle node rises to the top and the two sides balance out.

With a single rotation
the lopsided tree straightened up.
Only a few nodes changed seats,
yet both sides are at similar depth again.
What matters is that the ordering rule of values
was not disturbed at all.
The left is still small, the right still large.
Only the shape changed; the promise held,
so finding works just as well.

Depth is guaranteed, however much there is

Keeping balance with a rotation
on every insert and remove has a payoff.
No matter how much data piles up,
the tree's depth grows only slowly.
Even when the count doubles,
the depth grows by just one more step.
This slow growth is called log.
So whether there are a hundred values or a million,
it always guarantees a find within a few steps.

Grow the data count. The skewed tree's depth climbs just as much, but the balanced tree deepens slowly, one step at a time.

The skewed tree's depth shot up
right along with the growing data.
But the balanced tree,
even as the data multiplied,
kept its depth almost the same.
This very difference
is what makes a balanced tree dependable.
No matter how much data comes,
you can trust it to find things fast.

Let's wrap up

Gathered on one line, it is this.
If a tree grows on one side only
it becomes nearly a line and slows down.
A balanced tree keeps both sides at similar depth.
When one side gets heavy on insert or remove
it re-seats things with a rotation.
Thanks to that, however much data there is,
the depth grows slowly (log)
and always guarantees a find within a few steps.

Tap the key points in order to review. (lean = slow -> keep sides even -> re-seat by rotation -> guaranteed by log)

Now you know how a tree
keeps its own balance.
This was its secret for not losing
fast finding even while inserting and removing.
We only have to hand over the values,
and the tree tidies its shape by itself.
The tricky rotations we leave to the tree,
and we just enjoy the fast finding.