In this assignment you will implement the second version of your spell checker.
ID: 3572674 • Letter: I
Question
In this assignment you will implement the second version of your spell checker. Using the randomized dictionary (random_dictionary.txt) given, read in the dictionary into an array of 26 Binary Search Trees (BST) , one for each letter of the alphabet. Thus the first BST would contain only those words starting with letter 'a', while the last would contain only those words starting with letter 'z'. Then, when you read in the book (oliver.txt), you examine the first character of each word, and search (this method is already implemented in BinarySearchTee class) the word in one of the BST. For each word read from the book, see if it is in the corresponding BST. If it is not found, then output the word. This word is either mis-spelled, or not in the dictionary. The words in the dictionary and the book should be run through the String Parser you wrote in Assignment 4. It is not necessary to store the book in a BST, only the dictionary should be stored. You are allowed to implement any other methods you see necessary.
DO NOT use Java API containers to create BST. Use the BinaryTree and other support classes we have already implemented in the class.
You should count the number of words found, number of words not found, number of comparisons for words found, and number of comparisons for words not found just as in assignment 4. Maintain counters to do this. At the end of the program, print out the average number of comparisons for the words found and average comparisons for words not found.
import java.io.*;
import java.util.*;
import javafx.scene.Node;
public class BinarySearchTree<E extends Comparable<E>> extends AbstractTree<E> {
static int max_level;
protected TreeNode<E> root;
protected int size = 0;
/** Create a default binary tree */
public BinarySearchTree() { }
/** Create a binary tree from an array of objects */
public BinarySearchTree(E[] objects) {
for (int i = 0; i < objects.length; i++)
insert(objects[i]);
}
/** Returns true if the element is in the tree */
public boolean search(E e) {
TreeNode<E> current = root; // Start from the root
while (current != null) {
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else // element matches current.element
return true; // Element is found
}
return false;
}
/** Insert element o into the binary tree
* Return true if the element is inserted successfully.
* Uses an iterative algorithm
*/
public boolean insert(E e) {
if (root == null)
root = createNewNode(e); // Create a new root
else {
// Locate the parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null)
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
return false; // Duplicate node not inserted
// Create the new node and attach it to the parent node
if (e.compareTo(parent.element) < 0)
parent.left = createNewNode(e);
else
parent.right = createNewNode(e);
}
size++;
return true; // Element inserted
}
protected TreeNode<E> createNewNode(E e) {
return new TreeNode<E>(e);
}
/** Inorder traversal from the root*/
public void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
protected void inorder(TreeNode<E> root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}
/** Postorder traversal from the root */
public void postorder() {
postorder(root);
}
/** Postorder traversal from a subtree */
protected void postorder(TreeNode<E> root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}
/** Preorder traversal from the root */
public void preorder() {
preorder(root);
}
/** Preorder traversal from a subtree */
protected void preorder(TreeNode<E> root) {
if (root == null) return;
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);
}
/** Inner class tree node */
public static class TreeNode<E extends Comparable<E>> {
E element;
TreeNode<E> left;
TreeNode<E> right;
public TreeNode(E e) {
element = e;
}
}
/** Get the number of nodes in the tree */
public int getSize() {
return size;
}
/** Returns the root of the tree */
public TreeNode getRoot() {
return root;
}
/** Returns an ArrayList containing elements in the path from the root leading to the specified element, returns an empty ArrayList if no such element exists. */
public ArrayList<E> path(E e){
java.util.ArrayList<E> list = new java.util.ArrayList<>();
TreeNode<E> current = root; // Start from the root
//implement the code here as in search method.
return list; // Return an array of elements
}
/* Returns the number of leaf nodes in this tree, returns 0 if tree is empty*/
public int getNumberOfLeaves(){
//left for you to implement in Lab 7
int total = 0;
if(leftSubTree(root.element) != null){
total += leftSubTree(root.element).size();
}
if(rightSubTree(root.element) != null){
total += rightSubTree(root.element).size();
}
return total+1;
}
/* Returns an ArrayList containing all elements in preorder of the specified element’s left sub-tree, returns an empty ArrayList if no such element exists. */
public ArrayList<E> leftSubTree(E e){
/*
The leftSubTree method works by first searching if the specified element exists in the tree
Then, it calls "preorderedList with the left branching subtree as the parameter
*/
//left for you to implement in Lab 7
ArrayList<E> elements = new ArrayList();
TreeNode<E> current = root; // Start from the root
while (current != null) {
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else{// runs if the element is found
elements = preorderedList(current.left);//calls the preorderedList
break;
}
}
return elements;
}
//
protected ArrayList<E> preorderedList(TreeNode<E> root){
ArrayList<E> list = new ArrayList<E>();
if(root != null){
if(root.left != null){
for(E e : preorderedList(root.left)){
list.add(e);
}
}
list.add(root.element);
if(root.right != null){
for(E e : preorderedList(root.right)){
list.add(e);
}
}
return list;//returns the completed list
}else{
return null;//return null if the initial parameter was null
}
}
/* Returns an ArrayList containing all elements in preorder of the specified element’s right sub-tree, returns an empty ArrayList if no such element exists. */
public ArrayList<E> rightSubTree(E e){
ArrayList<E> elements = new ArrayList();
TreeNode<E> current = root; // Start from the root
while (current != null) {
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else{// element matches current.element
//Add root element, recurrsively add lefts, recurrsively add rights
elements = preorderedList(current.right);
break;
}
}
return elements;
}
/* Returns the inorder predecessor of the specified element, returns null if tree is empty or element 'e' is not in the tree. */
public E inorderPredecessor(E e){
//left for you to implement in Lab 70
if(leftSubTree(root.element).contains(e)){
ArrayList<E> list = leftSubTree(root.element);
int elementLoc = list.indexOf(e);
int predecessorLoc = elementLoc--;
if(predecessorLoc == -1){
return root.element;
}else{
return list.get(elementLoc);
}
}
if(rightSubTree(root.element).contains(e)){
ArrayList<E> list = rightSubTree(root.element);
int elementLoc = list.indexOf(e);
int predecessorLoc = elementLoc--;
if(predecessorLoc == -1){
return root.element;
}else{
return list.get(elementLoc);
}
}
return null;
}
/** Delete an element from the binary tree.
* Return true if the element is deleted successfully
* Return false if the element is not in the tree */
public boolean delete(E e) {
// Locate the node to be deleted and also locate its parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null) {
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
break; // Element is in the tree pointed by current
}
if (current == null)
return false; // Element is not in the tree
// Case 1: current has no left children
if (current.left == null) {
// Connect the parent with the right child of the current node
if (parent == null) {
root = current.right;
}
else {
if (e.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
}
}
else {
// Case 2 & 3: The current node has a left child
// Locate the rightmost node in the left subtree of
// the current node and also its parent
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // Keep going to the right
}
// Replace the element in current by the element in rightMost
current.element = rightMost.element;
// Eliminate rightmost node
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
// Special case: parentOfRightMost == current
parentOfRightMost.left = rightMost.left;
}
size--;
return true; // Element inserted
}
/** Obtain an iterator. Use inorder. */
public java.util.Iterator iterator() {
return inorderIterator();
}
/** Obtain an inorder iterator */
public java.util.Iterator inorderIterator() {
return new InorderIterator();
}
// Inner class InorderIterator
class InorderIterator implements java.util.Iterator {
// Store the elements in a list
private java.util.ArrayList<E> list = new java.util.ArrayList<E>();
private int current = 0; // Point to the current element in list
public InorderIterator() {
inorder(); // Traverse binary tree and store elements in list
}
/** Inorder traversal from the root*/
private void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
private void inorder(TreeNode<E> root) {
if (root == null)return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
/** Next element for traversing? */
public boolean hasNext() {
if (current < list.size())
return true;
return false;
}
/** Get the current element and move cursor to the next */
public Object next() {
return list.get(current++);
}
/** Remove the current element and refresh the list */
public void remove() {
delete(list.get(current)); // Delete the current element
list.clear(); // Clear the list
inorder(); // Rebuild the list
}
}
/** Remove all elements from the tree */
public void clear() {
root = null;
size = 0;
}
}
Explanation / Answer
import java.io.*;
import java.util.*;
import javafx.scene.Node;
public class BinarySearchTree<E extends Comparable<E>> extends AbstractTree<E> {
static int max_level;
protected TreeNode<E> root;
protected int size = 0;
/** Create a default binary tree */
public BinarySearchTree() { }
/** Create a binary tree from an array of objects */
public BinarySearchTree(E[] objects) {
for (int i = 0; i < objects.length; i++)
insert(objects[i]);
}
/** Returns true if the element is in the tree */
public boolean search(E e) {
TreeNode<E> current = root; // Start from the root
while (current != null) {
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else // element matches current.element
return true; // Element is found
}
return false;
}
/** Insert element o into the binary tree
* Return true if the element is inserted successfully.
* Uses an iterative algorithm
*/
public boolean insert(E e) {
if (root == null)
root = createNewNode(e); // Create a new root
else {
// Locate the parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null)
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
return false; // Duplicate node not inserted
// Create the new node and attach it to the parent node
if (e.compareTo(parent.element) < 0)
parent.left = createNewNode(e);
else
parent.right = createNewNode(e);
}
size++;
return true; // Element inserted
}
protected TreeNode<E> createNewNode(E e) {
return new TreeNode<E>(e);
}
/** Inorder traversal from the root*/
public void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
protected void inorder(TreeNode<E> root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}
/** Postorder traversal from the root */
public void postorder() {
postorder(root);
}
/** Postorder traversal from a subtree */
protected void postorder(TreeNode<E> root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}
/** Preorder traversal from the root */
public void preorder() {
preorder(root);
}
/** Preorder traversal from a subtree */
protected void preorder(TreeNode<E> root) {
if (root == null) return;
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);
}
/** Inner class tree node */
public static class TreeNode<E extends Comparable<E>> {
E element;
TreeNode<E> left;
TreeNode<E> right;
public TreeNode(E e) {
element = e;
}
}
/** Get the number of nodes in the tree */
public int getSize() {
return size;
}
/** Returns the root of the tree */
public TreeNode getRoot() {
return root;
}
/** Returns an ArrayList containing elements in the path from the root leading to the specified element, returns an empty ArrayList if no such element exists. */
public ArrayList<E> path(E e){
java.util.ArrayList<E> list = new java.util.ArrayList<>();
TreeNode<E> current = root; // Start from the root
//implement the code here as in search method.
return list; // Return an array of elements
}
/* Returns the number of leaf nodes in this tree, returns 0 if tree is empty*/
public int getNumberOfLeaves(){
//left for you to implement in Lab 7
int total = 0;
if(leftSubTree(root.element) != null){
total += leftSubTree(root.element).size();
}
if(rightSubTree(root.element) != null){
total += rightSubTree(root.element).size();
}
return total+1;
}
/* Returns an ArrayList containing all elements in preorder of the specified element’s left sub-tree, returns an empty ArrayList if no such element exists. */
public ArrayList<E> leftSubTree(E e){
/*
The leftSubTree method works by first searching if the specified element exists in the tree
Then, it calls "preorderedList with the left branching subtree as the parameter
*/
//left for you to implement in Lab 7
ArrayList<E> elements = new ArrayList();
TreeNode<E> current = root; // Start from the root
while (current != null) {
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element)> 0) {
current = current.right;
}
else{// runs if the element is found
elements = preorderedList(current.left);//calls the preorderedList
break;
}
}
return elements;
}
//
protected ArrayList<E> preorderedList(TreeNode<E> root){
ArrayList<E> list = new ArrayList<E>();
if(root != null){
if(root.left != null){
for(E e : preorderedList(root.left)){
list.add(e);
}
}
list.add(root.element);
if(root.right != null){
for(E e : preorderedList(root.right)){
list.add(e);
}
}
return list;//returns the completed list
}else{
return null;//return null if the initial parameter was null
}
}
/* Returns an ArrayList containing all elements in preorder of the specified element’s right sub-tree, returns an empty ArrayList if no such element exists. */
public ArrayList<E> rightSubTree(E e){
ArrayList<E> elements = new ArrayList();
TreeNode<E> current = root; // Start from the root
while (current != null) {
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element)> 0) {
current = current.right;
}
else{// element matches current.element
//Add root element, recurrsively add lefts, recurrsively add rights
elements = preorderedList(current.right);
break;
}
}
return elements;
}
/* Returns the inorder predecessor of the specified element, returns null if tree is empty or element 'e' is not in the tree. */
public E inorderPredecessor(E e){
//left for you to implement in Lab 70
if(leftSubTree(root.element).contains(e)){
ArrayList<E> list = leftSubTree(root.element);
int elementLoc = list.indexOf(e);
int predecessorLoc = elementLoc--;
if(predecessorLoc == -1){
return root.element;
}else{
return list.get(elementLoc);
}
}
if(rightSubTree(root.element).contains(e)){
ArrayList<E> list = rightSubTree(root.element);
int elementLoc = list.indexOf(e);
int predecessorLoc = elementLoc--;
if(predecessorLoc == -1){
return root.element;
}else{
return list.get(elementLoc);
}
}
return null;
}
/** Delete an element from the binary tree.
* Return true if the element is deleted successfully
* Return false if the element is not in the tree */
public boolean delete(E e) {
// Locate the node to be deleted and also locate its parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null) {
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
break; // Element is in the tree pointed by current
}
if (current == null)
return false; // Element is not in the tree
// Case 1: current has no left children
if (current.left == null) {
// Connect the parent with the right child of the current node
if (parent == null) {
root = current.right;
}
else {
if (e.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
}
}
else {
// Case 2 & 3: The current node has a left child
// Locate the rightmost node in the left subtree of
// the current node and also its parent
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // Keep going to the right
}
// Replace the element in current by the element in rightMost
current.element = rightMost.element;
// Eliminate rightmost node
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
// Special case: parentOfRightMost == current
parentOfRightMost.left = rightMost.left;
}
size--;
return true; // Element inserted
}
/** Obtain an iterator. Use inorder. */
public java.util.Iterator iterator() {
return inorderIterator();
}
/** Obtain an inorder iterator */
public java.util.Iterator inorderIterator() {
return new InorderIterator();
}
// Inner class InorderIterator
class InorderIterator implements java.util.Iterator {
// Store the elements in a list
private java.util.ArrayList<E> list = new java.util.ArrayList<E>();
private int current = 0; // Point to the current element in list
public InorderIterator() {
inorder(); // Traverse binary tree and store elements in list
}
/** Inorder traversal from the root*/
private void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
private void inorder(TreeNode<E> root) {
if (root == null)return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
/** Next element for traversing? */
public boolean hasNext() {
if (current < list.size())
return true;
return false;
}
/** Get the current element and move cursor to the next */
public Object next() {
return list.get(current++);
}
/** Remove the current element and refresh the list */
public void remove() {
delete(list.get(current)); // Delete the current element
list.clear(); // Clear the list
inorder(); // Rebuild the list
}
}
/** Remove all elements from the tree */
public void clear() {
root = null;
size = 0;
}
}