What is a tree data structure
When you look up a word in a thick dictionary, you do not turn the pages one by one from the start. You open it in the middle, decide whether your word comes before or after, then open the middle of that half. Arrange data in a branching shape and you can do the same, because each step down cuts the candidates to check in half.
Data splits into branches
Earlier we saw how to lay data out in a single row. A row looks neat, but to find the value you want, you sometimes have to scan all the way from one end.
So this time, let's change the shape. Put one root at the top and let two branches grow from it, then two more from each of those. A shape that splits like this is called a tree, and each place that holds a value is called a node; in this lesson we call it a spot.
Tap the root to unfold the branches. Each tap splits them one level further.
The more it splits, the faster the spots multiply: each level down doubles the number of spots.
But why is this shape good for searching? The secret lies in which way you branch. When choosing a branch from the root, you do not go just anywhere; you follow a rule and pick only one side. Let's look at that rule next.
Halving the search at every step
When placing values in the tree, you set one rule: values smaller than a spot go in its left branch, and larger values go in its right branch. A tree that keeps this rule is called a binary search tree.
That makes searching very easy. If the value you want is smaller than the current spot, you throw away the whole right side and look only left. If it is larger, you throw away the whole left side instead. Each choice gets rid of half the remaining candidates.
Compare the target with the current spot and tap left if it is smaller, right if it is bigger. Each tap halves the candidates left.
Each choice cut the candidates in half. The branches you threw away never need to be checked again, because the rule tells you the answer is not in them.
So however many spots there are, a few choices narrow things down quickly. Now let's pick a real target and follow it down from the root.
Found in a few steps
Now choose one target value and follow it from the root. Compare the root with the target and go down left or right according to the rule. At that branch, compare again and go down again.
Repeat the same thing until you reach the target. If you count how many steps it takes, you will be surprised how few there are.
Choose a target and follow it down from the root one spot at a time. The number of steps it takes is counted as you go.
Even in a tree with seven spots, it took at most three steps. Laid out in a single row, the value at the end would have needed seven checks.
Thanks to the tree shape, you found it while looking at far fewer. So when there are more spots, does the number of steps grow just as much? Let's grow the tree and see.
Depth is the number of steps
The depth of a tree is the number of steps from the root to the bottom. That is also the largest number of steps a search can take.
The interesting part is that doubling the spots adds only one step of depth. Double them again, and it is one more step. So even when the data becomes enormous, the number of steps grows very slowly. Growing by one step each time the size doubles like this is called logarithmic growth.
Tap to double the number of spots. The spots shoot up, but the depth (the number of steps) grows slowly, one step at a time.
Even when the spots went from a thousand to two thousand, the depth grew by just one step. Even with a million spots, you get there in under twenty steps.
That is the real power of the tree shape. However much the data grows, the steps to find something barely increase. That is why trees are used so often for large data.
Summary
In short: you arrange data in a branching shape, a tree. Thanks to the rule of smaller to the left and bigger to the right, each step halves the candidates.
So even among thousands, you find a value in a few steps. The number of steps, that is, the depth, sets the speed. When the data doubles, the depth grows by just one step. It is exactly like opening a dictionary in the middle and halving your search.
Tap the key points in order to review. (data splits into branches → halve each step → found in a few steps → depth = steps)
Now you know why arranging data as a tree makes searching fast. But there is one catch. If values are put in a bad order, for example from smallest to largest, the tree becomes lopsided, stretching out long on one side only.
Then the advantage of halving disappears, and it is no better than scanning a row. The next lesson covers how a tree evens out both sides by itself.