Lab5: Binary Search Tree

Lab5: Binary Search Tree
Implement Binary Search Tree (BST)
Purpose
Learn to implement binary search tree
Understand how binary search tree can be used by implementing MAP ADT with binary search
tree.
Preparation
Download a zip file containing starter code files and a tsv file.
Read the lecture slides for Week 4
Objective
You are going to build a TreeMap, a kind of MAP ADT, which maps keys to values, and uses
Binary Search Tree as its underlying data structure. As an example use case, we are going to
build a TreeMap of your classmates so that you can look up your classmate’s information by id.
Instruction
● You are required to complete tree_map.py and bst.py by following the instructions in
the files.
● Open tree_map.py and read the code and comments in the file and understand what it is
trying to do.
● You are going to implement Python built-in __setitem__, __getitem__, and __contains__
methods in TreeMap class. __setitem__ will enable you to put a key value pair with []: e.g.
tmap[key] = val. __getitem__ will enable you to get a value with []: e.g. val = tmap[key].
__contains__ will enable you to check if a key exists with “in” operator: e.g. if key in tmap:.
● Open bst.py and implement the BSTNode class and recursive functions which operate on
BSTNode, and are required by tree_map.py. All functions defined in bst.py are not class methods
(do not include them in a class). The BSTNode class should have four attributes: key (any), val
(any), left (BSTNode), and right (BSTNode), where “any” means any data type.
● Complete methods for TreeMap class in tree_map.py.
● Complete import_classmates and search_classmate functions. Use classmate_factory
function supplied in classmate.py to convert information in classmates.tsv into objects of
1
CPE202 Spring 2020
Classmate, and put the objects into TreeMap. Your user shall be able to search for a classmate
by his or her ID (You are going to insert Classmate objects into your tree with IDs as keys). The
IDs are just sequentially assigned integers. If the same key already exists in the tree, update
(override) the data associated with the key.
● You may add extra instance variables and helper functions if you need, but make sure it
will not affect our test cases. Do not use inner functions (functions defined within a function) for
that will slowdown the execution of your code: inner functions are recreated every time the
function that houses the inner functions is called.
● You may change argument names as long as the change does not change the interfaces.
● Make sure to implement all three boilerplate methods for the two classes TreeMap and
BSTNode).
● Create lab5_tests.py to test all functions and methods in tree_map.py as well as bst.py.
Submit your work to the grader, Gradzilla, then Submit all your files (zip
them into one) to Canvas
2