【算法】二叉查找树（BST）实现字典API

int size()                    获取字典中键值对的总数量
void put(int key, int val)    将键值对存入字典中
int get(int key)              获取键key对应的值
void delete(int key)          从字典中删去对应键（以及对应的值）
int min()                     字典中最小的键
int max()                     字典中最大的键
int rank(int key)             key在键中的排名（小于key的键的数量）
int select(int k)             获取排名为k的键

public class BST {
  Node root; // 根结点
  private class Node { // 匿名内部类Node
    int key;  // 存储字典的键
    int val;  // 存储字典的值
    Node left,right; // 分别表示左链接和右链接
    int N; // 以该结点为根的子树中的结点总数
    public Node (int key,int val,int N) {
      this.key = key;
      this.val = val;
      this.N = N;
    }
  }
 
  public  int get (int key) { }
  public void put (int key,int val) {  }
  // 其他方法 ... ...
}

// 针对某个结点设计的递归处理方法
private int get(Node x, int key) {
  // 递归调用get方法
}
// 将root作为上面方法的参数，从根结点开始处理整颗二叉树
public int get(int key) {
  return get(root, key)
}

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

  private int get (Node x,int key) {
    if(x == null) return -1; // 结点为空， 未查找到
    if(key<x.key) {
      return get(x.left,key); // 键在左子树，向左子树查找
    }else if(key>x.key) {
      return get(x.right, key); // 键在右子树，向右子树查找
    }else{
      return x.val; // 查找成功，返回值
    }
  }
 
  public int get (int key) {
    return get(root,key);
  }

  private Node put (Node x, int key, int val) {
    if(x == null) return new Node(key,val,1); // 未查找到key,创建新结点，并插入树中
    if(key<x.key){
      x.left = put(x.left,key,val); // 向左子树插入
    }else if(key>x.key){
      x.right = put(x.right,key,val); // 向右子树插入
    }else {
      x.val = val; // 查找到给定key， 更新对应val 
    }
    x.N =size(x.left) + size(x.right) + 1; // 更新结点计数器
    return x; //
  }
 
  public void put (int key,int val) {
    if(root == null) root = put(root,key,val); // 向空树中插入第一个结点
    put(root,key,val);
  }

x.N =size(x.left) + size(x.right) + 1; // 更新结点计数器

  private Node min (Node x) {
    if(x.left == null) return x; // 如果左儿子为空，则当前结点键为最小值，返回
    return min(x.left);  // 如果左儿子不为空，则继续向左递归
  }
  public int min () {
    if(root == null) return -1;
    return min(root).key;
  }

  public Node deleteMin (Node x) {
    if(x.left==null) return x.right; // 如果当前结点左儿子空，则将右儿子返回给上一层递归的x.left 
    x.left = deleteMin(x.left);// 向左子树递归， 同时重置搜索路径上每个父结点指向左儿子的链接
    x.N = size(x.left) + size(x.right) + 1; // 更新结点计数器N 
    return x; // 当前结点不是min  ###
  }
 
  public void deleteMin () {
     root = deleteMin(root);
  }

  public Node delete (int key,Node x) {
    if(x == null) return null;
    if(key<x.key){
      x.left = delete(key,x.left); // 向左子树查找键为key的结点 #1
    }else if (key>x.key){
      x.right = delete(key,x.right); // 向右子树查找键为key的结点   #2
    }else{ // 在这个else里结点已经被找到，就是当前的x
 
      // 这里处理的是上述的 第一种情况和第二种情况：左子树为null或右子树为null（或都为null）
      if(x.left==null) return x.right; // 如果左子树为空，则将右子树赋给父节点的链接  #3
      if(x.right==null) return x.left; // 如果右子树为空，则将左子树赋给父节点的链接  #4
 
      // 这里处理的是上述的第三种情况
      Node inherit = min(x.right); // 取得结点x的继承结点
      inherit.right = deleteMin(x.right); // 将继承结点从原来位置删除，并重置继承结点右链接
      inherit.left = x.left; // 重置继承结点左链接
      x = inherit; // 将x替换为继承结点
    }
    x.N = size(x.left)+ size(x.right) + 1; // 更新结点计数器
    return x; // #5
  }
 
  public void delete (int key) {
    root = delete(key, root);
  }

  public int rank (Node x,int key) {
    if(x == null) return 0;
    if(key<x.key) {
      return rank(x.left,key);
    }else if(key>x.key) {
      return size(x.left) + 1 + rank(x.right, key);
    }else {
      return size(x.left);
    }
  }
 
  public int rank (int key) {
    return rank(root,key);
  }

  private Node select (Node x,int k) {
    if(x==null) return null;
    int t = size(x.left);
    if(t>k){
      return select(x.left,k);
    }else if(t<k) {
      return select(x.right,k-t-1);
    }else {
      return x;
    }
  }
 
  public int select (int k) {
    return select(root,k).key;
  }