CMPSC 130A (Fall 2020)
Programming Project #1
Due: Sunday, October 18, 2020 at 11:59 PM
1 Project Description
In this project you will be implementing a variant of binary search tree, which we will refer to as a
ternary search tree (TST). Binary search tree and its variants are members of a class of search tree
that are referred to as multi-way search trees. The generalization is that in comparison to a binary
search tree node that has a singleton key and two children (a left child and a right child), the node
in a multi-way search tree stores k keys and therefore have k + 1 children. Thus a ternary tree node
will store two keys, viz., klef t and kright and three children, viz., a left child, a middle child, and a
right child. The search property holds as before:
• The left sub-tree has keys smaller than klef t. • The right sub-tree has keys larger than kright. • The middle sub-tree has keys larger than klef t and smnaller than kright.
You are required to implement a Ternary Search Tree (TST) class. Each node in the TST is a
pair of (word,count) where word serves as the key and count is the value associated with the key and
shows the number of occurrences of the word in the underlying dataset represented by the current
instance of TST.
The TST class should have at least the following functions:
1. a constructor and a destructor.
2. a method for searching a word in the TST (the word may not exist in the dataset)
3. a function for inserting a new word into the TST if the word does not exist or increment the
count by 1 if the word already exists
4. a function for deleting a word from the TST if the count is 1 or decrement the count by 1 if
the count is greater than 1.
5. a function for doing a range search
For the sake of simplicity, you may assume that the tree does not contain duplicate keys. Given
the above definition, you can easily develop the algorithms for lookup, insert, and delete by generalizing the traditional binary search algorithms. This part of the project is the design step that requires
you to develop the pseudo-code for the three algorithms. You are warned that this generalization
is not as simple as it sounds – it does require some thinking especially for the insert and delete
functions. So we strongly recommend to get started early with the design and implementation.
The project needs to be implemented in C++ and uploaded to Gradescope’s “Project 1” assignment. It will be graded using autograder, so be very precise about the input and output formats
discussed later. Your submission should contain source files along with a makefile. The name of the
executable generated by makefile must be “project1.out”. Please note that it is possible that your
program could have some unexpected behavior on Gradescope’s autograder compared to whatever
1
machine you wrote the code on, so submit your program early and make sure it is bug free on
Gradescope. You are to implement your own TST, so do not use any library that automatically
does this for you (i.e. it is NOT OK to use STL containers other than vector). Gradescope score
will be manually overridden if any such library is used.
2 Input and Output
Gradescope will pass a string of commands via argv[1]. Each command will be separated by a
comma. The input output format for each functionality is as followed:
1. Lookup a given word. The TST should be searched to find the word. The program should
print out“[word] found”, along with the count of the word. If the word is not found the
program should output“[word] not found”. For both cases, the output string should end with
a newline.
Example:
lookup hello
hello found, count = 2
or if hello is not in the data structure
hello not found
2. Insert a word. If the word is not present, insert a new node for the word and set its counter
to 1. Otherwise, if the word is already present, then its counter should be increased by one.
The program should output“[word] inserted, new count = [count]”. There should be a newline
at the end of the output string.
Example:
insert goodbye
goodbye inserted, new count = 1
3. Delete a word. If the word has a count greater than 1 then the count gets decreased by 1
and the program should output “[word] deleted, new count = [count]”. If the word has count
1, then it should be removed from the data structures and the program should output ”[word]
deleted”. For both cases, the output string should end with a newline. Print nothing if the
word is not present in the TST (do not print an empty line).
Example:
delete yesterday
yesterday deleted, new count = 2
or if yesterday had a count of 1 before it was deleted
yesterday deleted
4. Do a range search. The program should print out all words alphabetically in between (and
including if present) the two words provided in the range search that are present in the TST.
You may assume that the first word will not be greater than the second word for the range
search parameters. Each result word should end with a newline. Note that, one or both words
passed as parameters may not be present in the TST. In that case, you need to print the words
present in the TST and fall in this range. If there is no result for the range search then the
program should not print any word.
2
Example:
range search band to cat
band
bankers
bat
cab
calling
band
bankers
bat
cab
calling
2.1 Full Test Example
Your program receives the commands through argv[1]. In the following example we have that the
starting count of hello is 2, of yesterday is 3, and goodbye is not present in the data structure. We
also have that the only words in between band and cat in the data structure are: band, bankers, bat,
and cab.
Gradescope passes the following commands through argv[1]:
lookup hello, insert goodbye, delete yesterday, insert hello, delete goodbye, range search
band to cat
We expect the following output:
hello found, count = 2
goodbye inserted, new count = 1
yesterday deleted, new count = 2
hello inserted, new count = 3
goodbye deleted
band
bankers
bat
cab
Note: In order to check your program thoroughly, we may also run additional test cases on CSIL
machine. The format of the test cases will be exactly same. That is, you will be given same
input as above and we will expect the same output. Please make sure you name the executable as
project1.out (this can be done using makefile). Not adhering to the instruction might result in
significant delays in grading or no score for the assignment.