Lab5: Binary Search Tree


Rate this product

Lab5: Binary Search Tree
Implement Binary Search Tree (BST)
Learn to implement binary search tree
Understand how binary search tree can be used by implementing MAP ADT with binary search
Download a zip file containing starter code files and a tsv file.
Read the lecture slides for Week 4
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.
● You are required to complete and by following the instructions in
the files.
● Open 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 and implement the BSTNode class and recursive functions which operate on
BSTNode, and are required by All functions defined in 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
● Complete import_classmates and search_classmate functions. Use classmate_factory
function supplied in to convert information in classmates.tsv into objects of
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
● Create to test all functions and methods in as well as
Submit your work to the grader, Gradzilla, then Submit all your files (zip
them into one) to Canvas

Open chat
Need help?
Can we help you?