Binary Tree, Sorting, and Big-Oh (Week 9- 10)

Since we learnt about tree object, the recursive feature of it made me increasingly curious about what else we could develop from this object. During Week 9 we mainly learnt about the Binary Tree Node and how to construct a Binary Search Tree(BST). A Binary Search Tree is basically a recursive node-based binary tree object with three special features: First, the left subtree of a node contains only nodes with keys less than the node's key; second, the right subtree of a node contains only nodes with keys bigger than the node's key; and third, there is no duplicate nodes.

There're several very representing methods of a BST, including insert, find, delete, and height. Learning about how to write those methods in class really inspired me a lot. Basically we need to right a helper function for almost all of those methods, which is quite challenging but helpful to me because I haven't had many chances practicing writing helper functions. Since all the functions and method are recursive, I achieved a more thorough understanding of recursive functions.

What's more, Week 9's lab is also both very challenging and inspiring. Together with my partner, we drew many pictures of what the function is going to do before starting to write the code. TA also helped us a lot on understanding the purpose of each function and how we could avoid unnecessary extra work.

During this week which is Week 10, I feel excited about learning about two more sorting method other than the three basic ones I learnt in last semester's 108 course. They are very efficient compared to the ones we have learnt and also make a lot of sense to me because I have had a decent understanding of recursive functions.

The first one is called Quick Sort which sounds good :) Basically it picks the very first value as a pivot value from a list of values and split the whole list in to three parts- the left half which contains values smaller than the pivot value, the pivot value, and the right half which contains values greater than the pivot value. After doing this step recursively, we can finally get the result which is a sorted list. However, this can be very time-consuming if the list given is already sorted. After quite an amount of discussion, we come up with an idea that we should randomly pick the pivot value instead of using the first value of the list as a pivot value. In this way the possibility of accidentally picking the smallest value as our pivot value decreased to a large extend.

The second sorting method I learnt is Merge sort which behaves even better than Quick sort. Briefly speaking, it divides the whole list into approximately equally half and compare the two smallest values from both sublists and send the smaller one to the merge list. By doing this recursively, we can get the resulting sorted list very fast.

By doing lab 10 this last week, I can see more directly from the graph me and my partner made out of each sorting algrithm. Appearantly the built-in sort method does the best job among all. The three sort methods we learnt from cs108 course has a running time of about n^2 while the other three methods we encountered this semester only require log(n) with base 2.

Looking forward to next week's class and hoping I can do well on the second test!