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
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.
Hand in the following files to Gradescope when submitting the assignment:
Remember to include a README.txt when submitting your assignment!
Your friendly TAs and Professor are here to help with this assignment! You can find our hours schedule here.
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
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
datafield on the
BSTNodeclass with two fields:
- Modify the
contains_atmethod to search the tree using this new
keyfield instead of the
- Add a
lookupmethod to the
BSTclass; 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
- Modify the
add_tomethod to take a key and a value (instead of the
dataargument). It should use the
keyargument 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
You should write good tests for the
test_bst.py. You do not need to include tests for any recursive
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
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?
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.