Week #10: My impressions of Week 9

We had only one lecture class for Week 9 since we had term 2 test on Wednesday. For the term test, I just hope that I achieved A on it. Professor Heap also clarified on which subjects are included for the test. Thanks to Professor Heap, I exactly knew what I had to study for. I would like to thank Professor Heap for his works.

During week 9, we focused on BST (Binary Search Tree) and its methods insert and delete. As the course material was fairly straight forward, I had no problem understanding the concept. Although I was confused by random module for Lab #8, my friend and I worked on it together. I also used Danny's office hours in order to understand the basic concept since I've realized that asking a question to professors is a much better than struggling over the question for 2 to 3 hours. One thing I noticed is that the course material for lab #8 will be revisited in different ways for CSC 263. This means that if I do not understand the problem and just ignore, this will once again come and cause problems to me later in CSC263 or other CS courses. Thankfully, with the help from Professor Heap, I understood the problem perfectly.

I would like to demonstrate some basic implementations for BST, insert and delete methods. For BST, we also need class BTNode. However, I will skip on the implementation part of BTNode as I've discussed before on my previous posts. The source is from lab 08 by Professor Danny Heap.

Now then, for class BST. 

(Source:  http://www.cdf.toronto.edu/~csc148h/winter/Labs/lab08/bst.py)

class BST:
"""Binary search tree.""" def __init__(self: 'BST', root: BTNode=None) -> None:
"""Create BST with BTNode root."""
self._root = root

def __repr__(self: 'BST') -> str:
"""Represent this binary search tree."""
return 'BST({})'.format(repr(self._root))

def find(self: 'BST', data: object) -> BTNode:
"""Return node containing data, otherwise return None."""
return _find(self._root, data)

(Source:  http://www.cdf.toronto.edu/~csc148h/winter/Labs/lab08/bst.py)

What I want to demonstrate now is insert and delete methods.

(Source:  http://www.cdf.toronto.edu/~csc148h/winter/Labs/lab08/bst.py)

def _insert(node: BTNode, data: object) -> BTNode:
    """Insert data in BST rooted at node, if necessary, and return root."""
    return_node = node
    if not node:
        return_node = BTNode(data)
    elif data < node.data:
        node.left = _insert(node.left, data)
    elif data > node.data:
        node.right = _insert(node.right, data)
    else:  # nothing to do
        pass
    return return_node




def _delete(node: BTNode, data: object) -> BTNode:
    """Delete, if exists, node with data and return resulting tree."""
   
    return_node = node
    if not node:
        pass
    elif data < node.data:
        node.left = _delete(node.left, data)
    elif data > node.data:
        node.right = _delete(node.right, data)
    elif not node.left:
        return_node = node.right
    elif not node.right:
        return_node = node.left
    else:
        node.data = _find_max(node.left).data
        node.left = _delete(node.left, node.data)
    return return_node
(Source:  http://www.cdf.toronto.edu/~csc148h/winter/Labs/lab08/bst.py)


Professor Danny Heap kindly provided us with the implementation of BST methods insert and delete. Although I had trouble understanding these methods, I got used to it soon as I've already experienced various Binary Search Tree. I think my experience on previous lab exercises also helped me understand lab 8 materials. I believe that doing lab exercises help me study and understand the course materials and develop me as a better computer scientist.