I said I would cover a new type of Tree in my post about Tree ADT's, didn't I?
Anyways, today I'm focusing on Binary Search Trees, which are also called BST's. Now, to understand BST's, lets first make one thing clear- they are NOT the same thing as Binary Trees. I made this mistake a lot when I first started working with them, and it made communicating my ideas about these concepts quite annoying. So in case I wasn't clear- let me reiterate this point one more time:
A Binary Tree- also called a BT- is simply a tree ADT which always has 2 positions for possible children- left and right. This means that, if you take any node in a BT, you can only access a maximum of two other nodes. Although this may seem restrictive at first, it also allows us to implement various types of search algorithms. And this is where BST's come in.
A BST is just a type of a BT with an additional rule; that the value of any node in the tree must be larger than the value of every node in the sub-tree who's root is it's left child. And the same is true for the sub-tree rooted in its right child, except with larger values instead. Confusing? Here's a better way of explaining it.
Remember, the topmost node of a tree (the one with no parent) is the root. Any node in a tree can be considered the root of its own tree- called a sub-tree of the original tree. In order to access a specific node in some tree- let's just say it's value is 7- we need to use a search algorithm, and we must always start at the root of the tree provided. Than, we must find some way to travel (or "transverse") the nodes of the trees until we find the node we want. Unlike a list, we do not simply travel over every node in the tree in a sequence until we find the one with the value we want. In fact, such a searching method is actually considered to be really inefficient. After all, you would have to evaluate every element in the list just to verify if the element isn't in the list.
However, there are more efficient search algorithms, such as binary search. Binary Search takes list already sorted in ascending order, and takes it's middle element. It than splits the list into two sub-lists- one containing every element left of the middle, and one for every element to the right. It than does a comparison. If the element your looking for is bigger, than go to the right sub-list and repeat the algorithm. If its smaller, it will go to the left sub-list and repeat. And if it's not bigger or smaller, than congrats, it can only be equal, and so you've found it!
As you have probably guessed, binary search trees are another way of implementing this search algorithm. However, rather than take a presorted list, it takes a BST. Since a BST, by definition, stores elements in such a manner so that the only elements in the left sub-tree of the node have values smaller than its own (and bigger with right), a similar algorithm can be implemented to find any piece of data. For instance, if the node you are looking for has a value of 5, and the value of the node you are evaluating is 7, you know that the node you are looking for must occur in the sub-tree to the left of the current node (if it's in the tree at all), since that sub-tree contains all the values smaller than 7. So, even in the worst case, this search algorithm will be significantly faster than a simple, linear search.
No comments:
Post a Comment