Hello, I'm suppose to write a Java program using NetBeans IDE 8.2 that does the following:

Empirically Demonstrate the Difference in Performance between Searching Unbalanced Binary Search Trees and AVL Trees

Compare Attributes of AVL Trees and Unbalanced Binary Search Trees

In detail, searching a binary search tree is O(h), where h is the height of the tree. On average, a binary search tree with n keys generated from a random series of insertions has expected height O(log n). A binary search tree may degenerate into a list, the so-called pathological case. In that case, searching is O(n).

You will insert a series of words into an AVL tree and a BST tree from a text file, whose name will be supplied as a command line argument. You will convert these words to uppercase prior to inserting them into the trees to make searching for them easier. Your program will generate the following tables:

Tables 1-2 show words from the insertions into the binary search and AVL trees using level-order traversal, as indicated in the table subheading. Table 3 shows the size, height and diameter of each tree. Table 4 shows the total number of node accesses (visits) in each tree when the words from the file are searched for in the tree.

The nodes in either data structure will contain words (strings). You will need to open the text file, read the words from the file and insert them into both trees, simultaneously. After inserting the data, you will close the file.

To generate Table 4, you will need to reopen the file, read it and search for each word in the tree while counting the total number of node visits (accesses) during the search for the words in the trees. Note that the number of node accesses when searching for a word is 1 + depth of the word in the tree. Be sure to search for the uppercase version of each word.

Name your program TwoTreesAnalyzer. The three text files words0.txt, words1.txt and words2.txt below along with the other Java codes AVLTreeException.java, AVLTreeAPI.java, AVLTree.java, BSTreeException.java, BSTreeAPI.java, BSTree.java and TwoTreesAnalyzer.java to help save time. Make all of them as class, except for BSTreeAPI.java and AVLTreeAPI, which should only be created as interfaces for the program. Also, only insert the code in where it says "insert code here" in comments.

Here are both the code and the text files.

Here are the following codes.

---------------------------------------------------------------------------------------------------

//AVLTree.java

package twotreesanalyzer; import java.util.ArrayList; import java.util.function.Function;

/** * Models an AVL tree. * @param data type of elements of the tree * @author * @since 99-99-9999 * @see AVLTreeAPI, AVLTreeException */

//public class AVLTree implements AvltreeAPI public class AVLTree> implements AVLTreeAPI { /** * The root node of this tree */ private Node root; /** * The number of nodes in this tree */ private int count; /** * A node of a tree stores a data item and references * to the child nodes to the left and to the right. */ private class Node { /** * the data in this node */ public E data; /** * the left child */ public Node left; /** * the right child */ public Node right; /** * the balanced factor of this node */ BalancedFactor bal; } /** Constructs an empty tree */ public AVLTree() { root = null; count = 0; }

public boolean isEmpty() { return (root == null); }

public void insert(E obj) { boolean[] forTaller; Node newNode = new Node(); newNode.bal = BalancedFactor.EH; newNode.data = obj; forTaller = new boolean[1]; if (!inTree(obj)) count++; root = insert(root,newNode, forTaller);

}

public boolean inTree(E item) { Node tmp; if (isEmpty()) return false; /*find where it is */ tmp = root; while (true) { int d = tmp.data.compareTo(item); if (d == 0) return true; else if (d > 0) { if (tmp.left == null) return false; else /* continue searching */ tmp = tmp.left; } else { if (tmp.right == null) return false; else /* continue searching for insertion pt. */ tmp = tmp.right; } } }

public void remove(E item) { boolean[] shorter = new boolean[1]; boolean[] success = new boolean[1]; Node newRoot; if (!inTree(item)) return; newRoot = remove(root,item, shorter, success); if (success[0]) { root = newRoot; count--; } }

public E retrieve(E item) throws AVLTreeException { Node tmp; if (isEmpty()) throw new AVLTreeException("AVL Tree Exception: tree empty on call to retrieve()"); /*find where it is */ tmp = root; while (true) { int d = tmp.data.compareTo(item); if (d == 0) return tmp.data; else if (d > 0) { if (tmp.left == null) throw new AVLTreeException("AVL Tree Exception: key not in tree call to retrieve()"); else /* continue searching */ tmp = tmp.left; } else { if (tmp.right == null) throw new AVLTreeException("AVL Tree Exception: key not in tree call to retrieve()"); else /* continue searching for insertion pt. */ tmp = tmp.right; } } }

