Well, binary search tree again! (week 9)

In week 9 we had our term test 2(which I sucked TAT).The reason I didn't do well in the test was I didn't deeply understand the contents in week 7. In week 9 professor introduced a new data structure called binary search tree(BST)to us. The basic definition for BST is a binary tree with its all larger item on the right hand side and all its smaller item on the left. For example if I have list [1,2,3,4,5,6] and I have 4 as the root of my BST. Then I need to put 3 on the left and 5 on the right because each item on the right hand of the previous node should be larger than the item on the left by definition. In the same way I got 1 left and 2 right for 3; 6 for 5( there's only one item for 5). The diagram will be like this:
    4
  3   5
1  2   6

（It's not quite good-looking but I hope it can make things clear.)

By building binary search tree we can reach a item in a far quicker way then using bubble search or insertion. The algorithm for BST is quite similar as the one for quick sort. Generally speaking, BST is a sorted binary tree which allow us to reach a certain node in a quicker way so that we can make our modification more efficiently.

As usual we were asked to try to write methods for BST: insert node, delete node, getitem and so on. It's not hard to implement these methods this time by knowing its definition and algorithm.

I looked for BST on wikipedia and it turns out to be a data structure with great
uses. The way it stores data by keys and its structure let it skip over half of the tree at a time, which greatly enhances the efficiency.