Week 9

WELCOME BACK!!!!!! How's it going for everybody? I hope everybody had an awesome week. Well today there's a snowstorm and I have no idea what is going on with the weather! Seriously today is March 12 and when I woke up today, all I can see is snow outside my window. However, U of T seems to think that their students are tough and snowstorm is just a piece of cake to them. So yea, I still have to go to class today. Ok no more complaining, let's get started.

This week again I'm gonna share about what I've learned in lecture and I actually want to talk about my lab, which is lab #8 because I do find it interesting and I've learned quite a lot from it. 

In this week's lecture, we talked about the Binary Search Tree. Yes not just the binary tree, the binary search tree. In a binary tree, different values can randomly disperse at any node of the tree. As long as the tree has the structure: a root plus possibly two children, then it's fine. However, in this case it'll take us a long time if we are trying to search for a specific node because we possibly have to go through all the nodes to find just that one node. This is the reason why we need the Binary Search Tree. The difference between the Binary Search Tree (BST) and a normal Binary Tree is that in a BST, the value of the left child must be smaller than the root, and the value of the right child must be greater than the root. Because of this special feature, BST has a much greater efficiency. It allows us to ignore almost half of the tree after every pass. 

Here is how the search function run in a BST:

say we have to find the value z.

we compare z to the first node's value, if z is smaller, then we call the search function again with only the left sub-tree. And if z is bigger, then we call the search function again with only the right sub-tree.

repeat the step above until z is equal to the node's value.

So can everybody see how efficient BST is compare to the normal Binary Tree?

Now I want to share about lab #8 that I have just finished this afternoon. This lab is mainly about BST and we have to write a function to count all the nodes in the BST that are smaller than a given number. Now this doesn't sound very hard after I've explained about the search function above right? Yet, when we actually started to code, we found that it was not as easy as we thought. In fact, we were stuck for like 15 mins and have no clue on what we were supposed to do. I don't want to share our solution of the lab here or this blog will be super long. But what I've learned today is that all the programs are actually connected to each other in some way. Just like our example in lab #8, we used a function in Stack class to solve the question. Interesting right? So if you are a computer science student, please don't think that you can forget a function after you got tested on it. Because every single can be helpful to your program.

That's all for this week's blog. See you next week!