二叉查找树

定义：一个二叉查找树是一棵二叉树，其中每个节点都含有一个Comparable键（以及相关联的值），且每个节点中的键都大于其左子树中的任意节点的键，而小于右子树任意节点的键。
下面是完整的代码：

public class BinarySearchTree<Key extends Comparable<Key>, Value> {
    
    private Node root;

    public BinarySearchTree() {
    }
    
    private class Node {
        private Key key;
        private Value value;
        private Node left;
        private Node right;
        private int size;   //以该节点为根的字树中的节点总数（包括自身）
        
        public Node(Key key, Value value, int size) {
            this.key = key;
            this.value = value;
            this.size = size;
        }
    }
    public void put(Key key, Value value) {
        if (key == null) throw new IllegalArgumentException("called put() with a null key");
        if (value == null) {   //插入一个value为null的值代表要删除他
            delete(key);
            return;
        }
        root = put(root, key, value);
    }

    //递归在左右子树中查找直到找到合适位置插入，注意size值，从上往下递归再从下往上返回时重塑
size值
    private Node put(Node node, Key key, Value value) {
        if (node == null) return new Node(key, value, 1);
        
        int cmp = key.compareTo(node.key);
        if (cmp < 0)        node.left = put(node.left, key, value);
        else if (cmp > 0)   node.right = put(node.right, key, value);
        else                node.value = value;
        
        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }
    
    public Value get(Key key) {
        return get(root, key);
    }
    
    private Value get(Node node, Key key) {
        if (node == null) return null;
        int cmp = key.compareTo(node.key);
        if (cmp < 0)        return get(node.left, key);
        else if (cmp > 0)   return get(node.right, key);
        else                return node.value;
    }

    //删除key键
    public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException("called delete() with a null key");
        root = delete(root, key);
    }
    
    private Node delete(Node node, Key key) {
        if (node == null) return null;    //key不存在
        
        int cmp = key.compareTo(node.key);
        if (cmp < 0) node.left = delete(node.left, key);
        else if (cmp > 0) node.right = delete(node.right, key);
        else {
            if (node.left == null) return node.right;  //左子树为空直接返回右子树
            if (node.right == null) return node.left;
            //左右子树都在的情况下，找到右子树中的最小节点，用它来代替被删除节点
            Node temp = node;
            node = min(node.right);
            node.right = deleteMin(temp.right);
            node.left = temp.left;
        }
        node.size = size(node.left) + size(node.right) + 1;  //一个节点大小=左子树大小+右子树大小+1
        return node;
    }

    //删除最大键
    public void deleteMax() {
        if (isEmpty()) throw new NoSuchElementException("called deleteMax() with empty symbol table");
        root = deleteMax(root);
    }
    
    private Node deleteMax(Node node) {
        if (node.right == null) return node.left;
        node.right = deleteMax(node.right);
        node.size = size(node.right) + size(node.left) + 1;
        return node;
    }

    //删除最小键
    public void deleteMin() {
        if (isEmpty()) throw new NoSuchElementException("called deleteMin() with empty symbol table");
        root = deleteMax(root);
    }
    
    private Node deleteMin(Node node) {
        if (node.left == null) return node.right;
        node.left = deleteMin(node.left);
        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }
    
    public int size() {
        return size(root);
    }
    
    private int size(Node node) {
        if (node == null)   return 0;
        else                return node.size;
    }
    
    private boolean isEmpty() {
        return size() == 0;
    }
    
    public Key min() {
        if (isEmpty()) throw new NoSuchElementException("called min() with empty symbol table");
        return min(root).key;
    }

    private Node min(Node node) {
        if (node.left == null)  return node;
        else                    return min(node.left);
    }
    
    public Key max() {
        if (isEmpty()) throw new NoSuchElementException("called max() with empty symbol table");
        return max(root).key;
    }
    
    private Node max(Node node) {
        if (node.right == null) return node;
        else                    return max(node.right);
    }
    
    /**
     * 二叉树中小于等于key的最大key键
     * @param key
     * @return
     */
    public Key floor(Key key) {
        if (key == null) throw new IllegalArgumentException("called floor() with a null key");
        if (isEmpty()) throw new NoSuchElementException("called floor() with empty symbol table");
        Node result = floor(root, key);
        if (result == null) return null;
        else                return result.key;
    }
    //递归直到找到key返回，若没有相匹配的则返回最后一个比key小的node，即最后一个调用floor（node.right，key）的node。
原因如下：往左递归寻找是因为要找到一个小于key的node，往右找是因为找到了已经找到了一个小于key的node，
要往右找找有没有更接近key的node，所以最后一个调用floor（node.right，key）的node就是我们想要的值
    private Node floor(Node node, Key key) {
        if (node == null) return null;   //表示树中没有与key相等的值
        int cmp = key.compareTo(node.key);
        if (cmp == 0) return node;   //表示找到了与key相等的值
        if (cmp < 0) return floor(node.left, key);
        Node temp = floor(node.right, key);
        if (temp != null) return temp;
        else              return node;
    }
    
    /**
     * 大于等于key的最小key键
     * @param key
     * @return
     */
    public Key ceiling(Key key) {
        if (key == null) throw new IllegalArgumentException("called ceiling() with a null key");
        if (isEmpty()) throw new NoSuchElementException("called ceiling() with empty symbol table");
        Node result = ceiling(root, key);
        if (result == null) return null;
        else return result.key;
    }
    
    private Node ceiling(Node x, Key key) {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if (cmp == 0) return x;
        if (cmp > 0) return ceiling(x.right, key);
        Node temp = ceiling(x.left, key);
        if (temp != null) return temp;
        else return x;
    }
    
    /**
     * 返回的这个键在树中正好有k个小于它的键
     * @param k
     * @return
     */
    public Key select(int k) {
        if (k < 0 || k >= size()) 
            throw new IllegalArgumentException("called select() with wrong number : " + k);
        Node result = select(root, k);
        return result.key;
    }
    
    private Node select(Node x, int k) {
        int size = size(x.left);
        if (k < size) return select(x.left, k);
        else if (k > size) return select(x.right, k-size-1);
        else return x;
    }
    //返回二叉树中小于key的node的个数
    public int rank(Key key) {
        if (key == null) throw new IllegalArgumentException("argument rank() is null");
        return rank(root, key);
    }
    
    private int rank(Node x, Key key) {
        if (x == null) return 0;
        int cmp = key.compareTo(x.key);
        if (cmp < 0) return rank(x.left, key);
        else if (cmp > 0) return 1 + size(x.left) + rank(x.right, key);
        else return size(x.left);
    }

}

二叉查找树平均情况下查找和插入时间复杂需为1.39logn；最坏情况下为n。