COS226

• Download FuzzyBinaryTree.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;

public class FuzzyBinaryTree<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 FuzzyBinaryTree() {
    }

    public int fuzzySearch(int key) {
        // TODO: implement this
    }
    
    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
    }
}