Write an Electronic Telephone Directory application in Java, using a Binary Search Tree (BST) as an internal data structure. (All work is to be done in Unix/Ubuntu Terminal)

Your BST implementation can be created from scratch or re-used from anywhere. You may NOT replace the BST with a different data structure.

The data you are given (see attached file) has the following format:

51850 Kianna Squares, Terre Haute|552.531.3674|Gislason Kenna 17386 Stephanie Parks, Palm Springs|018-594-2935 x716|Hickle Leone 97354 Queen Squares, Birmingham|(332)985-4036|Moore Gilbert

The fields are: address, telephone number, name. Every full name has a last name and a first name. The fields are separated by "|". The lines of the file are unsorted.

When loading this data, the key you must use is the full name. You need to parse each line of text and extract the name. Each record will therefore contain: {full_name, full_entry}.

Your tasks are as follows:

Write an application PrintIt to load the data file into a BST and then traverse the BST and print out the telephone listing in order of name. Where two people have the same names, the relative order of those entries does not matter.

Write an application SearchIt to search for an entry based on a full name. Your application must read in a list of queries from a query file, search for each one and output "Not found" or the full entry for each query. The data file must be loaded only once.

Write an application SearchItLinear with the same functionality as SearchIt, but replace your BST with an unsorted array. Rewrite the necessary algorithms.

Conduct an experiment with SearchIt and SearchItLinear to demonstrate the speed difference for searching between a BST and a linear array. Extract names from the data file and use only these names as queries. Use multiple subsets of the data from n=1 up to n=10000. Draw a graph that illustrates the relative performance of your applications for different values of n. Use the "time" Unix application to measure application execution time. If your computer is too fast to take accurate readings of small amounts of time, run the experiment multiple times (possibly using a shell script).

Dev requirements:

As a software developer, you are required to make appropriate use of the following tools:

git, for source code management

junit, for unit testing

javadoc, for documentation generation

make, for automation of compilation, documentation generation, unit testing and cleaning of files

Submission requirements:

Submit a .tar.gz compressed archive containing:

Makefile

src/

all source code

bin/

all class files

doc/

javadoc output

test/

junit test classes

Do not submit the junit jar files or the git repository.

The Binary search tree data structures were given to us:

Binary Search Tree:

public class BinarySearchTree> extends BinaryTree { public void insert ( dataType d ) { if (root == null) root = new BinaryTreeNode (d, null, null); else insert (d, root); } public void insert ( dataType d, BinaryTreeNode node ) { if (d.compareTo (node.data) <= 0) { if (node.left == null) node.left = new BinaryTreeNode (d, null, null); else insert (d, node.left); } else { if (node.right == null) node.right = new BinaryTreeNode (d, null, null); else insert (d, node.right); } } public BinaryTreeNode find ( dataType d ) { if (root == null) return null; else return find (d, root); } public BinaryTreeNode find ( dataType d, BinaryTreeNode node ) { if (d.compareTo (node.data) == 0) return node; else if (d.compareTo (node.data) < 0) return (node.left == null) ? null : find (d, node.left); else return (node.right == null) ? null : find (d, node.right); } public void delete ( dataType d ) { root = delete (d, root); } public BinaryTreeNode delete ( dataType d, BinaryTreeNode node ) { if (node == null) return null; if (d.compareTo (node.data) < 0) node.left = delete (d, node.left); else if (d.compareTo (node.data) > 0) node.right = delete (d, node.right); else if (node.left != null && node.right != null ) { node.data = findMin (node.right).data; node.right = removeMin (node.right); } else if (node.left != null) node = node.left; else node = node.right; return node; } public BinaryTreeNode findMin ( BinaryTreeNode node ) { if (node != null) while (node.left != null) node = node.left; return node; } public BinaryTreeNode removeMin ( BinaryTreeNode node ) { if (node == null) return null; else if (node.left != null) { node.left = removeMin (node.left); return node; } else return node.right; } }

Binary Tree:

public class BinaryTree { BinaryTreeNode root; public BinaryTree () { root = null; } public int getHeight () { return getHeight (root); } public int getHeight ( BinaryTreeNode node ) { if (node == null) return -1; else return 1 + Math.max (getHeight (node.getLeft ()), getHeight (node.getRight ())); } public int getSize () { return getSize (root); } public int getSize ( BinaryTreeNode node ) { if (node == null) return 0; else return 1 + getSize (node.getLeft ()) + getSize (node.getRight ()); } public void visit ( BinaryTreeNode node ) { System.out.println (node.data); } public void preOrder () { preOrder (root); } public void preOrder ( BinaryTreeNode node ) { if (node != null) { visit (node); preOrder (node.getLeft ()); preOrder (node.getRight ()); } } public void postOrder () { postOrder (root); } public void postOrder ( BinaryTreeNode node ) { if (node != null) { postOrder (node.getLeft ()); postOrder (node.getRight ()); visit (node); } } public void inOrder () { inOrder (root); } public void inOrder ( BinaryTreeNode node ) { if (node != null) { inOrder (node.getLeft ()); visit (node); inOrder (node.getRight ()); } } public void levelOrder () { if (root == null) return; BTQueue q = new BTQueue (); q.enQueue (root); BinaryTreeNode node; while ((node = q.getNext ()) != null) { visit (node); if (node.getLeft () != null) q.enQueue (node.getLeft ()); if (node.getRight () != null) q.enQueue (node.getRight ()); } } }

BinaryTreeNode:

public class BinaryTreeNode { dataType data; BinaryTreeNode left; BinaryTreeNode right; public BinaryTreeNode ( dataType d, BinaryTreeNode l, BinaryTreeNode r ) { data = d; left = l; right = r; } BinaryTreeNode getLeft () { return left; } BinaryTreeNode getRight () { return right; } }

BinaryTreeQueue:

public class BTQueue { BTQueueNode head; BTQueueNode tail; public BTQueue () { head = null; tail = null; } public BinaryTreeNode getNext () { if (head == null) return null; BTQueueNode qnode = head; head = head.next; if ( head == null ) tail = null; return qnode.node; } public void enQueue ( BinaryTreeNode node ) { if (tail == null) { tail = new BTQueueNode (node, null); head = tail; } else { tail.next = new BTQueueNode (node, null); tail = tail.next; } } }

BinaryTreeQueueNode:

public class BTQueueNode { BinaryTreeNode node; BTQueueNode next; public BTQueueNode ( BinaryTreeNode n, BTQueueNode nxt ) { node = n; next = nxt; } }

Excerpt from the text file containing data to be put in binary search tree:

69026 Upper, Mission Viejo|1-077-306-6380 x65575|Lueilwitz Candelario 98289 Alexander Pine #571, Walnut|955.747.0624 x2156|Wolf Mariane 51850 Kianna Squares, Terre Haute|552.531.3674|Gislason Kenna 17386 Stephanie Parks, Palm Springs|018-594-2935 x716|Hickle Leone 97354 Queen Squares, Birmingham|(332)985-4036|Moore Gilbert