week 7

More recursion in Binary Tree

• Binary Tree
• Recursion
• Abstract Data Type

 This week, we learn “Binary Tree” based on the ordinary ADT "tree" from the last week.

 "Binary Tree" is distinguish from the ordinary tree that every node has none or no more than 2 children which are also distinct from each other, the left children has the value less than its parent node's value and the right children should has the value greater than its parent node's value.
  
  Although at first sight, I think it is not that good but even troublesome when act as a data type to store data . 

  Since, it it works as a data type that used to store things, it has many weaknesses for example it could not guarantee the sequence of a series of numbers and I couldn't find a number by calling its index. However, when it function as a dictionary, it will display its powerful latent energy. For example:

For example, in the Binary Search Tree(BST) like above and a list contain [8,4,9,3,5,10]. If I want to find out whether 10 is in it. I only need one step(by the special property of BST, from 8 I could go straight to the right to the 9 and then to the right side get 10, total 2 steps!) but need 5 steps in the list.

Another example, if I want to find 5, I just need 2 steps(from 8 I could go straight to the left side and then go the right side of 4 which is 5, total 2 steps).But need 4 steps for the list.

With the n the elements it need only about log2(n) steps to find it out,which is much faster than any other data type.

 More you practice,More you will learn.

Week 6

Winter is leaving 

&

Reading Week break is coming

• Tree - A new useful ADT

The last week before Reading Week Break, which I am really looking forward to 
although I still have no girlfriend to celebrate the Valentine's Day（So sad...）

This week, I learn a new abstract data type which is called - Tree. It just looks

like a tree diagram, with some terminologies like root, node, children, edge,
leaf, height, depth etc. The Tree is created with the base of recursion, because 
every node with its children could be thought as a individual tree. 

By this recursion features, we could use it to quickly and efficiently search some information about every elements.

I once heard a concept 'Binary Tree', which seems to be a very useful ADT to 
store information with some features like magnitude or something which could 
greatly facilitate us to search something.

I believe Tree has much more interesting functions and applications, which needs me to explore.

By the way, the Chinese New Year is coming, which is also my sister birth year.
I wish all my family could live a healthy life and everyone could feel the beauty
of life and cherish the people around you.

Week 5

A tired week

• Quick Sort
• Stack & Queen

 Test,test,test..Do you wanna some more test? No!!!!!

 I've been through three tests this week, which almost wear me out.I have no energy to make complains. Here comes the slog:

 This week, Danny demonstrates a so called 'quick sort' sort method that could sort a list of number very quickly(forgive my plain words).By the help of the super powerful recursion, just few steps, every number are sorted.

 Here, is my analyse: For a given series of numbers: L=[6, 2, 5, 7, 1, 4, 3, 8]

 First, we choose the first elements as a flag, in this case is 6. 

 Second, every other number has to compare their number with 6, if it is smaller than it, insert to the left of 6. If it is greater than it, inset to the right of 6.

 Then, we get [3, 4, 1, 5, 2, 6, 5, 7, 8]. Now we just have to consider to sort the two sides' numbers of the number 6. 

 For the left part [3, 4, 1, 5, 2]. We repeat the above first and second steps, take 3 as a flag, then rearrange other numbers, then we get [2, 1, 3, 4, 5]. 

 By some check, repeat these steps until all numbers all sorted. Hence, we do it again, take 2 as a flag, then rearrange orther numbers, then we get[1, 2, 3, 4, 5]. The right side is the same.

 Less swap numbers means quicker sort, which is really useful by using recursion to complete such a problem. 

 Besides, I learned a new ADT(Abstract Data Type). Just like list, tuple and dictionery. We could use class to custom our own wanted ADT. 

 We can use a stack to check whether parentheses are balanced. It is featured

that the last item in is the first item out, which could be called 'LIFO'.Unlike

stack, queue is converse, which is 'FIFO'.It can be used to simulate the actual

world like a real queue. First people in the line should be the first to get 

out.

Ok, that's it. I need to take a bath and have a good rest.