Week 10

We had our term test 2 on the 11th of March, which is why we only had one lecture this week. I found term test 2 a bit harder than term test 1, but overall it went fine. This week we studied more about binary search tree, we implemented an insert and delete function. For the delete function, we went over the algorithm first in plain English and then translated that to python language. I thought this was a perfect way to do the coding, it made it quite easy. I will definitely follow this technique in the future. This is how we did that:

Algorithm for delete:
     1. If this node is None, return that
     2. If data is less than node.data, delete it from left child and
         return this node
     3. If data is more than node.data, delete it from right child
         and return this node
     4. If node with data has fewer than two children,
         and you know one is None, return the other one
     5. If node with data has two non-None children,
         replace data with that of its largest child in the left subtree,
         and delete that child, and return this node
    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

This was extremely helpful.