Chapter 11. Where to go next
- You get a brief overview of 10 algorithms that weren’t covered in this book, and why they’re useful.
- You get pointers on what to read next, depending on what your interests are.
Let’s go back to the binary search example. When a user logs in to Facebook, Facebook has to look through a big array to see if the username exists. We said the fastest way to search through this array is to run binary search. But there’s a problem: every time a new user signs up, you insert their username into the array. Then you have to re-sort the array, because binary search only works with sorted arrays. Wouldn’t it be nice if you could insert the username into the right slot in the array right away, so you don’t have to sort the array afterward? That’s the idea behind the binary search tree data structure.
A binary search tree looks like this.
For every node, the nodes to its left are smaller in value, and the nodes to the right are larger in value.
Suppose you’re searching for Maggie. You start at the root node.
Maggie comes after David, so go toward the right.
Maggie comes before Manning, so go to the left.
