Write an Electronic Telephone Directory application in Java, using a Binary Sear
ID: 3813498 • Letter: W
Question
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<dataType extends Comparable<? super dataType>> extends BinaryTree<dataType>
{
public void insert ( dataType d )
{
if (root == null)
root = new BinaryTreeNode<dataType> (d, null, null);
else
insert (d, root);
}
public void insert ( dataType d, BinaryTreeNode<dataType> node )
{
if (d.compareTo (node.data) <= 0)
{
if (node.left == null)
node.left = new BinaryTreeNode<dataType> (d, null, null);
else
insert (d, node.left);
}
else
{
if (node.right == null)
node.right = new BinaryTreeNode<dataType> (d, null, null);
else
insert (d, node.right);
}
}
public BinaryTreeNode<dataType> find ( dataType d )
{
if (root == null)
return null;
else
return find (d, root);
}
public BinaryTreeNode<dataType> find ( dataType d, BinaryTreeNode<dataType> 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<dataType> delete ( dataType d, BinaryTreeNode<dataType> 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<dataType> findMin ( BinaryTreeNode<dataType> node )
{
if (node != null)
while (node.left != null)
node = node.left;
return node;
}
public BinaryTreeNode<dataType> removeMin ( BinaryTreeNode<dataType> 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<dataType>
{
BinaryTreeNode<dataType> root;
public BinaryTree ()
{
root = null;
}
public int getHeight ()
{
return getHeight (root);
}
public int getHeight ( BinaryTreeNode<dataType> 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<dataType> node )
{
if (node == null)
return 0;
else
return 1 + getSize (node.getLeft ()) + getSize (node.getRight ());
}
public void visit ( BinaryTreeNode<dataType> node )
{
System.out.println (node.data);
}
public void preOrder ()
{
preOrder (root);
}
public void preOrder ( BinaryTreeNode<dataType> node )
{
if (node != null)
{
visit (node);
preOrder (node.getLeft ());
preOrder (node.getRight ());
}
}
public void postOrder ()
{
postOrder (root);
}
public void postOrder ( BinaryTreeNode<dataType> node )
{
if (node != null)
{
postOrder (node.getLeft ());
postOrder (node.getRight ());
visit (node);
}
}
public void inOrder ()
{
inOrder (root);
}
public void inOrder ( BinaryTreeNode<dataType> node )
{
if (node != null)
{
inOrder (node.getLeft ());
visit (node);
inOrder (node.getRight ());
}
}
public void levelOrder ()
{
if (root == null)
return;
BTQueue<dataType> q = new BTQueue<dataType> ();
q.enQueue (root);
BinaryTreeNode<dataType> 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>
{
dataType data;
BinaryTreeNode<dataType> left;
BinaryTreeNode<dataType> right;
public BinaryTreeNode ( dataType d, BinaryTreeNode<dataType> l, BinaryTreeNode<dataType> r )
{
data = d;
left = l;
right = r;
}
BinaryTreeNode<dataType> getLeft () { return left; }
BinaryTreeNode<dataType> getRight () { return right; }
}
BinaryTreeQueue:
public class BTQueue<dataType>
{
BTQueueNode<dataType> head;
BTQueueNode<dataType> tail;
public BTQueue ()
{
head = null;
tail = null;
}
public BinaryTreeNode<dataType> getNext ()
{
if (head == null)
return null;
BTQueueNode<dataType> qnode = head;
head = head.next;
if ( head == null )
tail = null;
return qnode.node;
}
public void enQueue ( BinaryTreeNode<dataType> node )
{
if (tail == null)
{
tail = new BTQueueNode<dataType> (node, null);
head = tail;
}
else
{
tail.next = new BTQueueNode<dataType> (node, null);
tail = tail.next;
}
}
}
BinaryTreeQueueNode:
public class BTQueueNode<dataType>
{
BinaryTreeNode<dataType> node;
BTQueueNode<dataType> next;
public BTQueueNode ( BinaryTreeNode<dataType> n, BTQueueNode<dataType> 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
Explanation / Answer
#ifndef PERSON_H #define PERSON_H #include #include using namespace std; class person { public: person(); // default constructor person(string n); person(string n, string pn); friend bool operator< (person, person); friend bool operator> (person, person); friend bool operator==(person, person); person operator=(person); string fname; string lname; string phone; }; // end Person #endif #include #include #include "person.h" using namespace std; class PhoneBook { private: struct tree_node { tree_node* left; tree_node* right; person data; void printnode(); }; tree_node* root; public: PhoneBook() { root = NULL; } bool isEmpty() const { return root==NULL; } void load(const string& fname); void store(const string& fname); void find(person d); void print_inorder(); void clear(); void inorder(tree_node*); void insert(person); void remove(person); void edit(person d); }; #include "person.h" #include #include person::person(string n, string ph){ char* cstr = new char[n.size()+1]; strcpy(cstr,n.c_str()); fname.assign(strtok(cstr," ")); lname.assign(strtok(NULL," ")); phone = ph; } person::person(string n) { char* cstr = new char[n.size()+1]; strcpy(cstr,n.c_str()); fname.assign(strtok(cstr," ")); lname.assign(strtok(NULL," ")); } person::person() { // Person is empty here } bool operator< (person p1, person p2){ if(p1.lname == p2.lname) return p1.fname p2.fname; else return p1.lname > p2.lname; } bool operator==(person p1,person p2){ if( p1.fname == p2.fname && p1.lname == p2.lname && p1.phone == p2.phone ) return true; else return false; } person person::operator=(person p1){ fname = p1.fname; lname = p1.lname; phone = p1.phone; return *this; } #include "PhoneBook.h" #include "person.h" #include void PhoneBook::insert(person d) { tree_node* t = new tree_node; tree_node* parent; t->data = d; t->left = NULL; t->right = NULL; parent = NULL; if(isEmpty()) root = t; else { tree_node* curr; curr = root; while(curr){ parent = curr; if(t->data > curr->data) curr = curr->right; else curr = curr->left; } if(t->data data) parent->left = t; else parent->right = t; } } void PhoneBook::remove(person d){ bool found = false; if(isEmpty()) { coutdata) curr = curr->right; else curr = curr->left; } } if(!found){ coutright == NULL)){ if(curr->left == NULL && curr->right != NULL) { if(curr == root){ root = curr->right; delete curr; return; } if(parent->left == curr) { parent->left = curr->right; delete curr; } else { parent->right = curr->right; delete curr; } } else { if(curr == root){ root = curr->left; delete curr; return; } if(parent->left == curr){ parent->left = curr->left; delete curr; } else{ parent->right = curr->left; delete curr; } } return; } if( curr->left == NULL && curr->right == NULL){ if(curr == root){ root = NULL; return; } if(parent->left == curr) parent->left = NULL; else parent->right = NULL; delete curr; return; } if (curr->left != NULL && curr->right != NULL){ tree_node* chkr; chkr = curr->right; if((chkr->left == NULL) && (chkr->right == NULL)) { curr = chkr; delete chkr; curr->right = NULL; } else { if((curr->right)->left != NULL){ tree_node* lcurr; tree_node* lcurrp; lcurrp = curr->right; lcurr = (curr->right)->left; while(lcurr->left != NULL){ lcurrp = lcurr; lcurr = lcurr->left; } curr->data = lcurr->data; delete lcurr; lcurrp->left = NULL; } else { tree_node* tmp; tmp = curr->right; curr->data = tmp->data; curr->right = tmp->right; delete tmp; } } return; } } void PhoneBook::print_inorder() { inorder(root); } void PhoneBook::inorder(tree_node* p) { if(p != NULL) { if(p->left) inorder(p->left); p->printnode(); if(p->right) inorder(p->right); } else return; } void PhoneBook::find(person d){ bool found = false; if(isEmpty()) { cout curr->data) curr = curr->right; else curr = curr->left; } } if(!found) { coutRelated Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.