This week the focus is on Binary Search Tree. We have been introduced this structure last week and it is further explored with emphasis on efficiency. In the lecture, we firstly discussed the different cases of deletion of data from BST rooted at node root. The most complex case is the deletion of the node itself. We need to search for the leaf at the right end of the left subtree or the leaf at the left end of the right subtree to replace the root and link it to the remaining subtrees. This search and replacement is efficient in a binary search tree. Then we developed the topic a bit to the measure of performance of sorting algorithms. When evaluating the complexity, we ignore the difference between the steps not dependent on the list size n.
During the lab, we implemented the count_less method in different classes regarding binary search trees. This actually raised my attention on use of helper functions. I seldom used helper functions in my assignments and exercises. However, they are quite useful when the recursion steps are done on another type of structure.
No comments:
Post a Comment