Impressions of Week 9

    The lab this week had to do binary search trees. In my post "Impressions of Week 7" I summarized what a binary tree was, and mentioned that a binary search tree could be searched more efficiently due to the fact that not every node has to be visited. To elaborate on this, say we have a binary tree such that all of the nodes' data are integers. To the left of each node is a sub-tree (also a binary search tree) where all its nodes contain data that is less than its root, and to the right is a sub-tree (also a binary search tree) containing nodes that have data that is greater than its root. If you are searching for the value 7 in a binary search tree with a root containing the value 15, only one half of the tree needs to be traversed, which would be the left side as the right side only contains values greater than 15. This makes binary search trees much more efficient, as finding values is faster than if it was a flat list.

    Another neat thing about binary search trees is that the data it contains does not have to be numbers, it can be any kind of data as long as its comparable. This could have many applications that would make searching algorithms much more efficient in a variety of useful programs, especially if the number of data entries is extremely large.

    As an example, here is a visual representation of a binary tree. Let's say we are looking for the value 200. If we used pre-order traversal, we would need to look at 14 nodes before we get to 200 (90, 50, 20, 5, 25, 75, 66, 80, 150, 95, 92, 111, 175, 166, 200). By traversing this as a binary search tree, we would only need to look at 3 nodes before arriving at 200 (90, 150, 175, 200). Looking at the first node, we go to the right since 200 > 90. 200 is also greater than 150 so we go on to 175, where 200 is once again somewhere to the right, and there it is at the end. That's 11 nodes that did not even have to be looked at, which may not seem like much, but if the tree was massive then it could save a lot of time.