Week 9 Recursion, tests, assignments

A more straight forward accounting of CSC 148's material... 

This has been a packed week for csc 148. We had to drill ourselves with recursion exercises to deal with the second test and now we have to utilize those honed  recursive thinking skills to handle assignment 2.

A big upside is that the preparation for the test and the material taught in class has greatly alleviated the difficulty of the second assignment. The tree exercises in particular are very helpful in conceptualizing the solving of the assignments.

I've yet to fully delve into the newly taught deletion methods of a Binary Search Tree, but I'd imagine that mastering it will be crucial to scoring well on the final exam. Intuitively the program can be broken down into these parts:

1.Look for the node which holds a data value which is the same as your data paramter:

You utilize the BST property of the tree and search in logn time by putting in if statements to look left if the current node being looked at is greater than your data value, look right if the current data value is less.

2. Once you find the node in question 'X' (with the right value), you must check the left child if it has one, and right if not.

3. If there is a left child, you look at the subtree connected to that node and put the maximum value in X's place. If there's no right child you simply move the right child into X's place. Doing either of these actions will preserve the BST's property.

4.Delete nodes that you've moved into X's place.

If you asked me to do this at the beginning of the course, I would be baffled. However, despite knowing how Binary Search Trees work, I'm still amazed at how algorithims can take advantage of it.

This video in particular was very helpful in solidifying concepts learned in class:

Final word for the week: compared to csc 108 the topic of BST's and these new delete methods are much more difficult, and dare I say it, maybe even harder than everything in that course besides the final exam.