Week 9: Binary Search Trees and Performance

The types of list searching that I am most familiar with, from my time in CSC108,  are linear search and binary search.  The first is big-O of n, meaning that its performance is proportional to the size of the list, making the search rather tedious.  Binary search is much less tedious, and has log n performance.  The only stipulation with using binary search is that the list is already sorted.

The past few weeks have been all about presenting known concepts in the form of a tree, and this week that was done for binary searches.  Aptly named binary search trees are based on two classes, a node class and a wrapper class.  The nodes contain a value and references to nodes on their left and right, while the wrapper class denotes the root node. 

Binary search trees, I found, makes searching for a particular value or set of values in the tree remarkably efficient.  Knowing that there are 2 paths, one which leads to a greater value and one which leads to a lesser value, dramatically cuts down on performance time.  However, there are also many nuances to using binary search trees.  When deleting a value, several cases have to be considered, from nodes that have no children to nodes that have one children, to nodes that are root nodes for the entire tree.   Though working with them requires more extensive coding, I certainly find it more efficient than my previous methods.