SLOG Post # 7 - Term Test 2 and Binary Search Trees

Term Test

This week's SLOG post will be about the second midterm test, which we wrote this week. The focus of this test was on recursive functions, trees, and linked lists. This was also our first test that, in my opinion, involved writing challenging code (our earlier test was really more about proper Python style and structure).

I think that I performed quite well on the test, although I am not certain as I haven't seen the marks yet. I employed the same sort of study methods as before. I went over the lecture slides, stopping whenever there was a practice question or function so that I could try it out myself. I also re-did all of the labs, making sure that I knew how to write the code for each function that we were assigned. I also put the code for some of the tricky functions on my "cheat sheet" for the test. This turned out to be a fantastic idea: some of the questions on the test were really similar to the ones that I had copied down.

Unlike the previous test, I didn't go through the course notes for the sections that were on the test. The main reason for this was that I was quite short on time: I also had to study for a physics midterm that was the night before. I don't think it significantly hindered my performance on the test, however. The course notes are really best for providing answers to tricky conceptual questions, and most of the questions on the test were practical questions that involved applying the concepts. Because these types of questions are so similar to the questions that we get on our labs, I was well prepared for them.

By now, I am pretty confident that my studying methods for CSC148 are quite effective. I will be using the same strategy for the final exam, and I'm optimistic that I will do quite well.

Binary Search Trees (BST's)

We also touched on BST's in class this week. BST's are trees that only contain numerical values* and an have an arity of two. The nodes in BST's are special: each node can have a left child (a node with a value less than the parent node's value) and a right child (a node with a value greater than the parent node's value). This creates two subtrees, a left subtree and a right subtree, in which all values are lower or higher (repectively) than the original parent node.

It's immediately apparent that BST's are quite powerful and useful as search tools. The left child-right child property makes it so that, when searching for a value in an ideal tree, very large portions of the tree can be skipped. To explain this I've included an optimal, or perfectly balanced, BST:

If you are looking for the value 111, you would only need to pass over 3 values (90, 150, and 95) before reaching 111.

However, there are some cases where a BST doesn't really help with your search efficiency, as is the case with this example:

Because each value is greater than the preceding value, the left child-right child property does not help since all the nodes are right children! this scenario is basically equivalent to a linked list: to get to 50, the last node, you'd need to pass through all of the other nodes to get to it.

I didn't have too much difficulty writing the binary search tree methods, which are usually recursive (like most of the regular tree methods). My TA had told me that when designing methods for BST's, it's best to consider the two simplest cases: a tree of height 1 (ie a node with no children) and a tree of height 2 (a node with a left child and a right child). If a method works for these two cases, it will (typically) work for all of them.

* Note: In our class, we only used BST's with numerical values. It is also possible to include other objects, as long as they also have an order (for example, letters).