Impression about week 9

Part1: Deletion in BST

This week in lecture we talked more about binary trees, specifically binary search trees. A binary search tree (BST) is similar to the binary tree I talked about two posts ago, except it has the extra condition that the data in the left subtree is less than the data in the root, which in turn is less than the data in the right subtree. This makes searching through the tree much more efficient, because we can use a binary search algorithm instead of a linear search algorithm. Recalling some information from CSC165, we know that binary search has runtime O(log n) whereas linear search takes O(n)–Binary search is much better, because the BST is already sorted, so it can ignore approximately half of the values, because they are all smaller/bigger than the value being searched for.


We also talked about deleting an element in a BST. To do this, we made a delete method in our BST class that simply calls a module-level function called _delete. If my understanding of wrapper classes from last week is correct, BST class function is acting as a wrapper for the module-level delete function, which does most of the work. The module-level function has many cases to deal with. It is given a node in a BST and data to delete. If the node is not None, it can look for the data in the left subtree if the data is less than the node’s data, and the right subtree if it is greater, using the definition of a binary search tree. It then uses recursion to get down to a base case, where the node’s data is equal to the data being searched for. It returns a new tree with the appropriate data deleted.

def delete(node, data):
    ''' (BTNode, data) -> BTNode

    Delete, if it exists, node with data and return resulting tree.

    >>> b = BTNode(8)
    >>> b = insert(b, 4)
    >>> b = insert(b, 2)
    >>> b = insert(b, 6)
    >>> b = insert(b, 12)
    >>> b = insert(b, 14)
    >>> b = insert(b, 10)
    >>> b = delete(b, 12)
    >>> print(b)
            14
        10
    8
            6
        4
            2
    <BLANKLINE>
    if node is None:
        pass
    elif node.data > data:
        node.left = delete(node.left, data)
    elif node.data < data:
        node.right = delete(node.right, data)
    elif node.left is None:
        return_node = node.right
    elif node.right is None:
        return_node = node.left
    else:
        node.data = _find_max(node.left).data
        node.left = delete(node.left, node.data)
    return return_node

Part2: Term Test 2

Term test 2 was held on Wednesday. Preparing for the test, I concentrated on lab exercises. I redid all the lab exercises and timed my self.
I was very happy that most question on the test were similar to the lab exercises. Therefore, I finished the test for only 20 minutes.