Create a program called AnalyzeText.java that computes and prints some statistics on the words in the file data/donut.txt. Specifically:

1. Print the word that occurs most often in the file
2. Print a count of the words that occur exactly once
3. Compute and print the average length of a word

Use one of the tree implementations for storing words and their counts as they read in from the input text file. Use one of BST or BSTEssential.

Do not use try-catch method, Scanner, BufferedReader, or StringBuilder. Do something like this. No complex code.

StdIn.fromFile("data/donut.txt");

String[] words = StdIn.readAllStrings();

The files:

If you want to see how the BST it is here under section 3.3 .

https://algs4.cs.princeton.edu/code/

BSTEssential looks like this:

package myalgs4;

import java.awt.Font;

import algs4.Queue; import algs4.StdDraw;

/* * This is a simplified version of the BST class * */

public class BSTEssential, Value> {

private Node root; // root of BST private int size;

private static class Node,Value> { public Key key; // sorted by key public Value val; // associated data public Node left, right; // left and right subtrees

public Node(Key key, Value val) { this.key = key; this.val = val; } }

public BSTEssential() { this.root = null; this.size = 0; }

/* ********************************************************************* * Return the number of key-values pairs in the BST. ***********************************************************************/ public int size() { return this.size; } /* ********************************************************************* * Does there exist a key-value pair with given key? ***********************************************************************/ public boolean contains(Key key) { return get(key) != null; }

/* ********************************************************************* * Search BST for given key, and return associated value if found, * return null if not found (recursive version) ***********************************************************************/

public Value get(Key key) { return get(root, key); }

private Value get(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp < 0) return get(x.left, key); else if (cmp > 0) return get(x.right, key); else return x.val; } /* ********************************************************************* * Search BST for given key, and return associated value if found, * return null if not found (iterative version) ***********************************************************************/ /* public Value get(Key key) { Node x = root; while (x != null) { int cmp = key.compareTo(x.key); if (cmp < 0) x = x.left; else if (cmp > 0) x = x.right; else return x.val; } return null; } */ /* ********************************************************************* * Insert key-value pair into BST * If key already exists, update with new value ***********************************************************************/ public void put(Key key, Value val) { if (val == null) { delete(key); return; } root = put(root, key, val); }

private Node put(Node x, Key key, Value val) { if (x == null) { this.size++; return new Node<>(key, val); } int cmp = key.compareTo(x.key); if (cmp < 0) x.left = put(x.left, key, val); else if (cmp > 0) x.right = put(x.right, key, val); else x.val = val; return x; }

/* ********************************************************************* * Delete a key-value pair, given the key. ***********************************************************************/

public void delete(Key key) { root = delete(root, key); }

private Node delete(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp < 0) x.left = delete(x.left, key); else if (cmp > 0) x.right = delete(x.right, key); else { this.size--; // x is the node to be deleted. // The value returned in each of these cases below // becomes the value of the child reference from // the parent of x. Returning a null makes that // reference a null and so cuts x off, causing its // automatic deletion.

// Determine how many children x has. if (x.right == null && x.left == null){ // This is a leaf node. Change its // reference from its parent to null. return null; } else if (x.right == null) { // One child, to the left. Make that // the new child of x's parent. return x.left; } else if (x.left == null) { // One child, to the right. Make that // the new child of x's parent. return x.right; } else { // Node x has two children. // Find the node in x's left subtree with // the maximum key. Node leftTreeMaxNode = findMax(x.left); // Copy the key and value from that maximum // key node to x, thereby overwriting x's // original key and value. x.key = leftTreeMaxNode.key; x.val = leftTreeMaxNode.val; // Delete the node copied from. x.left = delete(x.left, leftTreeMaxNode.key); } } return x; }

private Node findMax(Node x) { Node temp = x; // Follow right children until you get to // a node with no right child. That node // has the maximum key in the tree rooted at x. while (temp.right != null) { temp = temp.right; } return temp; }

public Iterable keys() { Queue q = new Queue<>(); inOrder(root, q); return q; }

// This is an in-order traversal: visit left, visit x, visit right // Pre-order: visit x, visit left, visit right // Post-order: visit left, visit right, visit x private void inOrder(Node x, Queue q) { if (x == null) return; inOrder(x.left, q); q.enqueue(x.key); inOrder(x.right, q); return; } public int countValue(Value value) { return countValue(root, value); } private int countValue(Node x, Value value) { if (x == null) return 0; int count = 0; if (x.val.equals(value)) count++; count += countValue(x.left, value); count += countValue(x.right, value); return count;

}

public int height() { return height(root); }

private int height(Node x) { if (x == null) return -1; return 1+Math.max(height(x.left), height(x.right)); }

/* *************************************************************************** * Visualization *****************************************************************************/

public void drawTree() { if (root != null) { StdDraw.setPenColor (StdDraw.BLACK); StdDraw.setCanvasSize(1500,1000); drawTree(root, .5, 0.95, .35, 0); } } private void drawTree (Node n, double x, double y, double range, int depth) { int CUTOFF = 10; Font font = new Font("Arial", Font.BOLD, 30); StdDraw.setFont(font); StdDraw.text (x, y, n.key.toString()+":"+n.val.toString()); StdDraw.setPenRadius (.007); if (n.left != null && depth != CUTOFF) { StdDraw.line (x-range, y-.08, x-.01, y-.01); drawTree (n.left, x-range, y-.1, range*.5, depth+1); } if (n.right != null && depth != CUTOFF) { StdDraw.line (x+range, y-.08, x+.01, y-.01); drawTree (n.right, x+range, y-.1, range*.5, depth+1); } } }