Week9: Binary Search Tree

Hi! We learned more about Binary Search Tree this week. It is a sorted binary tree, and it is consisting of BSTNode. We also reviewed some sorting functions we have learned in CSC108 i.e. selection sort, insertion sort and bubble sort, and we examined their running time. They are relatively long.

First of all, we have a delete method for BST class and its helper function _delete. The most difficult part for me is to understand what we should do after we find the node we want to delete, when the node has two children. Usually we expect something like it is replaced by either node.left or node.right, and everything just move one step forward and the size decreases by one. Stack and some LinkedList work at that way. However, as we all noticed, the structure of the binary search tree will crash when it has more than two children. Also, we need to ensure node.left is smaller than the node and the node is smaller than node.right. Hence, we find the node with the largest value in node.left and it satisfies the properties of BST.  Moreover, I am thinking about whether we can replace the node by the smallest node in node.right; that seems work too.

As for the running time analysis, BST is sorted, therefore if we want to search a certain data, we can always decide to search either left subtree(smaller than data) or right subtree(larger than data), and the other is ignored. Thus if it is a well-balanced tree with size n, the expected running time will be O(lg(n)) which is the average running time. This is because what we are doing for searching is divide n in half until the exact value is reached, so the number of times is log2 n (2^x = n => x = log2 n ). However, in the worst case i.e. there is only left children or right children, the running time is O(n).

I need to keep working on searching and sorting. There are a lot of ways to do and we shall compare their efficiency in terms of its size n, and its running time when n is significantly large(as n approaches infinity). Thanks for reading and it will be great to receive your comments:)