Java Data Structure

For this exercise, implement a Table. It is an Abstract Data Type that models a dictionary or look$-$up

table, with information on collected items accessed by a unique, designated "key" for each item. One

example is the Motor Vehicle Department's driver information data accessed by driver identification code.

For this exercise, define a Table that supports the following operations:

initialize $-$ initialize an empty table $($this is the constructor$).$

insert $-$ insert an item in the table, given the item.

search $-$ given a key, return the associated data item.

getHeight $-$ return the height of the tree.

getSize $-$ return the number of nodes in the tree.

getAverageLevel $-$ return the average level of the nodes in the tree.

showTree $-$ display the contents of the tree in a tree$-$like fashion

toString $-$ display the entire contents of the table in order by their keys.

Remember that a Table is a collection of items with unique keys $($no duplicates$).$ If an insertion attempts

to add an item with a key that is already in the set, just ignore the insertion. This is intended as a general$-$

purpose tool, so there will be no input from the user and no output to the user $($inside the Table class$).$

When you do 'toString,$\text{'}$ return a String that presents the nodes of the tree in ascending order. When you

do 'showTree', display the nodes in a fashion that looks a little like a tree. For example, consider the

following binary search tree:

$\{$:$77$:$\}$

$8288($but only one item per line$).$

The result from showTree should look like the following. $($Turn your head to the left and look at it

sideways.$)$

Implementation:

Implement the Table as a Binary Search Tree. Define a Table class for the entire tree and a TNode class

for each node of the tree. In the TNode class, use three 'public' data members, and no member functions

$($except possibly a constructor with one parameter$).$ For the Binary Search Tree, keep only one data

member: a reference to the root. Represent the empty tree with null, and leaf nodes referring to two nulls

$($just as we have done in class and in the examples$).$ Use recursive algorithms for all the tree operations.

$($To compute the average level, write a function that computes the sum of the levels of the nodes in the

tree, then take the result of this function divided by the number of nodes $-$ getSize.$)$

To generalize the implementation, define a Keyed interface and use it as the type of all items and keys.

The Keyed interface must support the following operations:

int keyComp$($Keyed other$)$;

$//$ return a negative number if less than other, $0$ if equal, and positive if greater

String briefSummary$()$;

$//$ return a short string that summarizes the item, to fit in the showTree display

Notice that 'briefSummary' is not a replacement for 'toString'. It is an alternative that produces an

abbreviated summary of the item $($instead of the complete summary that comes from 'toString'$).$ It is only

to be used by the 'showTree' method.

To support the application, define two simple classes to provide objects in the tables.

First, an 'NBAPlayerKey', which includes an integer jersey number and a string to represent the team

name $($like $17$ for the Suns$).$ For this class, provide a constructor that initializes both data members, and

accessors for both, as well as the methods necessary to implement the 'Keyed' interface. In the 'keyComp'

method, order the data items by team name, and then by jersey number. Two instances are equal only if

both data fields are the same. For example, jersey #$1$ for the "Suns" is "less than" the jersey #$2$ for the

"Suns", and jersey #$2$ for the "Suns" is greater than jersey #$2$ for the "Lakers". In the 'briefSummary"

method, just return the jersey number and the first three letters of the team name $($to keep it short for the

'showTree' method. $($You can use the 'substr' method in the String class.$)$

Second, an 'NBAPlayer', which includes an integer jersey number, a string for the team name, a string for

the name of the player, and a double for the points per game average. This class must be a subclass of

'NBAPlayerKey'. In addition to the inherited data members and member functions, add data members for

player name and points per game. Also add an accessor for each of these. This class will also implement

the 'Keyed' interface, but using the methods inherited from the parent class to satisfy the requirements.

For the showTree method, do a reverse$-$order traversal $($right$-$root$-$left$)$ and pass the level of the root to the

recursive function that displays each subtree. $($Recall that the level of the child is one more than the level

of the parent.$)$ Use the level of each node to compute how many spaces to insert in front of the data of

each node. Call the briefSummary method from showTree $($but not toString$).$

Application:

For phase I, exercise all the operations of a table. Create one table of 'NBAPlayer's, then allow the user to

repeatedly perform selected operations on this table. Include a menu option for each of the operations

listed for a Table $($including the c