Question: This is to test a balanced tree. I need help testing an unbalanced tree the same way import java.io.File; import java.io.FileNotFoundException; import java.io.PrintWriter; import java.util.*;

This is to test a balanced tree. I need help testing an unbalanced tree the same way

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.*;
public class Test {
public static final String INPUT = System.getProperty("user.dir") + "/input/";
public static final String OUTPUT = System.getProperty("user.dir") + "/output/";
public static void main(String[] args) throws FileNotFoundException {
TreeMap map = new TreeMap();
long startTime;
long totalTime = 0;
for(int i = 1; i <= 77;i++) {
Scanner scnr = new Scanner(new File("c:/Users/tvazq/IdeaProjects/hw2/resources/" + i + ".okpuncs"));
while(scnr.hasNext()) {
String word = scnr.next();
startTime = System.nanoTime();
if(!map.containsKey(word))map.put(word, 0);
map.put(word, 1 + map.get(word));
totalTime += (System.nanoTime() - startTime);

}
}
PrintWriter out = new PrintWriter("c:/Users/tvazq/IdeaProjects/hw2/part2" + "frequencies.txt");

startTime = System.nanoTime();
Set allWords = map.keySet();
totalTime += (System.nanoTime() - startTime);
for(String word: allWords) {
startTime = System.nanoTime();
int frequency = map.get(word);
totalTime += (System.nanoTime() - startTime);
out.printf("%s\t%d\n", word, frequency);
out.flush();
}
out.close();
System.out.printf("%.3f ms", totalTime/1e6);
}
}

UnbalancedTree.java

package part2;
import java.util.ArrayList;
import java.util.List;

class BinaryNode {
E element;
BinaryNode left;
BinaryNode right;

BinaryNode(E element) {
this.element = element;
}
}

class OrderedKeyValue implements Comparable {
String key;
int value;

OrderedKeyValue(String key, int value) {
this.key = key;
this.value = value;
}

@Override
public int compareTo(OrderedKeyValue other) {
return this.key.compareToIgnoreCase(other.key);
}
}

class UnbalancedTreeMap {
BinaryNode root;

public UnbalancedTreeMap() {
root = null;
}

public int get(String key) {
BinaryNode current = root;
while (current != null) {
int comparison = key.compareToIgnoreCase(current.element.key);
if (comparison < 0) {
current = current.left;
} else if (comparison > 0) {
current = current.right;
} else {
return current.element.value;
}
}
return 0;
}

public int put(String key, int value) {
BinaryNode parent = null;
BinaryNode current = root;
int comparison = 0;
while (current != null) {
comparison = key.compareToIgnoreCase(current.element.key);
if (comparison < 0) {
parent = current;
current = current.left;
} else if (comparison > 0) {
parent = current;
current = current.right;
} else {
int oldValue = current.element.value;
current.element.value = value;
return oldValue;
}
}
OrderedKeyValue newElement = new OrderedKeyValue(key, value);
if (parent == null) {
root = new BinaryNode<>(newElement);
} else {
if (comparison < 0) {
parent.left = new BinaryNode<>(newElement);
} else {
parent.right = new BinaryNode<>(newElement);
}
}
return 0;
}

public String[] keySet() {
List keys = new ArrayList<>();
inOrderTraversal(root, keys);
return keys.toArray(new String[0]);
}

private void inOrderTraversal(BinaryNode node, List keys) {
if (node == null) {
return;
}
inOrderTraversal(node.left, keys);
keys.add(node.element.key);
inOrderTraversal(node.right, keys);
}
}

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock

import javaioFile import javaioFileNotFoundException impor... View full answer

blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!