CS1102 02/03 Semester 2 Lab 4A
Problem 1 (30%)
In this problem, you are to modify the code for binary search tree in your textbook (pg 471 -- 474). The source code can be downloaded from
http://www.comp.nus.edu.sg/cs1102/lab4a/.
Your task is to augment the implementation for binary search tree in your textbook so that every node maintains the following members:
· TreeNode parent a reference to the parent node. The parent field for the root node points to itself.
· int height the height of the node.
· int size the size of the subtree rooted at the node.
· TreeNode successor a reference to the node with the next larger value in the tree.
· TreeNode predecessor a reference to the node with the next smaller value in the tree.
All five fields must be correctly updated after insertion and deletion on the tree.
Input
Input to your program is a series of insert and delete instructions. Each line in the input contains an instruction of the form <operation> <data>. <operation> must be either INSERT or DELETE, and <data> is an integer. Your program should read these instructions and perform the sequence of operations as specified by the instructions, starting with an empty BST.
Output
Your program should perform preorder traversal on the BST that you have constructed, and output each of the members that you added, in the order specified above, one line per node. For references to TreeNode, you should output the item stored in the referenced TreeNode.
Example Input
INSERT 4
INSERT 9
INSERT 2
INSERT 1
INSERT 10
INSERT 11
DELETE 10
DELETE 1
INSERT 8
Example Output
4 3 5 8 2
4 2 1 4 _
4 2 3 11 8
9 1 1 9 4
9 1 1 _ 8
Problem 2 (70%)
The goal of this problem is to implement predictive text-based input for mobile phone using a tree-based data structure called trie.
Numeric inputs 1 to 9 from the mobile phone keypad can be mapped into a set of three uppercase letters are given below.
|
2 |
ABC |
|
3 |
DEF |
|
4 |
GHI |
|
5 |
JKL |
|
6 |
MNO |
|
7 |
PQRS |
|
8 |
TUV |
|
9 |
WXYZ |
To enter a word in a mobile phone, a user enters a sequence of digits whose letters in the word are mapped from. For example, to enter the word LAB, the user enters 522.
You are asked to implement a program that maintains a dictionary, takes in a sequence of digits as input, and outputs words in the dictionary in alphabetical order that could be represented by that sequence of digits. Your program must take care of the following two properties.
Non-uniqueness. Since each digit can represent up to three letters, the word represented by a sequence of digits might not be unique. For example, 228 could represent CAT, ACT or BAT. In this case, your program must output all three choices.
Prediction. You can predict the word the user wants to enter if there is only one possible way the word could be completed. For instance, 23 corresponds to AD, AE AF, BE, CE and CF. Besides matching the word BE, your program should also output AFTER and CERTAIN, because they are the only words in the dictionary that matches the prefix AF and CE respectively. There are more than one words that matches the prefix AD (ADD, ADDITION, ADDICT etc) so these words starting with AD should not be in the output.
For simplicity, you only need to output complete words in the dictionary (i.e. no partial matching as in normal mobile phone). You can assume that the input dictionary contains only words with uppercase letters (no blanks, numbers, symbols and punctuations).
To implement this program efficiently, you will need to use a tree-based data structure called trie. A trie is a structure commonly used to represent words in a dictionary. Each path from a root to a leaf corresponds to one word in the dictionary. To avoid confusion between words like THE and THEN, we add a special end-marker $ to the ends of all words. Each node in the trie can have at most 27 children, one for each letter, and $. The following figure shows an example of the trie data structure for words {THIS, THE, THEN, THIN, SING, SIN}.
In this problem, you should implement the trie data structure, populate it with words from an input dictionary, and use it to covert sequence of input digits into word(s).
Some sample dictionaries can be downloaded from
http://www.comp.nus.edu.sg/cs1102/lab4a/.
The dictionary contains one word per line.
Implementation Hints
· You will notice that most nodes will have far fewer than 27 children. For simplicity, you can use an array to store references to children, even though it is a waste of space.
· You can save some space by not storing nodes with $.
· Think recursively.
·
Design before you implement. This is not as difficult as you think. The solution should be at most 300 lines.
Input
The input contains both the dictionary and a sequence of mobile phone inputs, one per line. The dictionary can be read from a local file (good for testing and debugging) or read from stdin (what OJ will use for testing).
Option 1: To read from a local file, the first line of the input must be #filename, where filename is the name of a dictionary file. This is followed by multiple lines of mobine phone inputs.
Option 2: To read the dictionary from stdin, the inputs must begin with words in the dictionary, one per line. Followed by multiple lines of mobile phone inputs. Since dictionary must contains only uppercase letters, any numeric inputs indicates the end of dictionary words and the begin of mobile phone inputs.
Output
The output contains either the exact word, or the possible words represented by the digits on the corresponding line. Words on the same line must be in alphabetical order.
Sample Input 1
#850Basic.txt
23
5683
737
Sample Output 1
AFTER BE CERTAIN
LOUD LOVE
PERSON
REPRESENTATIVE REQUEST
Sample Input 2
THIS
THIN
THE
SIN
SING
THEN
SINGER
746
74643
Sample Output 2
SIN
SINGER