Week8

    Time flies. Only one month left till the end of classes. 
    Why don't we do a short review on what we've done so far? In my opinion, the most important elements of this course are recursion and class construction. I would say that recursion is the most powerful concept in this semester, for the reasons in my last week's post. Certainly, class construction has been an essential idea throughout this course. Stack, Tree and LinkedList are all depended on the design of classes. I think now we are really getting the taste of what Object-Oriented Programming is. 

    This week's lectures are on LinkedList and Binary Search Tree. LinkedList is basically a tree with an arity of one. We've learnt two ways to implement a LinkedList. The more complicated approach is to separate the implementation into a LinkedList node class and a wrapper class for the LinkedList. One benefit of this approach is that it makes thinking recursively more natural to programmers. Binary Search Tree is a tree, with an arity of two, in which the value of each node is controlled strictly -- the value on the left sub-tree must be smaller than the root and that on the right sub-tree must be larger than the root. The other way around might be possible too. The significance of this type of tree is the efficiency of searching. With its rigorous structure, binary search tree greatly reduces the search time it takes to iterate through the data of the tree. This would be crucial for data management with a massive amount of information.