Understanding Binary Search Trees
When considering whether to buy hardware or software, one of the most important considerations is often speed. We buy new servers because they will be faster. We buy new programs because we think they will offer a faster, more streamlined experience. When it comes to computers, speed is king.
How do we make things faster? Speed and optimization are huge, foundational fields in computer science, and hundreds of PhDs have been awarded over the decades to those who have made advances here. As such, we know quite a lot about programs and how to make them faster. In this post, we are going to discuss one such optimization, a “binary search tree”.
A binary search tree is a tool used to make finding things faster — a lot faster. Even better is that the more data you have, the more of a speed bump you get. Before discussing how a BST works, let’s set up our problem:
We have a bunch of things we want to search through; let’s say we have “n” things. We know what we want, but we don’t know where to find it. We could begin looking through what we’ve got, one at a time, but that might necessitate scanning through all “n” things — not an ideal scenario, especially if “n” is extensive.
So, what if there was a way to cut the total amount in half, at every step? In other words, instead of just looking at one thing, and then looking at the next, one after the other in a row, we could instead look at one item, and then decide after looking whether to go to the left or to the right, with each direction containing only half of what’s left? Then we could find what we’re looking for much faster — in “log(n)” time, to be precise, which is significantly faster than looking at everything.
The way a BST works is by putting the “average” thing at the top. Then, when beginning the search, we first check to see if what you’re looking for is more or less than the average. If it’s more, then it will look only at the half that is more than the average, and start again. This way, you have to check only a small fraction of the total number of items before you find what you’re looking for.
Binary search trees are a foundational technique for computer science, and are widely used. Understanding how they work is helpful for understanding the potential and limits of hardware and software.
Comments are closed