public void traverse(Function func) { traverse(root,func); }

public int size() { return count; } /*===> BEGIN: Augmented public methods END: Augmented public methods

/** * A enumerated type for the balanced factor of a node */ private enum BalancedFactor { LH(-1),EH(0),RH(1); BalancedFactor(int aValue) { value = aValue; } private int value; }

/* private methods definitions */ /** * An auxiliary method that inserts a new node in the tree or * updates a node if the data is already in the tree. * @param curRoot a root of a subtree * @param newNode the new node to be inserted * @param taller indicates whether the subtree becomes * taller after the insertion * @return a reference to the new node */ private Node insert(Node curRoot, Node newNode, boolean[] taller) { if (curRoot == null) { curRoot = newNode; taller[0] = true; return curRoot; } int d = newNode.data.compareTo(curRoot.data); if (d 0) { curRoot.right = insert(curRoot.right,newNode,taller); if (taller[0]) switch(curRoot.bal) { case LH: // was left-high -- now EH curRoot.bal = BalancedFactor.EH; taller[0]=false; break; case EH: // was balance -- now RH curRoot.bal = BalancedFactor.RH; break; case RH: //was right high -- rotate curRoot = rightBalance(curRoot,taller); break; } return curRoot; } else { curRoot.data = newNode.data; taller[0] = false; return curRoot; } }

/** * An auxiliary method that left-balances the specified node * @param curRoot the node to be left-balanced * @param taller indicates whether the tree becomes taller * @return the root of the subtree after left-balancing */ private Node leftBalance(Node curRoot, boolean[] taller) { Node rightTree; Node leftTree; leftTree = curRoot.left; switch(leftTree.bal) { case LH: //left-high -- rotate right curRoot.bal = BalancedFactor.EH; leftTree.bal = BalancedFactor.EH; // Rotate right curRoot = rotateRight(curRoot); taller[0] = false; break; case EH: // This is an error System.out.println("AVL Tree Error: error in balance tree in call to leftBalance()"); System.exit(1); break; case RH: // right-high - requires double rotation: first left, then right rightTree = leftTree.right; switch(rightTree.bal) { case LH: curRoot.bal = BalancedFactor.RH; leftTree.bal = BalancedFactor.EH; break; case EH: curRoot.bal = BalancedFactor.EH; leftTree.bal = BalancedFactor.EH; /* LH */ break; case RH: curRoot.bal = BalancedFactor.EH; leftTree.bal = BalancedFactor.LH; break; } rightTree.bal = BalancedFactor.EH; // rotate left curRoot.left = rotateLeft(leftTree); //rotate right curRoot = rotateRight(curRoot); taller[0] = false; } return curRoot; }

/** * An auxiliary method that right-balances the specified node * @param curRoot the node to be right-balanced * @param taller indicates whether the tree becomes taller * @return the root of the subtree after right-balancing */ private Node rightBalance(Node curRoot, boolean[] taller) { Node rightTree; Node leftTree; rightTree = curRoot.right; switch(rightTree.bal) { case RH: //right-high -- rotate left curRoot.bal = BalancedFactor.EH; rightTree.bal = BalancedFactor.EH; // Rotate left curRoot = rotateLeft(curRoot); taller[0] = false; break; case EH: // This is an error System.out.println("AVL Tree Error: error in balance tree in call to rightBalance()"); break; case LH: // left-high - requires double rotation: first right, then left leftTree = rightTree.left; switch(leftTree.bal) { case RH: curRoot.bal = BalancedFactor.LH; rightTree.bal = BalancedFactor.EH; break; case EH: curRoot.bal = BalancedFactor.EH; rightTree.bal = BalancedFactor.EH; /* RH */ break; case LH: curRoot.bal = BalancedFactor.EH; rightTree.bal = BalancedFactor.RH; break; } leftTree.bal = BalancedFactor.EH; // rotate right curRoot.right = rotateRight(rightTree); //rotate left curRoot = rotateLeft(curRoot); taller[0] = false; } return curRoot; }

/** * An auxiliary method that Left-rotates the subtree at this node * @param node the node at which the left-rotation occurs. * @return the new node of the subtree after the left-rotation */ private Node rotateLeft(Node node) { Node tmp; tmp = node.right; node.right = tmp.left; tmp.left = node; return tmp; }

/** * An auxiliary method that right-rotates the subtree at this node * @param node the node at which the right-rotation occurs. * @return the new node of the subtree after the right-rotation */ private Node rotateRight(Node node) { Node tmp; tmp = node.left; node.left = tmp.right; tmp.right = node; return tmp; }

/** * An auxiliary method that in-order traverses the subtree at the specified node * @param node the root of a subtree * @param func the function to be applied to the data in each node */ private void traverse(Node node, Function func) { if (node != null) { traverse(node.left,func); func.apply(node.data); traverse(node.right,func); } }

/** * An auxiliary method that deletes the specified node from this tree * @param node the node to be deleted * @param key the item stored in this node * @param shorter indicates whether the subtree becomes shorter * @param success indicates whether the node was successfully deleted * @return a reference to the deleted node */ private Node remove(Node node, E key, boolean[] shorter, boolean[] success) { Node delPtr; Node exchPtr; Node newRoot; if (node == null) { shorter[0] = false; success[0] = false; return null; } int d = key.compareTo(node.data); if (d 0) { node.right = remove(node.right,key,shorter,success); if (shorter[0]) node = deleteLeftBalance(node,shorter); } else { delPtr = node; if (node.right == null) { newRoot = node.left; success[0] = true; shorter[0] = true; return newRoot; } else if(node.left == null) { newRoot = node.right; success[0] = true; shorter[0] = true; return newRoot; } else { exchPtr = node.left; while(exchPtr.right != null) exchPtr = exchPtr.right; node.data = exchPtr.data; node.left = remove(node.left,exchPtr.data,shorter,success); if (shorter[0]) node = deleteRightBalance(node,shorter); } } return node; } /** * An auxiliary method that right-balances this subtree after a deletion * @param node the node to be right-balanced * @param shorter indicates whether the subtree becomes shorter * @return a reference to the root of the subtree after right-balancing. */ private Node deleteRightBalance(Node node, boolean[] shorter) { Node rightTree; Node leftTree; switch(node.bal) { case LH: //deleted left -- now balanced node.bal = BalancedFactor.EH; break; case EH: /ow right high node.bal = BalancedFactor.RH; shorter[0] = false; break; case RH: // right high -- rotate left rightTree = node.right; if (rightTree.bal == BalancedFactor.LH) { leftTree = rightTree.left; switch(leftTree.bal) { case LH: rightTree.bal = BalancedFactor.RH; node.bal = BalancedFactor.EH; break; case EH: node.bal = BalancedFactor.EH; rightTree.bal = BalancedFactor.EH; break; case RH: node.bal = BalancedFactor.LH; rightTree.bal = BalancedFactor.EH; break; } leftTree.bal = BalancedFactor.EH; //rotate right, then left node.right = rotateRight(rightTree); node = rotateLeft(node); } else { switch(rightTree.bal) { case LH: case RH: node.bal = BalancedFactor.EH; rightTree.bal = BalancedFactor.EH; break; case EH: node.bal = BalancedFactor.RH; rightTree.bal = BalancedFactor.LH; shorter[0] = false; break; } node = rotateLeft(node); } } return node; }

/** * An auxiliary method that left-balances this subtree after a deletion * @param node the node to be left-balanced * @param shorter indicates whether the subtree becomes shorter * @return a reference to the root of the subtree after left-balancing. */ private Node deleteLeftBalance(Node node, boolean[] shorter) { Node rightTree; Node leftTree; switch(node.bal) { case RH: //deleted right -- now balanced node.bal = BalancedFactor.EH; break; case EH: /ow left high node.bal = BalancedFactor.LH; shorter[0] = false; break; case LH: // left high -- rotate right leftTree = node.left; if (leftTree.bal == BalancedFactor.RH) { rightTree = leftTree.right; switch(rightTree.bal) { case RH: leftTree.bal = BalancedFactor.LH; node.bal = BalancedFactor.EH; break; case EH: node.bal = BalancedFactor.EH; leftTree.bal = BalancedFactor.EH; break; case LH: node.bal = BalancedFactor.RH; leftTree.bal = BalancedFactor.EH; break; } rightTree.bal = BalancedFactor.EH; //rotate left, then right node.left = rotateLeft(leftTree); node = rotateRight(node); } else { switch(leftTree.bal) { case RH: case LH: node.bal = BalancedFactor.EH; leftTree.bal = BalancedFactor.EH; break; case EH: node.bal = BalancedFactor.LH; leftTree.bal = BalancedFactor.RH; shorter[0] = false; break; } node = rotateRight(node); } } return node; } /* BEGIN: Augmented Private Auxiliary Methods */ /** * Recursively computes the height of the subtree * rooted at the specified node * @param node the root of a subtree * @return the height of the subtree rooted at the * specified node */ private int height(Node node) { //Implement this method } /** * Recursively computes the diameter of the subtree * rooted at the specified node * @param node the root of a subtree * @return the diameter of the subtree rooted at the * specified node */ private int diameter(Node node) { //Implement this method } /* END: Augmented Private Auxiliary Methods */ }

-------------------------------------------------------

//AVLTreeAPI.java

package twotreesanalyzer; import java.util.function.Function;

/** * Describes operations on an AVLTree * @param the data type * @author * @sinc 99-99-9999 * @see AVLTreeException */ public interface AVLTreeAPI> { /** * Determines whether the tree is empty. * @return true if the tree is empty; otherwise, false */ boolean isEmpty();

/** * Inserts an item into the tree. * @param obj the value to be inserted. */ void insert(E obj);

/** * Determine whether an item is in the tree. * @param item item with a specified search key. * @return true on success; false on failure. */ boolean inTree(E item);

/** * Delete an item from the tree. * @param item item with a specified search key. */ void remove(E item);

/** * returns the item with the given search key. * @param key the key of the item to be retrieved * @return the item with the specified key * @throws AVLTreeException when no such element exists */ E retrieve(E key) throws AVLTreeException;

/** * This function traverses the tree in in-order * and calls the function Visit once for each node. * @param func the function to apply to the data in each node */ void traverse(Function func); /** * Returns the number of items stored in the tree. * @return the size of the tree. */ int size(); }

______________________________________________________________

//AVLTreeException.java

package twotreesanalyzer; /** * Reports an exception in an AVL Tree * @author * @since 99-99-9999 */

public class AVLTreeException extends Exception {

/** * Creates a new instance of AVLTreeException without detail * message. */ public AVLTreeException() { }

/** * Constructs an instance of AVLTreeException with the * specified detail message. * @param msg the detail message. */ public AVLTreeException(String msg) { super(msg); } }

---------------------------------------------------------------------

//BSTree.java

package twotreesanalyzer;

import java.util.ArrayList;

import java.util.function.Function;

/**

* A binary search tree

* Requires JDK 1.8 for Function*

* @author

* @param the tree data type

* @since 99-99-9999

* @see BSTreeAPI, BSTreeException

*/

public class BSTree> implements BSTreeAPI

{

/**

* the root of this tree

*/

private Node root;

/**

* the number of nodes in this tree

*/

private int size;

/**

* A node of a tree stores a data item and references

* to the child nodes to the left and to the right.

*/

private class Node

{

/**

* the data in this node

*/

public E data;

/**

* A reference to the left subtree rooted at this node.

*/

public Node left;

/**

* A reference to the right subtree rooted at this node

*/

public Node right;

}

/**

* Constructs an empty tree

*/

public BSTree()

{

root = null;

size = 0;

}

public boolean isEmpty()

{

return size == 0;

}

public void insert(E item)

{

Node newNode = new Node();

newNode.data = item;

if (size == 0)

{

root = newNode;

size++;

}

else

{

Node tmp = root;

while (true)

{

int d = tmp.data.compareTo(item);

if (d==0)

{ /* Key already exists. (update) */

tmp.data = item;

return;

}

else if (d>0)

{

if (tmp.left == null)

{ /* If the key is less than tmp */

tmp.left = newNode;

size++;

return;

}

else

{ /* continue searching for insertion pt. */

tmp = tmp.left;

}

}

else

{

if (tmp.right == null)

{/* If the key is greater than tmp */

tmp.right = newNode;

size++;

return;

}

else

{ /* continue searching for insertion point*/

tmp = tmp.right;

}

}

}

}

}

public boolean inTree(E item)

{

return search(item) != null;

}

public void remove(E item)

{

Node nodeptr = search(item);

if (nodeptr != null)

{

remove(nodeptr);

size--;

}

}

public void traverse(Function func)

{

traverse(root,func);

}

public E retrieve(E key) throws BSTreeException

{

if (size == 0)

throw new BSTreeException("Non-empty tree expected on retrieve().");

Node nodeptr = search(key);

if (nodeptr == null)

throw new BSTreeException("Existent key expected on retrieve().");

return nodeptr.data;

}

public int size()

{

return size;

}

/*===> BEGIN: Augmented public methods

/**

* Computes the depth of the specified search key in this tree.

* @param item the search key

* @return the depth of the specified search key if it is in the.

* this tree. If it is not, -1-d, where d is the depth at which

* it would have been found it inserted in the current tree.

*/

public int depth(E item)

{

//Implement this method

}

/**

* Give the heigh of this tree.

* @return the height of this tree

*/

public int height()

{

return height(root);

}

/**

* Traverses this tree in level-order and applies

* the specified function to the data in each node.

* @param func the function to apply to the data in each node

*/

public void levelTraverse(Function func)

{

//Implement this method

}

/**

* Gives the diameter of this tree

* @return the diameter of this tree

*/

public int diameter()

{

return diameter(root);

}

/* END: Augmented public methods */

/**

* A recursive auxiliary method for the inorderTraver method that

* @param node a reference to a Node object

* @param func a function that is applied to the data in each

* node as the tree is traversed in order.

*/

private void traverse(Node node, Function func)

{

if (node != null)

{

traverse(node.left,func);

func.apply(node.data);

traverse(node.right,func);

}

}

/**

* An auxiliary method that supports the search method

* @param key a data key

* @return a reference to the Node object whose data has the specified key.

*/

private Node search(E key)

{

Node current = root;

while (current != null)

{

int d = current.data.compareTo(key);

if (d == 0)

return current;

else if (d > 0)

current = current.left;

else

current = current.right;

}

return null;

}

/**

* An auxiliary method that gives a Node reference to the parent node of

* the specified node

* @param node a reference to a Node object

* @return a reference to the parent node of the specified node

*/

private Node findParent(Node node)

{

Node tmp = root;

if (tmp == node)

return null;

while(true)

{

assert tmp.data.compareTo(node.data) != 0;

if (tmp.data.compareTo(node.data)>0)

{

/* this assert is not needed but just

in case there is a bug */

assert tmp.left != null;

if (tmp.left == node)

return tmp;

else

tmp = tmp.left;

}

else

{

assert tmp.right != null;

if (tmp.right == node)

return tmp;

else

tmp = tmp.right;

}

}

}

/**

* An auxiliary method that deletes the specified node from this tree

* @param node the node to be deleted

*/

private void remove(Node node)

{

E theData;

Node parent, replacement;

parent = findParent(node);

if (node.left != null)

{

if (node.right != null)

{

replacement = node.right;

while (replacement.left != null)

replacement = replacement.left;

theData = replacement.data;

remove(replacement);

node.data = theData;

return;

}

else

{

replacement = node.left;

}

}

else

{

if (node.right != null)

replacement = node.right;

else

replacement = null;

}

if (parent==null)

root = replacement;

else if (parent.left == node)

parent.left = replacement;

else

parent.right = replacement;

}

/* BEGIN: Augmented Private Auxiliary Methods */

/**

* An auxiliary method that recursively determines the height

* of a subtree rooted at the specified node.

* @param node a root of a subtree.

*/

private int height(Node node)

{

//Implement this method

}

/**

* Recursively computes the diameter of the subtree

* rooted at the specified node

* @param node the root of a subtree

* @return the diameter of the subtree rooted at the

* specified node

*/

private int diameter(Node node)

{

//Implement this method

}

/* END: Augmented Private Auxiliary Methods */

}

-----------------------------------------------------------------------------------

//BSTreeAPI

package twotreesanalyzer;

import java.util.function.Function; /** * Describes a binary search tree * Requires JDK 1.8 for Function * @author * @since 99-99-9999 * @param the data type * @see BSTreeException */ public interface BSTreeAPI> { /** * Determines whether the tree is empty. * @return true if the tree is empty; otherwise, false */ boolean isEmpty();

/** * Inserts an item into the tree. * @param obj the value to be inserted. */ void insert(E obj);

/** * Determine whether an item is in the tree. * @param item item with a specified search key. * @return true on success; false on failure. */ boolean inTree(E item);

/** * Delete an item from the tree. * @param item item with a specified search key. */ void remove(E item);

/** * returns the item with the given search key. * @param key the key of the item to be retrieved * @return the item with the specified key * @throws BSTreeException when no such element exists */ E retrieve(E key) throws BSTreeException;

/** * This function traverses the tree in in-order * and calls the function Visit once for each node. * @param func the function to apply to the data in each node */ void traverse(Function func); /** * This method returns the number of items stored in the tree. * @return the size of the tree. */ int size(); }

-------------------------------------------------------

//BSTreeException.java

package twotreesanalyzer; /** /** * Reports an exception in a binary search tree * @author * @since 99-99-9999 */ public class BSTreeException extends Exception { /** * Creates a new instance of BSTreeException without detail * message. */ public BSTreeException() { }

/** * Constructs an instance of BSTreeException with the specified * detail message. * @param msg the detail message. */ public BSTreeException(String msg) { super(msg); } }

-------------------------------------------------------------------------

//TwoTreesAnalyzer.java

package twotreesanalyzer;

import java.io.FileReader;

import java.io.IOException;

import java.io.PrintStream;

import java.util.Scanner;

import java.util.function.Function;

/**

* Performs insertions and searches, using the same data set,on a binary search

* tree and an AVL tree to empirically compare the performance of

* these operations on the trees.

* @author YOUR NAME

* @SEE AVLTree, AVLTreeException, BSTree, BSTreeException,

* @since DATE LAST MODIFIED

*/

public class TwoTreesAnalyzer

{

//Define auxiliary/helper method(s) for the main method, if any, here

/**

* @param args the command line arguments

* @throws AVLTreeException

* @throws BSTreeException

* @throws java.io.IOException

*/

public static void main(String[] args) throws AVLTreeException, BSTreeException, IOException

{

//Implement this method

}

}

-----------------------------------------------------------------

words0.txt

indubitably knowable emigratory bolshevistically fellowship alterative degenerateness gloriane consanguine hamiltonian

---------------------------------------------

words1.txt

low swift offer green inconclusive act thaw spoil country carpenter exist recognise coherent close provide future soup dad marked wrench pin luxuriant tub nose switch talk committee wool spy nut foamy coast babies soft kitty calendar reduce thundering driving ordinary rabbits extend bells relax fry shoes basket damaged dress groan laborer dead fasten wheel glue bare delightful bear soggy ground moor blue-eyed caring mute thoughtful curious humor bottle ski rinse uncle trouble heady injure courageous building happen different coil decide remarkable heavenly wrist late dinosaurs bizarre nasty cluttered melodic week bulb guess fallacious include mountain smart offer improve disapprove black fantastic health signal gather cub teeny scandalous island peck thank treat zippy cats exultant succeed polite boiling woozy war superb hat well-off juicy disturbed vivacious

-------------------------------------------

words2.txt

abactinal abbeystead activizing addressograph afar akeley aldus alterative animalizing arboured assyrian aweigh boeotia bolshevistically camillo canc chambertin citation confinedly consanguine crumby cupcake curing deathwatch degenerateness derbent desmidian edwin emigratory ermined exarate fellowship foehn frivoled geckos gloriane gradus granada haggard halloaed hamiltonian imminentness inactively indubitably infatuate knowable lacerated lenca loco luringly mephistopheles mimetic moniz musm nccl neatness nephological nondurable nonentry nonenunciatory nonevangelic nonfamilial nonincarnated nontemporal ostracism outfencing overcondensation pagoda passaree peahen personation poking pseudoregal refrainer reoffer scorch semidiaphanous soundingness stemware strikeover talkfest terribly tortuous transfiguration trueborn unconjecturable undersized unhoofed unisexually unnoting unreconcilableness vasectomising vilified violence viridescence vomitoria wagoner waukesha whetted zephyrinus

Table 1:Binary Search Tree [text filename] Level-order Traversal Word Table 2: AVL Tree [text filename] 1-order Traversal Word Table 1:Binary Search Tree [text filename] Level-order Traversal Word Table 2: AVL Tree [text filename] 1-order Traversal Word