The goal of this assignment is to practice working with the binary search tree structure and with sorting algorithms. There is also an SRC Response to be completed, which relates to the Web Scraping Project out now. This should be handed in separately on Gradescope. Look towards the bottom of the handout for more information on the SRC Response!

Setup and Handin

Setup

In order to setup homework5, create a new project in PyCharm. Copy the BST starter code below into a file named bst.py. You should also create a file names sorting.py, which is outlined later in the handout.

Handin

Hand in the following files to Gradescope when submitting the assignment:

  • bst.py
  • test_bst.py
  • sorting.py
  • test_sorting.py
  • README.txt

Remember to include a README.txt when submitting your assignment!

Staff Assistance

Your friendly TAs and Professor are here to help with this assignment! You can find our hours schedule here.

The Assignment

Binary Search Trees

Here is a lightly cleaned up version of the Binary Search Tree implementation we ended up with in class, which you should copy to a file called bst.py:

class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


class BST:
    def __init__(self):
        self.root = None

    def contains_at(self, node: BSTNode, data) -> bool:
        if not node:
            return False
        if node.data == data:
            return True
        if data < node.data:
            return self.contains_at(node.left, data)
        else:
            return self.contains_at(node.right, data)

    def contains(self, data) -> bool:
        return self.contains_at(self.root, data)

    def count_at(self, node) -> int:
        if not node:
            return 0
        return 1 + self.count_at(node.left) + self.count_at(node.right)

    def count(self) -> int:
        return self.count_at(self.root)

    def add_to(self, node: BSTNode, data):
        if node.data == data:
            return
        if data < node.data:
            if node.left:
                self.add_to(node.left, data)
            else:
                node.left = BSTNode(data)
        else:
            if node.right:
                self.add_to(node.right, data)
            else:
                node.right = BSTNode(data)

    def add(self, data):
        if not self.root:
            self.root = BSTNode(data)
        else:
            self.add_to(self.root, data)

Your task is to modify this binary search tree so that at each node it stores a value in addition to a key. To do this, you will need to:

  • Replace the data field on the BSTNode class with two fields: key and value
  • Modify the contains and contains_at method to search the tree using this new key field instead of the data field
  • Add a lookup method to the BST class; it should take a key and return the corresponding value if it is present in the tree; otherwise, it should raise a KeyError. Hint: this method’s implementation will be very similar to contains, and should use a recursive helper method similar to contains_at.
  • Modify the add_to method to take a key and a value (instead of the data argument). It should use the key argument to determine where to add a node. If a node with that key is already in the tree, it should instead replace its value.

You should not need to modify count.

You should write good tests for the contains, count, lookup, and add methods in test_bst.py. You do not need to include tests for any recursive helper methods.

Insertion Sort

In sorting.py, write a function called insertion_sorted that takes in a list and returns a sorted list. Your function should use the insertion sort algorithm:

  • Create a new list for the result of your function
  • Loop over the elements of the input list
  • For each element, put it in the right place in the result list
  • Return the sorted result list

You can use the insert method on lists. The insert method inserts an item into a list at a given index; for example:

>>> lst = ["c"]
>>> lst.insert(0, "a")
>>> lst
["a", "c"]
>>> lst.insert(1, "b")
>>> lst
["a", "b", "c"]
>>> lst.insert(3, "d")
>>> lst
["a", "b", "c", "d"]

While your function implements the same algorithm as our insertion sort function from class, its implementation will look quite different: it’s building a new list rather than modifying its argument. For your reference, here is the insertion sort function we ended up with in class:

def insertion_sort(lst: list):
    """
    Sort a list in place using insertion sort
    """
    index = 1
    while index < len(lst):
        insertion_index = index
        while insertion_index > 0 and lst[insertion_index] < lst[insertion_index - 1]:
            element = lst[insertion_index]
            lst[insertion_index] = lst[insertion_index - 1]
            lst[insertion_index - 1] = element
            insertion_index = insertion_index - 1
        index = index + 1

You should write tests for your sorting function in test_sorting.py.

README

In your README.txt, please include answers to the following questions:

  • Did you discuss this assignment with any other students? Please list their cs logins.
  • How many late days are you using on this assignment?

SRC Response

Look over the SRC Response Handout linked here. This SRC Response asks you to reflect on the social implications of your web scraping project. Unlike the previous SRC Responses, there will NOT be a peer review for this response.