// main code borrowed from algs4 textbook
import java.util.NoSuchElementException;
import java.util.Arrays;
import java.lang.UnsupportedOperationException;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
// binary tree that allows for "fuzzy searches"
public class FuzzyBinaryTreeSolution<Value> {
private Node root; // root of BST
private class Node {
private Integer key; // sorted by key
private Value val; // associated data
private Node left, right; // left and right subtrees
private int size; // number of nodes in subtree
public Node(Integer key, Value val, int size) {
this.key = key;
this.val = val;
this.size = size;
}
}
public FuzzyBinaryTreeSolution() {
}
private static int NOT_FOUND = Integer.MAX_VALUE;
// (private) AUXILIARY recursive method
private int fuzzySearch(Node current, int key) {
// step 1: base case: we've reached leaves
if (current == null) return NOT_FOUND;
// step 2: recursive substeps
int leftCandidate = fuzzySearch(current.left, key);
int rightCandidate = fuzzySearch(current.right, key);
// step 3: combine results
// initially assume that the best key candidate
// is the current one (current.key)
int bestCandidate = current.key;
int distanceBest = Math.abs(key - bestCandidate);
// check if the candidate from the left might be better
if (leftCandidate != NOT_FOUND) {
int distanceLeft = Math.abs(key - leftCandidate);
if (distanceLeft < distanceBest) {
distanceBest = distanceLeft;
bestCandidate = leftCandidate;
}
}
// check if the candidate from the right might be better
if (rightCandidate != NOT_FOUND) {
int distanceRight = Math.abs(key - rightCandidate);
if (distanceRight < distanceBest) {
distanceBest = distanceRight;
bestCandidate = rightCandidate;
}
}
return bestCandidate;
}
public int fuzzySearch(int key) {
// step 0: call auxiliary method with the SAME parameters
// but on the root
return fuzzySearch(root, key);
}
public boolean isEmpty() {
return size() == 0;
}
public int size() {
return size(root);
}
// return number of key-value pairs in BST rooted at x
private int size(Node x) {
if (x == null) return 0;
else return x.size;
}
public boolean contains(Integer key) {
if (key == null) throw new NullPointerException("argument to contains() is null");
return get(key) != null;
}
public Value get(Integer key) {
return get(root, key);
}
private Value get(Node x, Integer 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;
}
public void put(Integer key, Value val) {
if (key == null) throw new NullPointerException("first argument to put() is null");
if (val == null) {
return;
}
root = put(root, key, val);
}
private Node put(Node x, Integer key, Value val) {
if (x == null) return new Node(key, val, 1);
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;
x.size = 1 + size(x.left) + size(x.right);
return x;
}
public static void main(String[] args) {
// TEST
FuzzyBinaryTreeSolution<String> fbt = new FuzzyBinaryTreeSolution<>();
// even though the Fuzzy Binary Tree is a *symbol table*
// where we supposedly associate a key to a value, here
// we just care about the key --- so will always set
// the value to "some value"
fbt.put(1, "some value");
fbt.put(4, "some value");
fbt.put(5, "some value");
StdOut.println("fuzzy search of 3 in {1, 4, 5}: " +
fbt.fuzzySearch(3));
}
}