二叉搜索树

import java.util.*;

/**
 * 二叉搜索树实现。
 * 动态模拟器地址
 * https://www.cs.usfca.edu/~galles/visualization/BST.html
 * @param <K>
 * @param <V>
 */
public class ExtHashMap<K extends Comparable<K>, V> implements Map<K, V> {

    private transient Node root;

    private transient int size = 0;

    class Node {
        public K key;
        public V value;
        public Node left, right;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public boolean containsKey(Object key) {
        return false;
    }

    @Override
    public boolean containsValue(Object value) {
        return false;
    }

    @Override
    public V get(Object key) {
        Node node = obtain(root, key);
        return node == null ? null : node.value;
    }

    private Node add(Node node, K key, V value) {
        if(node == null) {
            node = new Node(key, value);
            size++;
            return node;
        }
        if(key == node.key) {
            node.value = value;
            return node;
        }
        if(node.key.compareTo(key) > 0) {
            /**
             * 这里有点绕，来做一个简说备注下，举例说明
             *  首先，新增加节点，都是从节点开始起。
             *  比如，根节点A，其左边还没有节点，那么再一次add方法，
             *  也是执行if(node == null)这方法块。
             *  再比如，根节点A，其左边已有节点AL，那么再一次add方法（第一参数当然是传AL节点，因为是在AL节点上添加），
             *  就得重新判断到底是AL的左边还是右边。
             *  再比如，已存在三个节点以上，也是这样判断。
             */
            node.left = add(node.left, key, value);
        } else {
            node.right = add(node.right, key, value);
        }
        return node;
    }

    private Node obtain(Node node, Object key) {
        if(node == null) {
            return null;
        }
        if(node.key == key) {
            return node;
        }
        if(node.key.compareTo((K) key) > 0) {
            return obtain(node.left, key);
        } else {
            return obtain(node.right, key);
        }
    }

    @Override
    public V put(K key, V value) {
        if(root == null) {
            root = new Node(key, value);
            size++;
            return value;
        }
        add(root, key, value);
        return value;
    }

    @Override
    public V remove(Object key) {
        return null;
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> m) {

    }

    @Override
    public void clear() {

    }

    @Override
    public Set<K> keySet() {
        return null;
    }

    @Override
    public Collection<V> values() {
        return null;
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        return null;
    }

    public static void main(String[] args) {
        ExtHashMap<String, String> map = new ExtHashMap<String, String>();
        String value = map.put("10", "10d");
        System.out.println("======value=" + value);
        value = map.put("15", "15d");
        System.out.println("======value=" + value);
        value = map.put("11", "11d");
        System.out.println("======value=" + value);
        value = map.put("9", "9d");
        System.out.println("======value=" + value);
        value = map.get("9");
        System.out.println("======value=" + value);
        System.out.println(map.size());
    }
}