In computer science, binary search trees (BST), sometimes called ordered or sorted binary trees, are a particular type of container… bla… bla… bla… Stop! Binary Search Trees are brilliant and they save a lot of our search time making things much faster that they could be. But before we get to its official definition just imagine that you’ve been already using Binary Search Trees along with a subway…
Imagine you’re in the middle of simplified subway station with eight exits and you need to get to the eighth one.
What do you normally do? You make one turn (decision) after another each time deciding what is the shortest path to the exist
Eventually the distance to exit
#8 is the most valuable criteria you’re using to make correct decisions during each turn. Thus let’s mark all turns and exists with a number that represents the distance to desired exit
#8 from it. For example if you’re in the middle of the station that it would take 13 “steps” for you to get to exit
#8. Also if you’re already at the exit
#8 it would mean that you’re zero-steps far from it. And so on for all other turns and exists.
Actually this is something your brain automatically does. Every time you make a turn you know what the shortest path. These numbers are just a way to make this process understandable not only for human brain but for computer as well.
OK, now let’s clean that drawing up a little and remove subway scheme.
Now let’s clean it up even more and remove useless duplicates to simplify things.
Voila! We’ve got Binary Search Tree (BST) we’re using each time during our subway trips!
How you’re using BST?
Start from root node. Once you came out from subway car you’ve appeared on the top of binary search tree — the node with number
13that is also called the root node. It means that you need to make
13“steps” to get to the target. Your target is exit
#8which is equal to number
0in a tree (zero steps to exit
Remember that nodes are sorted. Eventually all our turns (tree nodes) became sorted by the distance to exit
#8. It means that for every turn you make you have a hint — if right turn is closer to the target then all other turns after the right one will be even closer. And the opposite is also true — if the left turn is farther from the target then all other turns after the left one will be even farther.
Perform search — make a decision. So you’re standing in the root node. If you look to the right you would see that next node (next turn) is
8steps far from the target (node with number
8). Meanwhile the left turn will draw you farther from the target and you’ll be 19 steps far from it. So you decide to turn right. By doing so you’re actually performing a binary search. Binary because there are only two options exists for each turn.
Perform search for every other node. If you keep doing it on every node (every turn) you’ll get to the target node you’re looking and you do it pretty fast (only
3decisions out of
Now, I hope, we can replace those bla-bla-blas from official Binary Search Tree definition that you’ve already met in the beginning of the article. Here we go:
In computer science, binary search trees (BST), sometimes called ordered or sorted binary trees, are a particular type of container: data structures that store “items” (such as numbers, names etc.) in memory. They allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that allow finding an item by its key (e.g., finding the phone number of a person by name).
I hope it sounds a little bit clearer now :)
Of course this illustration is simplified and in a real word there could be “subway stations” (other cases) that are much more complicated with much more nodes and turns. The nodes may be added and removed dynamically. The binary search tree may be unbalanced and inefficient and the one which will require self-balancing and so on. But this is the case for another article.