Week 9

The new concept of Binary Search Trees is a bit harder to understand than I thought. The structure of a BST is simple enough; it's basically a regular tree but sorted. Each value that is smaller than the root is contained in the left sub-tree while each value larger than the root is contained in the right sub-tree. Each value is automatically sorted as it is inserted into the tree so there is rarely a need to call a sort method on a BST. Since BSTs are sorted, it is an applicable class for a binary search. The binary search cuts its search query in half every time it does not find its desired value. When compared to the linear search which checks each value one by one, the binary search is more efficient. One of the concepts I'm having difficulty understanding is how some of its methods work. For example, I don't understand how a delete method deletes the root in a BST and replaces it.

Mr. Heap also went into the concept of big-ohs this week. I already learned about this in CSC165 but it's still a nice refresher to have it be introduced again. The big-oh represents the maximum number of steps to be executed by a program. This means that the big-oh of a program would be focused on the worst case argument. Big-ohs represent these maximums in the form of mathematical functions (eg. constant, linear, quadratic) where the function is truncated to the term with the highest power (eg. if the function n^2 + 3n + 16 were to represent the number of steps a program would take in the worst case, only the term n^2 would be considered important). This makes big-ohs useful for determining the efficiency of programs