COS226

• Download FuzzyBinaryTreeSolution.java

// 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));
    }
}