Week #11: Why Geeks Need to Know How to Write..... Revisited

Going back to my first blog post, I believe I could've elaborated more on my thoughts about the topic of why geeks need to know how to write, as I can clearly see it is very general and kind of confusing. I do agree with everything I said but reading through other SLogs I've come across very interesting points that I had not even considered.

One interesting idea I came across is how knowing how to write helps with coding. In coding comments are essential. As Leon Wong wrote in his blog (http://theremustbe.blogspot.ca/search?updated-max=2015-02-06T20:25:00-08:00&max-results=7) "clear and understandable comments are steady bridges between you and other programmers". Therefore knowing how to organize and clearly communicate your steps will make your code more readable and understandable by other programmers.

Week #10: Test and Mutating BST

Week #9 we had the second term test. It covered Trees including Binary Search Trees and it also covered Linked Lists. I discussed Binary Search Trees and Linked Lists in my previous blogs. Therefore refer to those for more information.

That week also learned about two important functions for mutating Binary Search Trees, insert and delete.

INSERT

This function inserts a new node into the Binary Search Tree and when it does so it must satisfy the conditions of a BST. These state that the data of the node must be comparable, the data in the left subtree must be less than that of the node and the data of the right subtree must be greater.

Here is the code (taken from class notes) for the function insert:

DELETE

The function delete, as its name states, it deletes a node from a Binary Search Tree. When deleting a node from a BST you must reconnect the remaining subtree. Here is the code (taken from class notes) for the function delete:

As demonstrated in the code, both functions use recursion to mutate the Binary Search Tree so that each node follows the appropriate criteria of BSNode.

Week #9: Linked Lists

Week #8 was about Linked Lists.

What is a Linked List?

A Linked List structure consists of nodes that have a value (object) and a reference to another object, therefore another node. When initializing a Linked List Node you pass the value as a parameter and have a default parameter for the reference, set to None.  Here is a more visual representation of the Linked List :

Linked Lists can be described as recursive structures because every node refers to a linked list.

But sometimes it is easier to approach this structure as one train of links. For this approach we implement the class Linked Lists as a "wrapper" representing the structure as a whole. We create variables to keep track of the front (head) and the back (tail) links as well as the size of the whole list. This is the approach we took when working on Lab 07.

One basic concept that we need to understand is how to traverse all the items in the Linked List. This bit of code is very useful for many functions that are used to manipulate the structure.

When traversing all the items, we need to call on the first node (front/head) and use the default parameter for the Linked List Node, nxt, that will return the next link. The python code (taken from class notes) is as follows:

cur_node = self.front

while <some condition here>:

     # do something here.....

     cur_node = cur_node.nxt

This code is only a basis that helps implement functions such as _contains_ or _get_item_. Knowing how to traverse the tree allows you to manipulate links and search for links as well.

Week #8: Binary Trees

During week #7 we were introduced to Binary Trees.  A Binary Tree differs from the generic Tree design, as it contains nodes that have a maximum of two children referred to as left and right.

Here is an example of a Binary Tree:

When traversing a Binary Tree, there are three different orders in which the nodes can be visited:

1. Inorder: left child, root, right child

2. Preorder: root, left child, right child

3. Postorder: left child, right child, node

We can extend our understanding of a Binary Tree and create a Binary Search Tree (BST). A Binary Search Tree is ordered/sorted.  The left subtree always contains data less than the node data and the right subtree always contains data that are greater than the node data, therefore the data of the all node must be comparable.

Here is an example of a Binary Search Tree:

Efficiency of a Binary Search Tree

As mentioned in our class notes, if the tree of n nodes is "balanced", it will have a height of about log(n). Therefore when using this binary search tree to find data you will access about log(n) nodes. The structure of the BST depends entirely on the order of insertion of the items. Worst case scenario would be if you had to access n nodes (linear relationship) which is the same as having a list and going through every single item to find your desired data. A balanced BST is obviously more efficient.

Here is an example of a balanced BST vs and unbalanced BST: