CS 596 Assignment 2

	CS 596 Fall Semester, 1998 Assignment 2
	To Assignment Index San Diego State University -- This page last updated 20-Sep-98

Due:

September 30, in class for SDSU section,

October 1 in class for Qualcomm section

Implement a ternary search tree with integer keys. A ternary search tree is like a binary search tree, except each node in the tree has up to two keys and three subtrees. Figure A below shows a node with keys 10 and 20. The subtree A contains keys with values less than 10, the subtree B contains keys with values between 10 and 20. The subtree C contains keys with values greater than 20. When you insert a key into an empty ternary tree, that key becomes a key in the root node. The second key inserted into the ternary tree becomes the second key in the root node. These two keys are kept in order. All subsequent keys are inserted using the same rules in the proper subtree of the root note. So if we were to insert the numbers 10, 40, 7, 20, 5, 6, 30, 15 we would get the tree in Figure B. Your ternary tree needs to have the following methods:

put( int key, Object value) which stores the key and object in the proper location in the tree as described above. If key is already in the tree, its value is changed to the new value.

get( int key) returns the value stored in with the given key in the tree.

contains( int key) returns true if the tree contains the key.

toString() returns a string representation of the tree using the following recursive rule: for each node print "(" then left subtree, smallest key, middle subtree, largest key, right subtree ")". So toString() on the tree in figure B will result in (( 5 (6) 7 ) 10 ( (15) 20 30) 40 )

Your ternary tree and any support classes need to be in a package. Your test program can not be in that package. Test input will be given later.

Figure A

Figure B

visitors since 20-Sep-98