Narrowing down in a tree shape

Data splits into branches

Earlier we learned how to
line data up in a single row.
A row looks neat,
but to find a value in the middle
you sometimes walk all the way from an end.
So this time we change the shape.
Put one root at the top
and split it into two branches.
From each branch, two more.
This splitting shape is called a tree.

Tap the root to unfold branches. Each tap splits one more level.

The more it splits, the faster the spots grow.
Each level doubles the branches.
But why is this shape
good for searching?
The secret is in which way it splits.
When you pick a branch from the root
you do not go just anywhere,
you keep a rule and pick one side.
Let's see that rule next.

Each step halves the search

When you place values in a tree
you set one rule.
Values smaller than a spot go to the left branch,
bigger ones go to the right branch.
Then searching gets very easy.
If your target is smaller than the current spot
you drop the whole right side and look only left.
If bigger, you drop the whole left side instead.
With each single choice,
half of the remaining candidates disappear.

Compare the target with the current spot: tap left if smaller, right if bigger. Each tap halves the remaining candidates.

With each choice,
the candidates dropped to half.
A dropped branch never needs another look.
Thanks to the rule you know
the answer cannot be inside it.
So no matter how many spots,
a few choices narrow it down fast.
Then shall we pick a real target
and follow it from the root?

Found in just a few steps

Now pick one target value
and follow it from the root.
Compare the root spot with the target
and by the rule go down left or right.
At that branch compare again and go down again.
Until you reach the target spot
you repeat the same thing.
Count how many steps it takes,
and the surprisingly small number will amaze you.

Set a target and follow down from the root one spot at a time. It counts how many steps it takes.

Even a seven-spot tree
took at most three steps to reach.
If they were in one row
the last value would need seven looks.
Thanks to the tree shape
we found it with far fewer looks.
So if there are many more spots,
does the step count shoot up too?
Let's grow it ourselves next.

Depth is the number of steps

The depth of a tree
is the number of steps from root to bottom.
That is also the most steps
a search can ever take.
The fun part: even if you double the spots,
the depth grows by just one step.
Double again, one more step.
So even when data grows enormous
the step count rises very slowly.
This slow deepening we say
grows like a logarithm.

Tap to double the number of spots. The spots jump, but the depth (steps) grows just one step at a time.

Even when spots go from a thousand to two thousand
the depth grew by only one step.
A million spots
are reached within about twenty steps.
This is the real power of the tree shape.
No matter how data swells,
the steps to find barely grow.
That is why, for large data,
the tree shape is used so often.

Let's wrap up

Gathered on one line, it is this.
Put data in a branch shape, a tree.
With the rule smaller left, bigger right,
each step halves the candidates.
So even thousands are found in a few steps.
The number of steps, the depth, is the speed.
When data doubles
the depth grows by just one step.
It is just like opening a dictionary
at the middle and narrowing by half.

Tap the key points in order to review. (splits into branches -> halve each step -> found in a few steps -> depth is the steps)

Now you know why putting data
in a tree shape finds things fast.
But one thing nags a little.
If the order you insert values is bad,
the tree can grow long to one side,
a lopsided tree.
Then the charm of halving fades.
How can we keep a tree
even on both sides?
Let's see that balance story in the next lesson.