Assignment 3

Assignment 3
The following is a programming assignment. Submissions should be made on
UMLearn only. Ensure that you submit all files necessary to compile and run
your program, along with a readme that explains how to compile and run your
program. Compilation should only take one command (which may require a
makefile).
Implementation In this assignment, you should provide an implementation of
the Red-Black Tree data structure. You should use a class or a struct (or something similar) for this, so that your implementation can be instantiated. For
our purposes, keys will be non-negative integers and values will be strings. Your
program should accept exactly one command line argument, which is the name
of a csv file containing a list of operations (so that test files are not language
specific). Your program should create an empty red-black tree and then execute
the operations in the file. Each line of the file corresponds to one operation.
The first field is the name of the operation, and the remaining fields are the
parameter(s) for the operation. The operations, parameters, expected outputs,
and required asymptotic running times are described below. The output of each
operation (if any) should be printed to stdout. A sample csv file and the expected output when running with this file as input are available on UMLearn.
• Insert has parameters key and value (forming a key-value pair) and no
output. O(log n) running time.
• Search has parameter key and should output the value associated with
that key in the dictionary. O(log n) running time.
• Delete has parameter key and no output O(log n) running time.
• Minimum has no parameters and should output the key and value of the
key-value pair with the smallest key. O(1) running time.
• Maximum has no parameters and should output the key and value of the
key-value pair with the largest key. O(1) running time.
• Select has parameter i and should output the key and value of the keyvalue pair of rank i. O(log n) running time.
1
• Rank has parameter key and should output the rank of the key-value pair
with this key. O(log n) running time.
In addition, your implementation should support the operations print (which
prints all the keys in the dictionary in increasing order) and validate (which
uses assertions to ensure that all red-black and BST properties hold).
2

Get Your Custom Essay Written From Scratch
Are You Overwhelmed With Writing Assignments?
Give yourself a break and turn to our top writers. They’ll follow all the requirements to compose a premium-quality piece for you.
Order Now