# CS143 – Lab 4 DecimalSearchTree

CS143 – Lab 4
DecimalSearchTree
Introduction
A binary search tree is a tree structure where each node contains a unique value, has at most two
children, contains values in the left subtree that are less than that in the node and values in the right
subtree that are greater than that in the node. However, a binary tree is not the only possible tree
structure.
A decimal search tree contains unique values just like a binary search tree, but instead of having at most
two children each node has at most ten children. If the objects being saved in the tree have a sorting key
that is a non-negative whole number with a known maximum number of digits (k), then every operation
reduces to O(k), because each layer of the tree represents a different digit in the key. The layers of the
tree are in Most Significant Digit (MSD) order, with the most significant digit at the top and the least
significant digit at the bottom of the tree.
Each node of a decimal search tree is made up of a value and a 10-element array of children. All branch
nodes have a null value, and all leaf nodes that contain a non-null value have a children array filled with
nulls. This puts all of the actual data at the lowest level in the tree. Below is a partially-filled decimal tree
for three-digit keys:
root
null value
children[0..9]

 child 2null valuechildren[0..9]

child 5
null value
children[0..9]
child 0
obj1 value
null children
key = 250
value = obj1
child 6
obj2 value
null children
key = 256
value = obj2
child 7
null value
children[0..9]
child 4
null value
children[0..9]
child 9
obj3 value
null children
key = 749
value = obj3
The decimal search tree can then be used like a map or dictionary where the keys are always nonnegative whole numbers. (This method of sorting data is very similar to the radix sort.) Some examples
of collections that lend themselves to decimal search trees include students with numeric student ID
numbers, employees with social security numbers, and inventory items with unique product ID
numbers.
The following operations are possible:
• contains(key) – returns true if a value with the given key exists in the tree, false if not
• get(key) – returns the value at the given key, or null if it does not exist
• insert(value) – inserts a value that contains a unique non-negative whole-number key, returning
true if the value was inserted and false if not
• remove(key) – removes the value with the given key from the tree, returning true if the value
was found and removed and false if not
• isEmpty() – returns true if all values are null, false if not
Lab Overview
In Lab 4 your task is to create a sorted decimal map based on a decimal search tree interface. It must be
generic, implement all of the above methods, and provide an iterator. The generic class must extend the
DecimalSortable interface, which requires a getKey() method.
In the Lab 4 module you are given a NetBeans project that contains the following classes:
• A DecimalSearchTree interface that defines the above methods. (This interface just needs its
• A DecimalSortable interface that defines the getKey() method. (This interface is complete.)
• A Product domain class that implements the DecimalSortable interface. (This class is complete
and can be used to create a collection to test the decimal map.)
• A SortedDecimalMap concrete class that implements the above ADT. (This class needs most of
• A nested DecimalIterator class that uses an underlying queue. (The fillQueue recursive method
is currently just a stub that needs to be written. The rest is complete.)
• A nested DecimalNode class. (This code is complete.)
You must complete the SortedDecimalMap and DecimalIterator classes, create a JUnit test class, and
thoroughly test SortedDecimalMap. The following requirements and limitations apply:
• You may not add any other fields or methods to any of the classes or interfaces.
• You must write code for all of the methods marked with a TODO.
• You must create JUnit test methods as necessary to assure 100% coverage of the
SortedDecimalMap class, including all iterator and node methods.
Group Work
For the first week, you will work on this lab individually. Get it working the best you can. Get a test class
replace the method bodies marked with a TODO comment with the correct code.
Bring your code to class the first day of the second week. You will then be assigned a group, and that
group will have a Google Sheets document to share. Post your code in the correct cell for each of the
methods listed in the column with your name at the top. Then meet with your group and compare
solutions. Choose the best solution or create a new solution out of a combination of your code. Place
the code in the “final version” column.
Now open a clean version of the NetBeans project, and copy and paste the final code solutions into the
proper methods. Spend some time examining each group member’s test class. From these build a test
that provides the fullest code coverage. Be sure to clean up indentation and spacing, name variables
using proper Java naming conventions, and create proper JavaDoc comments. When you are satisfied
with your work, zip up the NetBeans project and submit it to the Lab 4 assignment. Do not edit or delete