CS 14 Ternary Search Tree

Ternary Search Tree

In this homework, you will work on a Ternary Search Tree. First, read the file TSTs.pdf that contains the basic concepts about Ternary Search Tree. This is not an easy assignment as it may seem to be. You should start early and consider the hints at the bottom of this page.

In summary, Ternary Seach Trees were proposed by Bentley and Sedgewick¹ as an optimal option for sorting and searching multikey data, specially when the keys are character strings.

Figure 1 illustrates the pseudocode of the operations for the ADT TST. Figure 2 shows the UML diagram for the class TST, and Figure 3 for the struct TSTNode.

// TSTNode is the type of the items stored in the tree

+ TST()
// Creates an empty TST.

+ virtual ~TST()
// Destroys a TST.

+ void readDictionary (const string & file_name)
// Reads the file file_name 
// Stores each line as one string in a TST.

+ void insertString (const string & string_ref)
// Adds the string string_ref to the TST.

+ bool hasString(const string & string_ref) const
// Returns true if the string string_ref exists in the TST.
// Otherwise, returns false.

+ void printCompletions(const string & string_ref) const
// Prints, in alphabetical order, all words in the TST 
// that have string_ref as prefix.

- bool hasPrefix (const string & string_ref, 
       TSTNode * & node_ptr, int & char_idx) const
// Auxiliary function.
// Searches for the node corresponding to the prefix string_ref.
// If it finds the node, it sets node_ptr to a pointer to 
// the respective node, and returns true.
// If is does not find the node, it sets node_ptr to a pointer to 
// the last node found, char_idx to the index of the 
// character in the prefix string associated with that node, and 
// returns false.

Figure 1. Pseudocode for the ADT TST Operations

Figure 2. UML diagram for the class TST

Figure 3. UML diagram for the struct TSTNode

Auxiliary sources

Ternary Search Trees, Jon Bentley and Bob Sedgewick.
Plant your data in a ternary search tree, Wally Flint.
Interesting application: Data Structures and Search Trees, by Bryan Hyde, describes how biologists use TSTs to find short DNA sequences that could be in a sequence of thousands of genes.
¹ Bentley, J.L, Sedgewick, R. Fast Algorithms for Sorting and Searching Strings. Symposium on Discrete Algorithms (ACM SIAM), 1997.

The Assignment

Write an implementation of the ADT TST that uses a TSTNode to represent the nodes. So, you will have two files: TST.h (tree header) and TST.cc (tree implementation).

Write a main program (tree.cc) that reads a dictionary from a given file and creates a ternary search tree. We will be using /usr/share/dict/words on hill. Add to tree.cc the word completion function. Given a word as parameter, this function returns the list of its completions, which means the words in the dictionary that start with the parameter. For example:

	
Enter name of dictionary file: dictionary.txt

Enter word (0 to end):
batman

List of completions for the prefix "batman":
batman

-------------------------------------------------

Enter word (0 to end):
acceen

List of completions for the prefix "acceen":
No completions found for the prefix "acceen".

-------------------------------------------------

Enter word (0 to end):
accen

List of completions for the prefix "accen":
accend
accendibility
accendible
accension
accensor
accent
accented
accenting
accentless
accentor
accentuable
accentual
accentuality
accentually
accentuate
accentuated
accentuating
accentuation

-------------------------------------------------

Enter word (0 to end):
0

Hints and considerations

1. This is not an easy assignment as it may seem to be. You should start early and consider the following hints:

Practice inserting strings into the tree by hand until you fully understand how it works.
The code to insert a string and the code to check if one given string is in the tree have similar structures.
The in-order traversal is a little bit different from the regular (binary) trees in-order traversal. Take your time to understand how it works before coding.
Use a small version of the dictionary that we are providing as a test dictionary.

2. Keep in mind the following considerations:

Modularity/Modifiability. Use functions for different tasks.
Easy of use. Prompt the user for input in a manner that makes it clear what it expects. Label the output.
Fail-safe programming. Check for error in input. Check for error in logic. Test to invalid input data. Functions should check their invariants, enforce their preconditions, and check the values of their arguments.
Style. Have and keep the same identifier and indentation styles.
Easy debugging/readability. Write comments explaining all functions, variables, constants, and main segments of your code. Use reasonable/intuitive names for your functions, variables, and constants.