概念

首先我们要了解二叉树和二叉查找树的概念
二叉树是一个空连接，可以有左右子树，每个链接都能指向自己的子树。

二叉查找树

每个节点的值都大于等于左子树的所有节点，小于等于右子树的所有节点。
BST有个重要性质：中序遍历递增。

方法get

如果树是空的返回空
如果相等，直接返回
小于，递归左子树
大于，递归右子树

方法put

如果root为空，新建一个
如果插入的存在，覆盖
不存在，新建一个，然后递归放到合适的位置。

分析

二叉树算法的运行时间取决于树的高度，最好的情况是一颗完全二叉树O(logN)，最坏的情况是一条线N

方法floor

floor(key)，找到小于这个键的最大键
当小于根节点，那么在左子树
大于根节点，先判断右子树，右子树没有，返回左子树。

import javax.xml.soap.Node;
import java.util.ArrayList;
import java.util.List;

public class BST<Key extends Comparable<Key>,Value> implements OrderedST<Key,Value> {
    protected Node root;
    protected class Node{
        Key key;
        Value val;
        Node left;
        Node right;
        //以该节点为根的子树节点总数
        int N;
        //红黑树中使用
        boolean color;
        Node(Key key,Value val,int N){
            this.key=key;
            this.val=val;
            this.N=N;
        }
    }


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

    private int size(Node root) {
        if(root==null){
            return 0;
        }
        return root.N;
    }

    @Override
    public Value get(Key key) {
       return get(root,key);
    }

    private Value get(Node root, Key key) {
        if(root==null){
            return null;
            }
        int cmp=key.compareTo(root.key);
        if(cmp==0){
            return root.val;
        }else if(cmp>0){
            return get(root.right,key);
        }else{
            return get(root.left,key);
        }
    }
    protected void recalculateSize(Node root){
        root.N=size(root.left)+size(root.right)+1;
    }
    @Override
    public void put(Key key, Value value) {
        root=put(root,key,value);

    }

    private Node put(Node root, Key key, Value value) {
        if(root==null){
            return new Node(key,value,1);
        }
        int cmp=key.compareTo(root.key);
        if(cmp==0){
            root.val=value;
        }else if(cmp<0){
            root.left=put(root.left,key,value);
        }else {
            root.right=put(root.right,key,value);
        }
        recalculateSize(root);
        return root;
    }

    @Override
    public Key min() {
        return min(root).key;
    }

    private Node min(Node x) {
        if (x == null)
            return null;
        if (x.left == null)
            return x;
        return min(x.left);
    }
    public void deleteMin() {
        root = deleteMin(root);
    }

    public Node deleteMin(Node x) {
        if (x.left == null)
            return x.right;
        x.left = deleteMin(x.left);
        recalculateSize(x);
        return x;
    }
    @Override
    public Key max() {
        return null;
    }
    public void delete(Key key) {
        root = delete(root, key);
    }
    private Node delete(Node x, Key key) {
        if (x == null)
            return null;
        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            x.left = delete(x.left, key);
        else if (cmp > 0)
            x.right = delete(x.right, key);
        else {
            if (x.right == null)
                return x.left;
            if (x.left == null)
                return x.right;
            Node t = x;
            x = min(t.right);
            x.right = deleteMin(t.right);
            x.left = t.left;
        }
        recalculateSize(x);
        return x;
    }
    @Override
    public int rank(Key key) {
        return rank(root,key);
    }

    private int rank(Node root, Key key) {
        if(root==null){
            return 0;
        }
        int cmp=key.compareTo(root.key);
        if(cmp==0){
            return size(root.left);
        }
        else if(cmp<0){
            return rank(root.left,key);
        }else{
            return 1+size(root.left)+rank(root.right,key);
        }
    }

    @Override
    public List<Key> keys(Key l, Key h) {
        return keys(root, l, h);
    }

    private List<Key> keys(Node x, Key l, Key h) {
        List<Key> list = new ArrayList<>();
        if (x == null)
            return list;
        int cmpL = l.compareTo(x.key);
        int cmpH = h.compareTo(x.key);
        if (cmpL < 0)
            list.addAll(keys(x.left, l, h));
        if (cmpL <= 0 && cmpH >= 0)
            list.add(x.key);
        if (cmpH > 0)
            list.addAll(keys(x.right, l, h));
        return list;
    }
    public Key floor(Key key){
        Node x=floor(root,key);
        if(x==null){
            return null;
            }
            return x.key;
    }
    private Node floor(Node x,Key key){
        if(x==null){
            return null;
        }
        int cmp=key.compareTo(x.key);
        if(cmp==0){
            return x;
        }
         if(cmp<0){
            return floor(x.left,key);
        }
        Node t= floor(x.right,key);
        return t!=null?t:x;
        }
    }