What is a balanced tree

Leaning to one side makes it slow

In a tree, each step down halves the range left to check. But what happens if you insert values only in order, from smallest to largest?
Each new value is larger than everything inserted so far, so it always attaches at the far right. The branches stop splitting and the tree stretches into one long line. It is a tree in name only; in shape, it is the same as the single row we saw earlier.

Insert the values in order. The tree grows long on one side until it is almost a line, and the steps to find a value shoot up.

A tree stretched into one line has practically no branches. Going down from the top, the range shrinks not by half but by just one each step.
So to find the value at the end, you have to count one by one from start to finish. A tree built to find things quickly has ended up slow. That defeats the purpose of using a tree.

Keeping both sides at about the same depth

Even with the same values, a better shape changes everything. Instead of piling everything on one side, you put the middle value at the top and branch the smaller values to the left and the larger values to the right.
Then each step down truly halves the range left to check. A tree that keeps both sides at about the same depth like this is called a balanced tree.

These two trees are made from the same values. Tap the lopsided tree and the balanced tree to compare their depth. Which one reaches the bottom sooner?

The count is the same, but the balanced tree is much shallower. Shallower means fewer steps to the bottom, which means faster searching.
But even a tree that starts out well balanced can slowly grow heavy on one side as values keep going in and out. Nobody can rebuild it by hand each time, so the tree has to fix itself.

Rebalancing with rotations

When one side gets heavy, the tree slightly rearranges a few nodes. It lifts a node from the heavy side up and moves the node that was above it down one level.
Then the weight that had piled up on one side is shared between both, and the tree is balanced again. Rearranging like this is called a rotation. It fixes only the shape, while still keeping the order rule that smaller values go left and larger ones go right.

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

One rotation turned the lopsided tree upright. Only a few nodes moved, yet both sides are about the same depth again.
The key point is that the order rule was not disturbed at all: the left side is still smaller and the right side still larger. Only the shape changed and the promise held, so searching works just as well. There are several kinds of trees that keep their balance this way, each with slightly different rules for judging balance.

Depth is guaranteed, however much data

Keeping the balance with rotations on every insert and delete has a big benefit: however much the data grows, the tree's depth grows only slowly.
Even when the count doubles, the depth gets just one level deeper. As we saw in the last lesson, growing slowly like this is called logarithmic. So whether there are a hundred values or a million, you can always find one within a few steps.

Increase the amount of data. The lopsided tree's depth grows as fast as the data, but the balanced tree deepens slowly, one level at a time.

As the data grew, the lopsided tree's depth shot up along with it. But the balanced tree's depth stayed almost the same even when the data grew several times over.
It is exactly this difference that makes balanced trees dependable: however much data comes in, you can trust that searching will stay fast.

Summary

In short: a tree that grows on one side only becomes almost a line and slows down. A balanced tree keeps both sides at about the same depth.
When one side gets heavy during inserts and deletes, it rearranges itself with rotations. Thanks to that, however much data there is, the depth grows slowly (log), so you can always find a value within a few steps.

Tap the key points in order to review. (lopsided is slow → keep both sides even → rearrange by rotation → guaranteed by log)

Now you know how a tree keeps its own balance. That is the secret to staying fast to search even while values go in and out. We just hand over the values, and the tree takes care of the rotations.
Database indexes are built from balanced trees like these too, but they use wide, shallow trees in which each node holds several values and has a great many branches. The next lesson looks at how such indexes are actually used in a database.