UCR CS 14: Introduction to Data Structures and Algorithms

Spring Quarter 2003 / Class webpage



Assignment 04: Ternary Search Tree

Remember:

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 Sedgewick1 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


The Assignment (10 points)

5 points. 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).

2 points. Write a main program (tree.cc) that reads a dictionary from a given file and creates a ternary search tree. You can download the dictionary we are going to use: dictionary.txt.

3 points. Add to tree.cc the completion word 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