二叉查找树

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

public class BST<Key extends Comparable<Key>, Value>{
    private Node root;        //二叉查找树的根结点
    private class Node{
        private Key key;              //键
        private Value val;            //值
        private Node left, right;    //指向子树的链接
        private int N;               // 以该结点为根结点的子树中的结点总数
        public Node(Key key, Value val, int N){
            this.key = key;  this.val = val; this.N = N;
        }
    }

    public int size(){
        return size(root);
    }
    private int size(Node x){
        if(x == null) return 0;
        else      return x.N;
    }
    public Value get(Key key){
        return get(root, key);
    }
    private Value get(Node x, Key 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(Key, Value val){
        root = put(root, key, val);
    }  
    private Node put(Node x, Key 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.N = size(x.left) + size(x.right) +1;
        return x;
    }
}

我们嵌套了一个私有类来表示二叉树上的一个结点，每个结点都含有一个键，一个值，一个左链接，一个右链接和一个统计结点计数器。算法中的size()方法将空链接的值当做0，从而保证有size(x) = size(x.left) + size(x.right) + 1。
使用二叉查找树的算法的运行时间取决于树的形状。最好的情况下，一棵含有N个结点的树是完全平衡的，每条空链接和根结点的距离均为~lgN。一般情况下，树的情况与此相接近。

在N个随机键构造的二叉查找树中，查找命中平均比较的次数为_{2lgN；查找未命中和插入操作的平均比较次数为}2lgN。

---

二叉查找树中max(), min(), floor(), ceiling()方法的实现:

• 最大键和最小键
  如果根结点的左链接为空，那么一棵二叉查找树的最小的键就是根结点；如果左链接非空，那么树中最小的键就是左子树的最小键。
• 向上取整与向下取整
  如果给定的键key小于二叉查找树的根节点的键，那么小于等于key的最大键floor(key)一定在根结点的左子树；如果给定的键key大于二叉查找树的根结点，那么只有当右子树中存在小于等于key的键，小于等于key的最大键才会在右子树，否则根结点就是小于等于key的最大键。

public Key min(){
    return min(root).key;
}
private Node min(Node x){
    if ( x.left == null) return x;
    return min(x.left);
}
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;
    else if(cmp <0)  return floor(x.left, key);
    Node t = floor(x.right, key);
    if (t != null)  return t;
    else  return x;
}

---

二叉查找树中select()和rank()方法的实现：

• 查找
  假设我们想找到排名为k的键。如果左子树中的结点数t等于k，则返回根结点的键；如果t大于k，则继续在左子树中查找；如果t小于k，则在右子树中查找排名为k-t-1的键。
• 排名
  rank()是select()的逆方法。如果给定的键与根结点的键值相等，则左子树的结点数t；如果小于根结点的键值，则返回该键在左子树中的排名；如果大于根结点的键值，设根结点的键值为t，则返回t+1加上它在右子树中的排名。

public Key select(int k){
    return select(root, k).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 rank(Key key){
    return rank(key, root);
}
private int rank(Key key, Node x){
    if( x == null) return 0;
    int cmp = key.compareTo(x.key);
    if  (cmp < 0)  return rank(key, x.left);
    else if(cmp >0)  return 1+size(x.left)+rank(key, x.right);
    else  return size(x.left);
}

---

二叉查找树中delete()方法的实现：

• 删除最大键和最小键
  对于删除最小键deleteMin(),我们要不断深入根结点的左子树中直到遇见一个空链接，然后将指向该结点的链接指向该结点的右子树。因为没有任何链接指向被删除的结点，所以它会被垃圾处理器清理掉。同时应注意更新它到根结点的路径上所有结点的计数器的值。
• 删除操作
  删除具有一个或没有子结点的结点操作类似于之前，但对于删除具有两个子结点的结点的操作，为了处理删除后多的两棵子树，一种方法是选取右子树的最小结点来填补被删除的结点的位置。简单的步骤是先将指向即将被删除的结点的链接保存为t，将x指向它的后继结点min(t.right)，再将x的右链接指向deleteMin(t.right)，最后将x的左链接设为t.left。

public void deleteMin(){
    root = deleteMin(root);
}
private Node deleteMin(Node x){
    if (x == null)  return x.right;
    x.left = deleteMin(x.left);
    x.N = size(x.left)+size(x.right)+1;
    return x;
}

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{
        Node t = x;
        x = min(t.right);
        x.right = deleteMin(t.right);
        x.left  = t.left;
    }
    x.N = size(x.left) + size(x.right) + 1;
    return x;
}

---

二叉查找树的范围查找操作

• 范围查找
  为了实现返回给定键值范围内的keys()方法，我们首先需要遍历二叉查找树——中序遍历，即先打印出根结点的左子树的所有键，然后打印出根结点的键，最后打印出根结点右子树的所有键。代码如下：
  private void print(Node x){
  if(x == null) return;
  print(x.left);
  StdOut.println(x.key);
  print(x.right);
  }
  为了实现接受两个参数并能够将给定范围的键返回给用例的keys()方法，我们可以将所有落在给定范围内的键加入一个队列Queue并跳过那些不可能含有所查找键的子树。

public Iterable<Key> keys(){
    return keys(min(), max());
}
public Iterable<Key> keys(){
    Queue<Key> queue = new Queue<Key>();
    keys(root, queue, lo, hi);
    return queue;
}
private void keys(Node x, Queue<Key> queue, Key lo, Key hi){
    if( x = null)  return;
    int cmplo = lo.compareTo(x.key);
    int cmphi = hi.compareTo(x.key);
    if( cmplo < 0) keys(x.left, queue, lo, hi);
    if( cmp <=0 && cmphi >= 0) queue.enqueue(x.key);
    if(cmphi > 0) keys(x.right, queue, lo, hi);
}