This is to test a balanced tree. I need help testing an unbalanced tree the same way
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.*;
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
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
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
BinaryNode
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
public UnbalancedTreeMap() {
root = null;
}
public int get(String key) {
BinaryNode
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
BinaryNode
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
inOrderTraversal(root, keys);
return keys.toArray(new String[0]);
}
private void inOrderTraversal(BinaryNode
if (node == null) {
return;
}
inOrderTraversal(node.left, keys);
keys.add(node.element.key);
inOrderTraversal(node.right, keys);
}
}
Microeconomics An Intuitive Approach with Calculus
ISBN: 978-0538453257
1st edition
Authors: Thomas Nechyba