Binary search tree is a new class we learned in lectures. It is a tree class with root, and children, and it is designed for fast searching. It has some properties to make it happens. First of all, the left subtree only contains the nodes whose corresponding value is less than the value related to root. Similarly, its right subtree only contains the nodes those corresponding value that is greater than the value on root. Additionally, Its left and right subtrees should also be binary search tree. The last necessary rule is that there is no duplicate nodes allowed.
With above properties and certain methods defined, if we use binary serach tree to search on a value, the worst time complexity in terms of big O notation is that O(n), while the best case has time complexity of O(log n), where n is the number of elements in the list. Compare to linear searching methods, it has a remarkable improvement.
However, binary search tree has a lot of things I still do not familiar with, such as how to code its deleting method. I would spend the rest of this week try to have a better understanding of it, so I can be prepared for our following test.
No comments:
Post a Comment