Week 8

This week, we continued on and talked about binary search trees and touched on big o notation/some running time analysis (which we are learning concurrently in CSC165) as well. I'll be discussing mainly BSTs and the assignment which is due next week.

In essence a binary search tree is a binary tree where the left subtree of a node only contains values smaller than the value of the node, and the right subtree of an doe only contains values greater than the value of the node. This allows for a quicker search (roughly O(logn)) for most cases. Earlier in the course we encountered a data structure very similar to BSTs (I forget if it was a lab or an exercise) which was essentially implemented as a nested list instead of a tree. In both cases they essentially provided a different kind of structure to perform binary search (as opposed to the standard way on a sorted list). Instead of finding the midpoint in a list, and changing the upper and lower bound every iteration, in a BST the root is in a way the midpoint, and you traverse to the left subtree or right subtree instead of rerunning the algorithm on the left half or right half of the list. It isn't clear to me the benefit of implementing a binary search tree instead of sorting a bunch of values in a list, especially since binary search on a list will always be O(logn) whereas the BST could have a worst case runtime of O(n) if every node only has a right child. Perhaps the different variations of BSTs that Danny mentioned in class (AVL, red-black, splay, tango trees) have a better performance in more specific situations.

While going over BSTs, we also covered some of the common methods of a BST, like inserting, deleting, and the __contains__ method. They are both simpler than I expected, and involve finding the location of the node in question (or where it should be), and updating the children of the nodes around it to either delete or insert a node (I'm oversimplifying it a little). The contains method was the easiest of all, but is an extremely useful method to have, especially in a class like a BST. In the last few classes I learned a lot about useful built in methods like contains, len, repr, and str. One thing that I didn't realize was that with the insert method, the initialization of a BST with a list of values was made much simpler by just calling the insert method on each value.

A last thing that we did this week was finish up on assignment 2. I had never thought of organizing regular expressions into a binary tree, but it did seem an extremely natural thing to do. The assignment was a great way to practice recursion and manipulating/using binary trees while learning about what a regular expression is. It also provided some review on classes and inheritance. After this assignment I realized that so far the assignments have been very helpful in allowing the opportunity for the application of the topics learned in class on a larger scale and in a more challenging way than what is done in exercises and labs.

Speaking of which, if anyone was able to finish the iterative function of count_less from the lab let me know how you did it!