1 前言

最近在学习《算法4》第三章查找，里面讲述了现代应用常用的一种抽象结构符号表以及符号表的几种实现，本文仅是自己学习的记录，如有不当，欢迎指正。

现代计算机和网络使得我们能够访问海量的信息。高效检索这些信息的能力是处理它们的重要前提。

我们使用符号表这个词来描述一张抽象的表格，我们会将信息(也称之为值)存储在其中，然后按照指定的键来搜索并获取这些信息。键和值的具体意义取决于不同的应用。

符号表有时也被称为字典，例如在英语字典中，键就是单词，值就是单词所对应的定义和注解。

符号表有时又叫做索引，在一本书中，键是术语，而值是对应的页面。

本章说明了基本的API和两种重要实现后，会学习三种经典的数据类型实现高效的符号表：二叉查找树，红黑树和散列表。

2 符号表

符号表最主要的目的就是将一个键和一个值联系起来。并希望能够将一个键值对插入符号表，且插入之后能从符号表的所有键值对中按照键直接找到相对应的值。

定义：符号表是一种存储键值对的数据结构，支持两种操作：插入(put): 将一组新的键值对存入表中；查找(get)：根据指定的键，返回对应的值。

一些典型的符号表应用：

符号表应用	查找的目的	键 Key	值 Val
字典	找出单词的释义	单词	释义
图书索引	找出相关的页码	术语	页码
文件共享	找到歌曲的下载地址	歌曲名	下载地址
账户管理	处理交易	账户号码	交易详情
网络搜索	找出相关的网页	关键词	网页名称
编译器	找出符号的类型和值	变量名	类型和值

2.1 API

符号表是一种典型的抽象数据类型; 代表着一组定义清晰的值以及相应的操作，使得我们能够将类型的实现和使用区分开，通过泛型符号表API，暂时忽略掉键和值的具体类型，先把注意力集中到操作上。

以下是一种简单的泛型符号表API

public class ST<Key,Value>{
    ST()  //创建一张符号表
    
    void put(Key key,Value val) //将键值对插入表中
    Value get(Key key) //获取键key对应的值，不存在则返回null
    void delete(Key key)  //从表中删除对应的键及其对应的值
    boolean contains(Key key) //键key在表中是否有对应的值
    boolean isEmpty()  //表是否为空
    int size()  //表的大小
    Iterable<Key> keys() //表中所有键的集合
}

首先讨论一下API到具体实现中需要注意的几个设计决策

1. 泛型 泛型的使用使得了一次代码，到处使用称为了现实。对于符号表，我们在创建时，通过明确地指定键和值的类型来区分它们的不同角色，比如说键是单词类型，而值是对应单词的注解，那么这个新创建的表自然就是一本字典，而如果指定键是术语，而值是对应的页码，那么该新创建的表则可以充当是一本书的索引。
2. 重复的键：我们遵循以下规则:
   • 每个键只对应着一个值，即表中不允许有重复的键。
   • 当我们插入一个新的键值对时，发现该键已经存在于表中了，我们就用新的值代替旧的值。
3. 空键 我们规定键不能为空，使用空键为空会产生一个运行时异常。
4. 空值 我们还规定不允许有空值。这个规定的直接原因是在我们的API定义中，当键不存在时get()方法会返回null。这个规定给我们带来了两个好处：1是可以通过判断get()方法是否返回空来判断给定的键是否存在于符号表中 2 是当我们删除一个key以及它对应的val时，我们可以通过put(key,null)来实现对key的删除，进而实现延时删除。
5. 删除操作 在符号表中，删除的实现可以有两种方法，延时删除，也就是先将键对应的值置为空，然后再某个时候再删去所有值为空的键。也可以实现为即时删除，也就是立刻从表中删除指定的键。
6. 键的等价性 要确定一个键是否存在于符号表中，我们首先需要建立对象等价性的概念，如何判断传入的key和表中的key是相等的或不等的呢？在JAVA中，按照约定所有的对象都继承了一个equals()方法，可以通过equals方法来判断两个key是否相等。

2.2 有序符号表

上面提到的API是最基本的，无序的符号表实现的一些基本方法。然而在现实生活中的典型的应用程序中，键一般都是可比较的。为了查找的方便，常常会对键进行排序(如英语字典自然是按字母先后顺序的，这样查找起来才方便嘛)，因此抽象到我们的数据结构中，体现为键都是Comparable的对象，因此我们可以通过a.compareTo(b)来比较a和b两个键。

基于此，我们书写一种有序的泛型符号表的API

public class ST<Key extends Comparable<key>, Value>{
    ST()  //创建一张符号表
    
    void put(Key key,Value val) //将键值对插入表中
    Value get(Key key) //获取键key对应的值，不存在则返回null
    void delete(Key key)  //从表中删除对应的键及其对应的值
    boolean contains(Key key) //键key在表中是否有对应的值
    boolean isEmpty()  //表是否为空
    int size()  //表的大小
    Key min()  //最小的键
    Key max()  //最大的键
    Key floor(Key key) //小于等于key的最大键
    Key ceiling(Key key)//大于等于key的最小键
    int rank(Key key)   //小于key的键的数量
    Key select(int k) // 排名为key的键
    void deleteMin()  //删除最小的键
    void deleteMax()  //删除最大的键
    int size(Key lo,Key hi)  //[lo....hi]之间键的数量
    Iterable<Key> keys(Key lo,Key hi) //[lo..hi]之间的所有键，已排序
    Iterable<Key> keys() //表中所有键的集合    
}

重点看排名和选择，检测一个新的键是否插入合适的位置的基本操作是排名(rank，找出小于指定键的键的数量，返回的位置就是指定键插入的位置) 和 选择(select，找出排名为k的键)，并且有对于0到size()-1的所有i都有i == rank(select(i))且有key=select(rank(key))。

同时还实现了范围查找，给定两个键，在这两个键之间有多少键，有哪些键？在很多应用特别大型数据库中，能够处理这类查询是有序符号表在实践中被广泛应用的重要原因之一。

再谈键的等价性：前面提到，键的等价性我们通过equals来进行判断。而JAVA的一条最佳实践就是维护所有Comparable类型中的compareTo()方法和equals()方法的一致性。也就是说，任何一种Comparable类型的两个值a和b都要a.compareTo(b)==0 和a.equals(b)的返回值的相同。为了避免潜在的二义性，我们只会使用compareTo()方法来比较两个键。

2.3 无序链表中的顺序查找

符号表中使用的数据结构的一个简单选择是链表，每个结点存储一个键值对，如下面的代码所示：

get()的实现即是遍历链表，用equals()方法比较待查找的键和每个结点中键，匹配成功我们就返回对应的值，都不能匹配则返回null。

put()的实现同样也是遍历链表，如果匹配成功我们就用第二个参数指定的值更新该键对应的原来的值，否则我们就用给定的键值对创建一个新的结点并插入到链表的开头。这种方法也称之为顺序查找。

基于链表的符号表的索引用例的轨迹如图：

无序链表实现的符号表

package com.Chapter2_Search;

import com.Algorithm.Chapter1.Queue;

//顺序查找，基于无序链表
public class SequentialSearchST <Key,Value>{
    private Node first;

    //The size of List
    private int N;
    private class Node{
        // 链表节点的定义
        Key key;
        Value val;
        Node next;

        //有参构造函数
        public Node(Key key, Value val, Node next) {
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }
    public Value get(Key key){
        for(Node x=first;x!=null;x=x.next){
            if(key.equals(x.key)){
                return x.val; //命中
            }
        }
        return null;  //未命中
    }

    public void put(Key key,Value val){
        for(Node x=first;x!=null;x=x.next){
            if(key.equals(x.key)){
                x.val=val;  //命中，修改原值
                return ;
            }
        }
        first=new Node(key,val,first); //  未命中，新建一个Node， 且该Node成为了新的first
        N++;
    }
    
    public int size(){
        return N;
    }
    
    public boolean contains(Key key){
        for(Node x=first;x!=null;x=x.next){
            if(key.equals(x.key)){
                return true;
            }
        }
        return false;
    }

    public boolean isEmpty(){
        return N==0?true:false;
    }

    public void delete(Key key){
        if(key.equals(first.key)){
            Node tem=first;
            first=first.next;
            tem=null;
            return ;
        }
        for(Node pre=first,x=first.next;x!=null;x=x.next){
            if(key.equals(x.key)){
                pre.next=x.next;
                x=null;
                N--;
                return ;
            }
            pre=pre.next;
        }
    }
    
    public Iterable<Key> keys(){
        Queue<Object> queue=new Queue<>();
        for(Node i=first;i!=null;i=i.next){
            queue.enqueue(i.key);
        }
        return (Iterable<Key>) queue;
    }
}

查找一个已经存在的键并不需要线性级别的时间，一种度量方法是查找表的中每个键，并将总时间除以N。在查找表中的每个键的可能性都相同的情况下时，这个结果就是一次查找平均所需要的比较数,我们称之为随机命中。尽管符号表中用例的查找位置不大可能是随机的，但这个模型也可以适应的很好，我们容易得到随机命中所需的平均比较次数为~N/2。算法中第一个键需要1次比较，第二键需要2次比较，一次类推，平均比较次数为(1+2+3+4+5+6+…+N)/N=(N+1)/2~N/2。

推论：向一个空表中插入N个不同的键需要~$N^2/2$次比较。

分析证明了基于链表的实现的符号表的顺序查找是非常低效的，特别是在巨型表中,N常常非常巨大。

2.4 有序数组的二分查找

下面我们要学习有序符号表API的完整实现。它使用的数据结构是一对平行的数组。一个存储键一个存储值，算法BinarySearchST可以保证数组中Comparable类型的键有序，然后使用数组的索引高效地实现get()和其他操作。

这份代码实现的核心的rank方法，它返回表中小于给定键的键的数量，对应get方法，只要给定的键存在表中，rank方法就能精确地告诉我们在哪里找到它(返回对应的下标)

对于put方法，只要给定的键存在于表中，rank()方法同样能精确地告诉我们到哪里去更新它的值(返回精确的下标)，以及键不存在时应该将键放在何处(就放在返回的下标的位置)，我们将所有更大的键向后移动一格来腾出位置(从后向前移动)并将给定的键值对分别插入到各自数组的合适位置。

基于有序数组的符号表实现的索引用例的轨迹如下图:

基于有序数组实现的符号表

public class BinarySearchST <Key extends Comparable<Key>,Value>{

    private Key[] keys;
    private Value[] vals;
    private int N=0;
    public BinarySearchST(int capacity){
        keys = (Key[]) new Comparable[capacity];
        vals = (Value[]) new Object[capacity];
    }

    public BinarySearchST() {

    }

    public int size(){
        return N;
    }

    public boolean isEmpty(){
        return N==0;
    }

    // 小于 key的键值，等于key在键数组中对应的索引位置
    public int rank(Key key){
        int l=0;
        int h=N-1;
        while(l<=h){
            int mid=l+(h-l)/2;
            int cmp=key.compareTo(keys[mid]);
            if(cmp<0){
                h=mid-1;
            }
            else if(cmp>0){
                l=mid+1;
            }
            else{
                return mid;
            }
        }
        return l;
    }
    public Value get(Key key){
        if(isEmpty()){
            return null;
        }
        int i=rank(key);
        if(i<N && keys[i].compareTo(key)==0 ){
            return vals[i];
        }
        return null;
    }

    public void put(Key key,Value val){
        int i=rank(key);
        if(i<N && keys[i].compareTo(key)==0){
            vals[i]=val;
            return ;
        }
        for(int j=N;j>i;j--){
            keys[j]=keys[j-1];
            vals[j]=vals[j-1];
        }
        keys[i]=key;
        vals[i]=val;
        N++;
        return ;
    }

    public void delete(Key key){
        int i=rank(key);
        if(i<N && key.compareTo(keys[i])==0){
            for(int j=i;j<N-1;j++){
                keys[j]=keys[j+1];
                vals[j]=vals[j+1];
            }
            keys[N]=null;
            vals[N]=null;
            N--;
            return ;
        }
        return ;
    }
    public boolean contains(Key key){
        int i=rank(key);
        if(i<N && key.compareTo(keys[i])==0){
            return true;
        }
        return false;
    }
    public Key min(){
        if(isEmpty()){
            return null;
        }
        return keys[0];
    }
    public Key max(){
        if(isEmpty()){
            return null;
        }
        return keys[N-1];
    }

    //小于等于key的最大值
    public Key floor(Key key){
        int i=rank(key);
        if(i<N && keys[i].compareTo(key)==0){
            return keys[i];
        }
        else{
            return ((i-1)<N)?keys[i-1]:null;
        }
    }

    //大于等于key的最小键值
    public Key ceiling(Key key){
        int i=rank(key);
        return i<N?keys[i]:null; //key比所有值都大时返回null
    }
    //查询索引值为k的键,为rank的逆
    public Key select(int k){
        if(k<0 || k>=N){
            return null;
        }
        return keys[k];
    }
    public void deleteMin(){
        delete(min());
    }
    public void deleteMax(){
        delete(max());
    }
    public int size(Key lo,Key hi){
        if(lo.compareTo(hi)>0){
            return 0;
        }
        int i=rank(lo);
        int j=rank(hi);
        if(j<N && keys[j].compareTo(hi)==0){
            return j-i+1;
        }
        return j-i;
    }
    public Iterable<Key> keys(Key lo,Key hi){
        Queue<Key> q=new Queue<>();
        for(int i=rank(lo);i<rank(hi);++i){
            q.enqueue(keys[i]);
        }
        if(contains(hi)){
            q.enqueue(keys[rank(hi)]);
        }
        return q;
    }
    public Iterable<Key> keys(){
        return keys(min(),max());
    }
}

我们使用有序数组存储键的原因是，我们在查找的时候可以使用二分查找，我们基于二分查找实现了其他方法的基石：rank方法

//rank方法迭代版本
public int rank(Key key){
        int l=0;
        int h=N-1;
        while(l<=h){
            int mid=l+(h-l)/2;
            int cmp=key.compareTo(keys[mid]);
            if(cmp<0){
                h=mid-1;
            }
            else if(cmp>0){
                l=mid+1;
            }
            else{
                return mid;
            }
        }
        return l;
    }

//rank方法递归版本
public int rank(Key key,int lo,int hi){
    if(hi<lo){
        return lo;
    }
    int mid=lo+(hi-lo)/2;
    int cmp=key.compareTo(keys[mid]);
    if(cmp<0){
        return rank(key,lo,mid-1);
    }
    else if（cmp>0){
        return rank(key,mid+1,hi);
    }
    else{
        return mid;
    }
}

在有序数组中使用二分法查找排名的轨迹如下图:

rank方法的递归实现还能够让我们立即得到一个结论：二分查找很快，在N个键的有序数组进行二分查找最多需要(lgN+1)次比较，无论是否成功。

在给出的方法的实现中，ceiling方法调用了一次rank，而接受两次参数的默认size方法调用了两次rank，因此也保证了这次操作所需的时间最多是对数级别的。而min()，max()，和select()操作所需的时间都是常数级别的，这是数组的特性：快速访问。

下图是BinarySearchST的操作的成本:

尽管BinarySearchST能够保证查找所需的时间是对数级别的，但BinarySearch仍然无法支持我们构建大型的符号表去处理大型的问题。因为put方法太慢了。二分查找减少了比较的次数，但它无法改变一下事实：在键是随机排列的情况下，构造一个基于有序数组的符号表所需要访问数组的次数是数组长度的平方级别的。

一般情况下二分查找都比顺序查找快得多，有时候也是实际应用程序的一个好的选择，对于一个静态表(初始化之后不再允许插入了)来说，将其在初始化时就排序，我们在初始化时花费平方级别的时间完成初始化，之后的查找只需花费对数级别的时间，在一些应用中这样的花费是可以接受的。当然，二分查找不适合很多应用，如查找和插入操作是混合进行的。

现代应用需要同时能够支持高效的查找和插入两种操作的符号表实现，也就是说，我们在构造庞大的符号表的同时能够任意的插入，删除，查找键值对。

下表是简单的符号表的成本总结：

核心的问题在于我们能否找到同时保证查找和插入操作都是对数级别的算法和数据结构，答案是可以。

我们如何实现这个目标呢？要支持高效的插入操作，我们似乎需要一种链式结构，而要支持高效的查找操作，我们希望数据结构可以使用二分查找。但单链表是无法使用二分查找的，因为二分查找的高效操作来自于快速通过索引取得任何子数组的中间元素，但得到一条单链表的中间元素的唯一方法只能是沿链表遍历。

为了将二分查找的效率和链表插入的灵活性结合起来，我们需要更复杂的数据结构，能够同时拥有两者的就是二叉查找树。

3 二叉查找树

二叉查找树实现的符号表结合了链表插入的灵活性和有序数组查找的高效性。

我们所使用的数据结构由结点组成，节点包含的链接可以为空null或者指向其他结点。

在二叉树中，每个结点只能有一个父结点，根结点例外，每个结点都有左右两个链接，分别指向自己的左子结点和右子结点。

尽管指向的是下一个结点，我们可以有更大的视野，把每个链接看成指向了另一棵二叉树，而这棵树的根结点就是被指向的那个结点。

在二叉查找树中，每个结点还包含了一个键和一个值，键之间有顺序之分以支持高效的查找。

定义: 一棵二叉查找树(BST)是一棵二叉树，其中每个结点都含有一个Comparable的键(以及对应的值)，且每个结点的键都大于左子树中的任意结点的键而小于右子树中任意的结点

通过二叉树的定义，我们看到，二叉树首先是链式结构的，可以支持高效的插入，同时，每个结点的键都大于左子树中的任意结点的键而小于右子树中任意的结点使得我们可以高效地找出中间值，实现二分查找而进行高效的查找。

3.1 基本实现

我们定义了二叉查找树的数据结构，并用它实现有序符号表的API。

1 数据表示

我们定义了一个结点类。每一个结点都含有一个键，一个值，一条左链接，一条右链接和一个结点计数器。左链接指向一棵由小于该节点的所有键构成的二叉查找树，右链接指向一棵由大于该结点的所有键组成的二叉查找树。

变量N给出了以该结点为根结点的子树的结点总数。

我们在算法中实现了私有方法size(Node x),返回以x为根结点的结点总数，有size(x)=size(x.left)+size(x.right)+1

一棵二叉查找树代表了一组键的集合，而同一个集合可以用多课不同的二叉查找树树表示，如下图所示。

我们将一棵二叉查找树的所有键投影到一条直线上，我们一定可以得到一条有序的键列。

2 查找

首先给出查找算法：

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 x.val;
    }
    else{
        return get(x.right,key);
    }
}

一般来说，在符号表中查找一个键可能的得到的有两种结果: 如果含有该键的结点存在于表中，我们的查找就命中，我们就可以返回相应的值。否则查找未命中，返回null。根据数据表示的递归结构我们马上就能得到在二叉查找树中查找一个键的算法: 如果树是空的，则查找未命中，返回null;如果被查找的键和当前根结点的键相等，查找命中。否则我们就递归地在左或右子树中继续寻找。

在二分查找中每次迭代之后查找的区间就会减少一半，而在我们的二叉查找树中，随着我们不断地向下查找，当前结点所表示的子树的大小也在减少，因为我们每次要么命中，要么根据待查找的键与根结点的键比较大小，从而只选择左子树或只选择右子树进行递归查找。我们理想的情况下是减少一半，但左子树和右子树不一定会相等，但可以肯定的是，查找范围至少会减少一个结点，也就是根结点。

当找到一个含有待查找的键的结点(命中)或者当前子树变为空(未命中)时这个递归过程才会结束。从根结点开始，在每个结点的查找，要么直接返回，要么在他的一个子结点上展开搜索，因此，一次查找也就定义了树的一条路径。对于成功命中的查找，路径在含有被查找的键的结点结束，而对于未命中的查找，路径最终是一个空链接。

二叉查找树中的查找命中和查找未命中情况如下：

3 插入

我们可以看到，二叉查找树的查找代码几乎和二分查找的一样简单，这种简洁性是二叉查找树的重要特性之一。

而二叉查找树的另一个更重要的特性就是插入的实现难度和查找差不多。当查找一个不存在于树中的结点并结束于一条空链接时，我们需要做的就是将链接指向一个含有被查找的键的新结点，进而完成了插入。

public void put(Key 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.val=val;
    }
    else{
        x.right=put(x.right,key,val);
    }
    x.N=size(x.left)+size(x.right)+1;
    return x;
}

put()方法的实现逻辑和二分递归查找的逻辑是相似的，如果树是空的，则返回一个含有该键值对的新结点;如果被查找的键小于根结点的键，我们递归在左子树中插入该键，否则在右子树中插入该键。因此，二叉查找树插入可以接近到查找的效率。

使用二叉查找树插入新建的轨迹：

3.2 分析

使用二叉查找树的算法的运行时间取决于树的形状，而树的形状又取决于键被插入的先后顺序。在最好的情况下，一棵含有N个结点的树是完全平衡的，每条空链接和根结点的距离都为~lgN。而在最坏的情况下，搜索路径上可能有N个结点，也称二叉查找树退化为链表了，但在一般情况下树的形状和最好的情况更接近。

如图3.2.7：

一些命题：

命题C：在由N个随机键构造的二叉查找树中，查找命中平均所需要的比较次数为~2lnN(约为1.39lgN)

命题D：在由N个随机键构造的二叉查找树中，插入和查找未命中平均所需要的比较一次为~2lnN(约为1.39lgN)

命题C说明了在二叉查找树查找随机键的成本比二分查找高39%，而命题D则说明了这些额外的成本是值得的，因为插入一个新键的成本是对数级别的。

3.3 有序性相关的方法与删除操作

二叉查找树得以广泛应用的一个重要原因就是它能够保持键的有序性，因此它可以作为实现有序符号表API中的众多方法的基础。下面，我们研究有序符号表API中各个方法的实现

1. 最大键和最小键

递归实现即可,比较简单

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

 public Key max(){
     if(root==null){
         return null;
     }
     return max(root).key;
 }
 private Node max(Node x){
     if(x.right==null){
         return x;
     }
     return max(x.right);
 }

2 向上取整和向下取整

同样选择递归实现，代码如下

public Key floor(Key key){  //小于等于key的最大键
       Node x=floor(root,key);
       if(x==null){  //找不到小于等于key的最大键，返回null
           return null; 
       }
       else{
           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 floor(x.left,key);
       }
       else if(cmp==0){
           return x;
       }
       else{
           Node t=floor(x.right,key);  //右子树中是否有小于等于key的键
           if(t!=null){  //有的话右子树中小于等于key的最大键就是整棵树中小于等于key的最大键
               return t;
           }
           else{
               return x;  //没有的话根结点的键就是整棵树中小于等于key的最大键
           }
       }
   }

   //大于等于key的最小键盘
   public Key ceiling(Key key){
       Node t=ceiling(root,key);
       if(t!=null){
           return t.key;
       }
       else{
           return null;
       }
   }
   private Node ceiling(Node x,Key key){
       if(x==null){
           return null;
       }
       int cmp=key.compareTo(x.key);
       if(cmp<0){
           Node t=ceiling(x.left,key);
           if(t!=null){
               return t;
           }
           else{
               return x;
           }
       }
       else if(cmp==0){
           return x;
       }
       else{
           return ceiling(x.right,key);
       }
   }

3 选择操作和排名操作

我们在二叉查找树中的每个结点维护着子树结点计数器变量N就是来支持次操作的。

完整实现代码：

public int rank(Key key){
    return rank(root,key);
}
private int rank(Node x,Key key){  //返回以x根节点的子树中小于x.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 size(x.left);
    }
    else{
        return 1+size(x.left)+rank(x.right,key);
    }
}


public Key select(int k){ //返回排名为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 x;
    }
    else{
        return select(x.right,k-t-1);  //之所以要-1，因为根结点也要算进去
    }
}

4 删除最大键和删除最小键

删除最大键和删除最小键并不会破坏掉树的有序性，直接删除即可，不再需要其他的操作保证树的完整性，实现比较简单，代码如下：

public void deleteMin(){ //删除最小值
     if(root==null){
         return ;
     }
     root=deleteMin(root);
 }
 private Node deleteMin(Node x){
     if(x.left==null){
         return x.right;  //根节点无左子女，右子女成为了新的根
     }
     x.left=deleteMin(x.left);
     x.N=size(x.left)+size(x.right)+1;
     return x;
 }

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

5 删除操作

我们可以使用类似删除最大值和最小值的方法删除只有一个结点或者没有子结点的结点，但如何删除一个拥有两个子结点的结点呢？删除之后我们需要处理两棵子树，而被删除的结点的父结点值有一条空出来的链接。

我们采用这样的方法：在删除结点x后用它的后继结点填补它的位置，因为x有一个右子结点，因此它的后继结点就是右子树中的最小结点。这样的替换可以保持树的有序性，我们可以用4个步骤完成将x替换为它的后继结点的任务：

1. 将指向即将被删除的结点的链接保存为t
2. 将x指向它的后继结点min(x.right)
3. 将x的右链接指向 deleteMin(t.right)
4. 将x的左链接设为t.left，也就是被删除结点的左子树。

在递归调用后我们会修正被删除的结点的父结点的链接，并将由此结点到根结点的路径上的所有结点的计数器减去1。

二叉查找树的删除操作如图：

实现代码：

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.left==null){
               return x.right;  //只有单子结点
           }
           if(x.right==null){  //只有单子结点
               return x.left;
           }
           Node t=x;  //t临时存储被删除的结点t
           x=min(t.right);  //找到被删除结点的后续节点,x刚好替换在被删除元素的位置上
           x.right=deleteMin(t.right);
           x.left=t.left;           //这两句最为关键,维持了二叉搜索树的有序性
       }
       x.N=size(x.left)+size(x.right)+1;  //维护N
       return x;
   }

6 范围查找

要实现能够返回给定范围内键的keys()方法，我们可以采用树的中序遍历，先递归打印树的左子树，打印根结点，再打印树的右子树。

我们还要实现一个接受两个参数并能够将给定范围内的键返回给用例的keys()方法，我们可以修改一下这段代码，将所有落在给定范围以内的键加入一个队列Queue并跳过那些不可能含有所查找键的子树。

如下：

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

3.4 性能分析

二叉查找树和有序性相关的操作的效率如何？我们首先需要知道树的高度，给定一棵树，树的高度决定了所有操作在最坏情况下的性能(范围查找出外，因为它的额外成本和返回的键的数量成正比)。

命题E：在一棵二叉查找树中，所有操作在最坏情况下所需的时间都与树的高度成正比。

总的来说，二叉查找树的实现并不困难，且当树的构造和随机模型近似时在各种实际应用场景中它都可以进行快速的查找和插入。同时，它还支持高效的rank()，select()，delete()以及范围查找等操作。但同时，当在某些场景中二叉查找树发生退化，在最坏情况下的恶劣性能是不可接受的。这是我们寻找更好的算法和数据结构的主要原因。

4 平衡查找树

我们在前面学习过的算法已经能够很好地应用于许多应用程序中，但它们在最坏情况下的性能还是很糟糕。

我们希望对二分查找树进行改进，使得在最坏情况下也能保持较高效的性能。

理想情况下我们希望能够保持二分查找树的平衡性。在一棵含有N个结点的树中，我们希望树高为~lgN。

4.1 2-3查找树

为了保证查找树的平衡性，我们需要一些灵活性，因此在这里我们运行树中的一个结点可以保存多个键，确切的说，我们将一棵标准的二叉查找树的结点称为2-结点(含有一个键和两条链接)，而现在我们引入3-结点，它包含了两个键和三条链接。2-结点和3-结点中的每条链接都对应着其中保存的键所分割产生的一个区间。

定义：一棵2-3查找树或成为一棵空树，或由以下结点组成：

• 2-结点：含有一个键(及其对应的值)和两条链接，左链接指向的2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
• 3-结点：含有两个键(及其对应的值)和三条链接，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。

2-3查找树示意图如下：

一棵完美平衡的2-3查找树的所有空链接到根结点的距离都应该是相同的。

1 查找

2-3查找树的查找算法原理是与二叉查找树基本一样的。要判断一个键是否存在树中，先将键与根结点中的键比较，如果相等，则查找命中；否则我们就根据比较结果定位到相应的区间，左链接？中链接？还是右链接？再到子树中继续递归地查找。如果子树为空链接，则查找未命中。

查找过程如图3.3.2所示:

2 向2-结点中插入新键

要在2-3树中插入一个新结点，我们可以和二叉查找树一样先进行一次未命中的查找，然后新结点挂在树的底部，但这样的话树无法保持完美平衡性。我们使用2-3树的主要原因就在于它能够在插入后继续保持平衡。如何未命中的查找结束于一个2-结点，就比较好处理，我们只需要把这个2-结点替换成一个3-结点，将要插入的键保存在其中即可，这样树的高度不会发生变化，自然会继续保持平衡。

向2-结点中插入新的键如图3.3.3所示:

3 向一棵只含有一个3-结点的树中插入新键

只含有一个3-结点的树插入新建，唯一结点中已经没有可以插入新建的空间了。为了将新键插入，我们临时将新键存入该结点，使之称为一个4-结点。它很自然地扩展了以前的结点并含有3个键和4条链接数。

创建一个4-结点很方便，我们也很容易将他转换为一棵由3个2-结点组成的2-3树。这棵树既是一棵含有3个结点的二叉查找树，同时也是一棵完美的二叉平衡树，插入前树的高度为0，插入后树的高度为1。这个例子很简单，但却说明了2-3树是如何生长的？2-3树是向上生长的！

如图3.3.4

4 向一个父结点为2-结点的3-结点中插入新键

假设未命中的查找结束于一个3-结点，而它的父结点是一个2-结点。在这种情况下我们需要在维持树的完美平衡的前提下为新键腾出空间。

我们像先前一样构造一个临时的4-结点，并将其分解，但此时我们不会为中键创建一个新结点，而是将其移动到原来的2-父结点中，使得父结点称为了一个3-结点。

这次转换并不影响2-3查找树的有序性，也不影响树的完美平衡性，插入后所有的空链接到根结点的距离仍然相同。

如图3.3.5

这个转换是2-3树动态变化的核心。

5 向一个父结点为3-结点的3-结点插入新键

再一步，假设未命中的查找结束于一个父结点为3-结点的3-结点，此时父结点已经没有额外的空间了，这时候该怎么办？

我们再次和上面一样构造一个临时的4-结点，然后依旧将它的中键插入到它的父结点中，父结点此时也变成了一个4-结点，我们在父结点做相同的变换，即分解父结点并把父结点的中键插入到父结点的父结点中去，套娃…

一直不断地向上分解，直至遇到一个2-结点并把它替换为一个不需要继续分解的3-结点，或是到达3-结点的根。此时根如果也变成了4-结点，则分解根，实现了2-3树的一次生长。

插入过程如图3.3.6

6 分解根结点

我们上面提到，如果从插入结点到根结点的路径上全是3-结点，我们的根结点最终将会变成一个临时的4-结点

此时我们将临时的根4-结点分解为3个2-结点，使得树高加1，实现了树的生长。这次最后的变换仍然保持了树的完美平衡性，因为变换的是根结点，也说明了2-3查找树是向上生长的。

分解根结点过程如图3.3.7

7 局部变换

将一个4-结点分解为一棵2-3树可能有6种情况，如图3.3.8。

2-3树插入算法的根本在于这些变换都是局部的。2-3树插入算法的根本在于这些变换都是局部的。除了相关的结点和链接之外不必修改或者是检查树的其他部分。每次更换中，变更的链接数量不会超过一个很小的常数，这大大降低的代码的复杂性。需要指出的是，不光是在树的底部，树中的任何地方只要符合相应的模式，变换都是可以进行的。每个变换都会将4-结点中的一个键送入它的父结点中，并重构相应的链接而不必涉及树的其他部分。

8 全局性质

这些局部变换不会影响到树的全局有序性和平衡性；任意空链接到根结点的路径长度都是相等的。

和标准的二叉树由上向下生长不同，我们反复提到2-3树的生长的由下往上的。在二叉查找树中，按照升序插入10个键会得到高度为9的一棵最差查找树(退化为链表了)，而使用了2-3查找树，树的高度是2。

2-3查找树似乎满足了我们的需求，在最坏的情况下，也能有对数级别的效率。

命题F：在一棵大小为N的2-3查找树中，查找和插入操作访问结点必然不超过lgN个。因为2-3查找树是完全平衡树。

如图3.3.10是 一棵 2-3查找树的构造轨迹：

因此我们可以确定2-3树在最坏情况下仍有较好的性能。每个操作中处理每个结点的时间都不会超过一个很小的常数，且这两个操作都只会访问一条路径上的结点，所以任何查找或者插入的成本都肯定不会超过对数级别。

可以看到，完美平衡的2-3树要比二叉查找树平展得多(高度更低)。例如，在含有10亿个结点的一棵2-3树的高度仅仅在19到30之间，完美只需要访问30个结点就能够在10亿个键中进行任意的插入和查找，这是相当惊人的。

如图是一棵由随机键构造的一棵典型的2-3树

但是，我们和真正的实现还有一段距离。我们希望找到一种简洁的2-3树实现的数据结构，只需要一点点代价就能用一种统一的方式完成从二叉查找树到2-3查找树的所有变换，这种数据结构是红黑二叉查找树。

5 红黑二叉查找树

上文所述的2-3树的插入算法并不难理解，现在我们会看到它的实现也不难，我们学习一种名为红黑二叉查找树的简单数据结构来表达并实现它。

5.1 替换3-结点

红黑二叉树背后的基本思想是用标准的二叉查找树(完全由2-结点构成)和一些额外的信息(表示3-结点)来表示2-3树。

我们将树中的链接分为两种类型：红链接将两个2-结点连接起来构成了一个3-结点。黑链接则是2-3树中的普通链接。

确切地说，我们将3-结点表示为由一条左斜的红色链接相连的两个2-结点，如图3.3.12所示。这种表示法的一个优点是，我们无需修改就可以直接使用标准二叉树的get()方法。对于任意2-3树，只要对结点进行转换，我们都可以立刻派生出一棵对应的二叉查找树。我们用这种方式表述2-3树的二叉查找树称为红黑二叉查找树，以下简称为红黑树。红黑树既是二叉查找树，又是2-3树。

5.2 一种等价的定义

红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树：

• 红链接均为左链接 (红链接其实也可以为右链接，只是为了代码的简洁性，我们强制规定红链接均为左链接)

• 没有任何一个结点同时和两条红链接相连。(否则就出现了4-结点了，在红黑树中会出现这样的结点，但我们马上会进行选择等处理保证没有任何一个结点同时和两条红链接相连)

• 该树是完美黑色平衡的，即任意空链接到根结点上的路径上的黑链接数量相同。

5.3 一一对应

完美将一棵红黑树中的红链表画平，那么将可以看到所以的空链接到根结点的距离都将是相同的，如图3.3.13。

如果我们将红链接相连的结点合并，得到的就是一棵2-3树。相反，如果将一棵2-3树中的3-结点画作由红色链接相连的两个2-结点，那么不会存在能够和两条红链接相连的结点，且树必然是完美黑色平衡的。

无论我们选择用何种方法去定义它们，红黑树既是二叉查找树，也是2-3树。如图3.3.14所示：因此，如果我们能够在保持一一对应关系实现2-3树的插入算法，那么我们就能够将两个算法的优点结合起来：二叉查找树简介高效的查找算法和2-3树中高效的平衡插入算法。

5.4 颜色表示

每个结点都只会有一条指向自己的链接，我们将链接的颜色保存在表示结点的Node数据类型的布尔变量color中。如果指向它的链接是红色的，那么该变量为true，黑色则是false。我们约定空链接为黑色。为了代码的清晰我们定义了两个常量RED和BLACK来设置和测试这个变量。

我们使用isRed()来测试一个结点和它的父结点之间的链表的颜色，当我们提到一个结点的颜色时，我们指的是指向该结点的链接的颜色，反之亦然。

颜色表示的代码如下：

private static final boolean RED = true;
private static final boolean BLACK=false;

private class Node{
    Key key;
    Value val;
    Node left,right;
    int N;
    boolean color;

    public Node(Key key, Value val, int n, boolean color) {
        this.key = key;
        this.val = val;
        N = n;
        this.color = color;
    }
}
private boolean isRed(Node x){
    if(x==null){
        return false;
    }
    return x.color==RED;
}

5.5 旋转

我们规定红黑树需要满足条件：

• 红链接均为左链接 (红链接其实也可以为右链接，只是为了代码的简洁性，我们强制规定红链接均为左链接)

• 没有任何一个结点同时和两条红链接相连。(否则就出现了4-结点了，在红黑树中会出现这样的结点，但我们马上会进行选择等处理保证没有任何一个结点同时和两条红链接相连)

• 该树是完美黑色平衡的，即任意空链接到根结点上的路径上的黑链接数量相同。

而在我们实现的某些操作中可能会出现违反上述条件的情况，比如出现了红色右链接或者两条连续的红链接，但在操作完成前这些都会被小心的旋转并修复。

旋转操作会改变红链接的指向，首先，假设我们有一条红色的右链接需要被转为左链接，如图3.3.16。这个操作叫做左旋转。ratateLeft方法接受一条指向红黑树的某个结点的链接作为参数，假设被指向的结点的右链接是红色的，这个方法会对树进行必要的调整并返回一个指向包含同一组键的子树且左链接为红色的根结点的链接。

简单的理解是：用两个键中的较小者作为根结点改变为将较大者作为根结点。

实现一个红色左链接转换为一个红色右链接的一个右旋转的代码完全相同，只需要将left和right互换即可。

旋转操作的代码如下：

//左旋转
public Node rotateLeft(Node h){
    Node x=h.right;
    h.right=x.left;
    x.left=h;
    x.color=h.color;
    x.N=h.N;
    h.color=RED;
    h.N=size(h.left)+size(h.right)+1;
    return x;
}

//右旋转
public Node rotateRight(Node h){
    Node x=h.left;
    h.left=x.right;
    x.right=h;
    x.color=h.color;
    x.N=h.N;
    h.N=size(h.left)+size(h.right)+1;
    return x;
}

5.6 在旋转后重置父结点的链接

无论是左旋转还是右旋转，旋转操作都会返回一条链接。我们总是会用rotateRight()或rotateLeft()的返回值重置父结点中相应的链接,这个链接可能是红色也可能是黑色的，这就可能会产生两条连续的红链接，但我们的算法会继续使用旋转(右旋)操作修正这种情况。

在插入新的键时我们可以通过使用旋转操作来保证2-3树和红黑树的一一对应关系，因为旋转操作可以保持红黑树的两个重要性质：有序性和完美平衡性。也就是说，我们在红黑树中进行选择时无需为树的有序性或者完美平衡性担心，下面我们来看看如何使用旋转操作来保持红黑树和2-3树的一一对应关系。

5.7 向单个2-结点中插入新键

向单个2-结点中插入新键对应于在2-3查找树中向2-结点中插入新键，只需要将新键和父结点合并为一个3-结点即可。对应到红黑树中的操作，就是将新键与对于父结点用红链接连接，但考虑到我们规定红黑树中只能有红色左链接，所以当出现红色右链接时我们要进行一次左旋转操作。如图3.3.18所示：

5.8 向树底部的2-结点插入新键

向树底部的2-结点插入新键，当我们找到插入位置后，总是将新结点用红链接与它的父结点相连。之所以要这么做的原因是：注意红黑树是2-3树的一种实现数据结构，而2-3树是向上生长的树，我们用红链接连接新的结点和父结点，就是为了保持平衡，保证树向上生长的特性。

此时，因为它的父结点是2-结点，所以跟上述想单个2-结点中插入新键操仍然相同，依旧是直接插入，或插入完左旋转一次。如图3.3.19所示:

5.9 向一棵双键树(即单个3-结点)中插入新键

该操作对应于2-3查找树中向一棵只含有3-结点的树中插入新键。这种情况又分为了三种情况：新键小于树中的两个键，在两者之间，大于树中的两个键，无论是哪种情况，都会产生一个同时连接到两条红链接的结点，我们的目标就是修正这一点：

• 新键大于原树中的两个键，此时新键被连接到3-结点的右链接。此时树是平衡的，根结点为中间大小的键，它有两条红色的链接分别和左右子女连接。此时我们考虑将两条链接的颜色都由红变黑，那么我们就得到了一棵由三个结点组成的平衡树，它正好能够对应一棵2-3树。此时需要注意，在将两条自连接的颜色都由红变黑的同时，指向中间键的链接要变为红色，因为要保持树是向上生长的特性。与我们在2-3查找树中，将中间键要插入到父结点中去是保持一致的。 如图3.3.20(左) 其他两种情况最终也会转为这种情况。

• 新键小于原树的两个键，它会被链接到最左边的空链接，这样就会产生连续两条的红链接,如图3.3.20(中)，此时我们只需要将上层的红链接右旋转一次即得到了第一种情况，然后使用相同的办法处理即可。

• 新键介于原树的两个键之间，这时又会产生两条连续的红链接，一条左链接，一条右链接，如图3.3.20(右)。此时我们只需要将下层的红链接左旋转得到第二种情况，然后按相同的办法处理。

总的来说，我们通过0次，1次和2次选择以及颜色的变化得到了期望的结构。

图3.3.20如下：

5.10 颜色转换

如图3.3.32所示，我们专门使用一个方法flipColors()来转换一个结点的两个红色子结点的颜色，同时还要将父结点的颜色由黑变红，目的是为了维持红黑树的平衡树，保证树是向上生长的。

flipColors(Node h)方法实现

private void filpColor(Node h){
    h.color=RED;  //h结点要被位红结点，否则树的高度会增加，破坏了完全二叉树的平衡性
    h.left.color=BLACK;
    h.right.color=BLACK;
}

5.11 根结点总是黑色的

在5.9中，我们所述，颜色转变会使得根结点变为红色，我们需要将根结点由红变黑，此时也即将一个4-结点变为3个2-结点,树的高度加+1，这就是红黑树生长的过程。

每当根结点由红变黑时树的黑链接高度就会+1

5.12 向树底部的3-结点插入新键

现在我们假设需要在树的底部的一个3-结点下插入一个新的结点，同样对应于2-3树中的操作。此时，前面出现的三种情况也都会出现，如果3.3.22所示。

指向新结点的链接有可能是3-结点的右链接，此时只需要转换颜色即可。

指向新结点的链接有可能是3-结点的左链接，此时需要先右旋转再转换颜色即可。

指向新结点的链接有可能是3-结点的中链接，此时需要先左旋转下层链接，然后右旋转上层链接，再转换颜色即可。

注意：颜色转换会使得指向中结点的链接变红，也就是相当于把它送入了父结点，这意味着在父结点中插入了一个新键，我们继续用递归的方式解决父结点中的问题。

5.13 将红链接在树中向上传递

2-3树中的插入算法需要我们分解3-结点，将中间键插入到父结点，一直这样操作知道遇到一个2-结点或者是根结点，我们所考虑过的所有情况都正式为了达成这个目标：每次必要的旋转之后我们都会进行颜色转换，这使得中结点变红，相当于插入了父结点中。而父结点就相当于插入了一个新的键，继续把红链接传递到父结点的中结点上去，直到遇到一个2-结点或者是根结点。

图3.3.23总结了三种情况，显示了在红黑树实现2-3树的插入算法的关键步骤：在一个3-结点下插入新键，先创建一个临时的4-结点，将其分解并将红链接又中结点传递给它的父结点，重复这个过程， 直到遇到一个2-结点或者是根结点。

总之：只要谨慎地使用左旋转，右旋转，颜色转换这三种简单的操作，就能保证插入操作后红黑树和2-3树的一一对应关系。对于经过的每个结点顺序地完成以下操作：注意这里是有顺序的，因为我们知道，三种情况最后都需要转化为颜色转换。

• 如果右子结点是红色的，而左子节点是黑色的，进行左旋转
• 如果左子结点是红色的且左子节点的左子节点也是红色，进行右旋转
• 如果左子节点和右子节点都是红色的，则进行颜色转换

红黑树的插入算法实现如下：

public Node put(Node h,Key key,Value val){
    if(h==null){
        return new Node(key,val,1,RED);
    }
    int cmp=key.compareTo(h.key);
    if(cmp<0){
        h.left=put(h.left,key,val);
    }
    else if(cmp>0){
        h.right=put(h.right,key,val);
    }
    else{
        h.val=val;
    }
    if(isRed(h.right) && !isRed(h.left)){
        h=rotateLeft(h);
    }
    if(isRed(h.left) && isRed(h.left.left)){
        h=rotateRight(h);
    }
    if(isRed(h.left) && isRed(h.right)){
        filpColor(h);
    }
    h.N=size(h.left)+size(h.right)+1;
    return h;
}

一棵红黑树的构造轨迹，如图3.3.24

红黑树的完整实现代码 （除去删除操作)，除了插入操作，其他操作基本都与二叉查找树相同。

public class RedBlackBST<Key extends Comparable<Key>,Value>{

    private Node root;
    private static final boolean RED = true;
    private static final boolean BLACK=false;

    private class Node{
        Key key;
        Value val;
        Node left,right;
        int N;
        boolean color;

        public Node(Key key, Value val, int n, boolean color) {
            this.key = key;
            this.val = val;
            N = n;
            this.color = color;
        }
    }
    private boolean isRed(Node x){
        if(x==null){
            return false;
        }
        return x.color==RED;
    }

    //左旋转
    public Node rotateLeft(Node h){
        Node x=h.right;
        h.right=x.left;
        x.left=h;
        x.color=h.color;
        x.N=h.N;
        h.color=RED;
        h.N=size(h.left)+size(h.right)+1;
        return x;
    }

    //右旋转
    public Node rotateRight(Node h){
        Node x=h.left;
        h.left=x.right;
        x.right=h;
        x.color=h.color;
        x.N=h.N;
        h.N=size(h.left)+size(h.right)+1;
        return x;
    }

    private void filpColor(Node h){
        h.color=RED;  //h结点要被位红结点，否则树的高度会增加，破坏了完全二叉树的平衡性
        h.left.color=BLACK;
        h.right.color=BLACK;
    }

    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 x.val;
        }
        else{
            return get(x.right,key);
        }
    }

    public void put(Key key,Value val){
        root=put(root,key,val);
        root.color=BLACK;
    }
    public Node put(Node h,Key key,Value val){
        if(h==null){
            return new Node(key,val,1,RED);
        }
        int cmp=key.compareTo(h.key);
        if(cmp<0){
            h.left=put(h.left,key,val);
        }
        else if(cmp>0){
            h.right=put(h.right,key,val);
        }
        else{
            h.val=val;
        }
        if(isRed(h.right) && !isRed(h.left)){
            h=rotateLeft(h);
        }
        if(isRed(h.left) && isRed(h.left.left)){
            h=rotateRight(h);
        }
        if(isRed(h.left) && isRed(h.right)){
            filpColor(h);
        }
        h.N=size(h.left)+size(h.right)+1;
        return h;
    }

    public boolean contains(Key key){
        Node x=root;
        while(x!=null){
            int cmp=key.compareTo(x.key);
            if(cmp<0){
                x=x.left;
            }
            else if(cmp>0){
                x=x.right;
            }
            else{
                return true;
            }
        }
        return false;
    }

    public boolean isEmpty(){
        return root==null;
    }

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

    public Key max(){
        if(root==null){
            return null;
        }
        return max(root).key;
    }
    private Node max(Node x){
        if(x.right==null){
            return x;
        }
        return max(x.right);
    }

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

    //大于等于key的最小键盘
    public Key ceiling(Key key){
        Node t=ceiling(root,key);
        if(t!=null){
            return t.key;
        }
        else{
            return null;
        }
    }
    private Node ceiling(Node x, Key key){
        if(x==null){
            return null;
        }
        int cmp=key.compareTo(x.key);
        if(cmp<0){
            Node t=ceiling(x.left,key);
            if(t!=null){
                return t;
            }
            else{
                return x;
            }
        }
        else if(cmp==0){
            return x;
        }
        else{
            return ceiling(x.right,key);
        }
    }

    public int rank(Key key){
        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 size(x.left);
        }
        else{
            return 1+size(x.left)+rank(x.right,key);
        }
    }

    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 x;
        }
        else{
            return select(x.right,k-t-1);
        }
    }


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

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

    public int size(Key lo,Key hi){
        int i=rank(lo);
        int j=rank(hi);
        if(contains(hi)){
            return j-i+1;
        }
        else{
            return j-i;
        }

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

5.14 删除操作

还没看懂，g。

5.15 红黑树的性质

结论：所有基于红黑树的符号表实现都能保证操作的运行时间为对数级别。

首先，无论键的插入顺序如何,红黑树都几乎是完美平衡的。

命题G：一棵大小为N的红黑树的高度不会超过2lgN。

命题H：一棵大小为N的红黑树中，根结点到任意结点的平均长度为~1.00lgN

红黑树的get()方法并不会检查结点的颜色，因此任何平衡性的操作不会产生任何负担，且因为树是平衡的，所以查找比二叉查找树快。每个键只会被插入一次，但可能被查找无数次，只用了最小的代价就取得了和最优情况的查找时间。

这是我们见到的第一个能够保证对数级别的查找和插入操作的实现。

命题 I 在一棵红黑树中，下面操作在最坏情况下所需的时间仍是对数级别的：get，put，min，max，floor，ceiling，rank，select deleteMin deleteMax delete 和 range(范围查找)

至此：各种符号表实现的性能总结如表：表3.3.2

6 散列表

如果我们的键值对所有的键都是小整数，我们可以用一个数组来实现无序的符号表，将键作为数组的索引而数组键i处储存的就是它对应的值。这样我们就可以快速访问任意键的值。

在本节中我们将要学习散列表。它是上述简易方法的扩展并能够处理更加复杂的类型的键。我们需要用算术操作将键转化为数组的索引来访问数组中的键值对。

使用散列的查找算法分为两步：

第一步是用散列函数将被查找的键转化为数组的一个索引。理想情况下，不同的键都能转化为不同的索引值。然而这仅仅是理想情况，我们知道，在现实应用中的键有时是很大的，我们不可能提供一个巨大的数组，让每个键都有一个"唯一的家"。我们提供的数组常常是元小于实际可能的键值的个数的，这种多到少的映射必然会出现两个或者多个键会散列到相同的索引值的情况。

因此第二步就是一个处理碰撞冲突的过程，如图3.4.1所示。

在描述了多种散列函数的计算后，我们会学习两种解决碰撞的方法：拉链法和线性探测法。

散列表是算法在时间和空间上作出权衡的经典例子。如果没有空间内存的限制，我们可以用一个超大的数组，让每个键都映射到不同的索引位置，那么所有的操作只需要访问内存一次即可完成。不会出现碰撞的情况。但这种理想情况不会经常出现，因为当键很多时需要的内存太大了。另一方面，如果没有时间的限制，我们可以用无序数组并进行顺序查找，这样就需要很少的内存。而散列表则是在时间和空间这两个极端找到了一种平衡。

使用散列表，可以实现在一般应用中拥有均摊后常数级别的查找和插入的符号表，这使得它在很多情况下成为实现符号表的最佳选择。

6.1 散列函数

我们面对的第一个问题就是散列函数的计算，这个过程将键转化为数组的索引。如果我们有一个能够保存M个键值对的数组，那么我们就需要一个能够将任意键转化为该数组范围内的索引(0~M-1范围内的整数)的散列函数。

我们要找的散列函数应该易于计算且能够均匀分布所有的键，即对于任意键，0~M-1之间的每个整数都有相等的可能性与之对应。要理解散列，首先就要思考如何去实现这样一个函数。

散列函数和键的类型相关，严格来说，对于每种类型的键我们都需要一个与之对应的散列函数。如果键是一个数，我们就可以直接用这个数;如果键是一个字符串，比如一个人的名字，我们需要将这个字符串转化为一个数;对于许多常见类型的键，我们可以利用Java提供的默认实现。

1 正整数

将整数散列最常用的方法是除留余数法，我们选择了大小为素数M的数组，对于任意正整数k，计算k除以M的余数k%M，这个散列函数能有效地将键散布在0~M-1范围内。之所以要选择一个素数M，是因为如果M不是素数，我们可能无法利用键中所包含的所有信息，这可能导致我们无法均匀地散列散列值。例如，如果键是十进制数而M是$10^k$，我们只能用到键的后k位，这可能会产生一些问题，如加大了碰撞的可能性。举个例子，如果M=100，那么1012和1223212和2345612和12都会散列到索引为12的位置，无论键是什么样子的，只要低2位是12，它对应的索引就是12，这可能会增大了碰撞的可能性。

2 浮点数

如果键是0~1之间的实数，我们可以将它乘以M并四舍五入得到一个0至M-1之间的索引值。这个方法很容易理解，但它是有缺陷的，因为这种情况下键的高位起的作用更大，最低位对散列的结果没有影响。修正这个问题的办法是将键表示为二进制数然后再使用除留余数法。

3 字符串

字符串也可以使用除留余数法进行处理，如下面的代码就能够用除留余数法计算String s的散列值。

int hash=0;
for(int i=0;i<s.length();++i){
    hash=(R*hash+s.charAt(i))%M;
}

Java的cahrAt函数返回一个char值，也就是一个非负16位整数。如果R比任何字符的值都大，这种计算就相当于将字符串当做一个N位的R进制值，并将它除以M并取余。

4 组合键

如果键的类型有多个整型变量，我们可以和String类型一样把它们混合起来，例如被查找的键的类型是Date，我们可以将它拆成几个独立的域:day,month和year，然后通过计算散列值，保证计算结果都在0~M-1范围内即可。

5 JAVA的规定

每种数据类型都需要相应的散列函数。于是JAVA令所有数据类型都继承了一个能够返回一个32比特整数的hashCode()方法。每一种数据类型的hashCode()方法都必须和equals()方法一致。也就是说：如果a.equals(b)返回true，那么a.hashCode()的返回值必然和b.hashCode()的返回值相同，反之如果两个对象的hashCode()的方法的返回值不同，则这两个对象一定是不同的。但hashCode()相同两个对象也不一定相同，因为我们知道有碰撞的出现。

注意需要同时重写hashCode和equals两个方法，而不能之重写一个。

6 将hashCode()的返回值转化为一个数组索引

因为我们需要的是数组的索引而不是一个32位的整数，我们在实现中会将默认的hashCode()方法和除留余数法结合起来产生一个0~M-1的整数，方法如下:

private int hash(Key x){
    return (x.hashCode() & 0x7fffffff)%M;
}

x.hashCode() & 0x7fffffff保证了结果为正数，%M得到对应的数组索引，在使用者的代码时我们一般会将数组大小M取为素数以充分利用原散列值的所有位。

7 软缓存

我们希望散列函数计算散列值是容易的，快速的，但如果散列值的计算很耗时，那么我们或许可以将每个键的散列值缓存起来，即在每个键中使用一个hash变量来保存它的hashCode()的返回值，相当于缓存使用。

第一次调用hashCode()方法，我们用散列函数计算对应的散列值，之后调用hashCode()会直接返回hash变量的值。

因为保证：当散列函数确定，同一对象多次调用hashCode都会返回相同的hash值，这是散列的一致性。

总的来说，要为一个数据类型实现一个优秀的散列方法需要满足三个条件：

• 一致性：等价的键必然产生相等的散列值。
• 高效性：计算简便。
• 均匀性：均匀地散列所有的值。

但是，在有性能要求时应该谨慎使用散列，因为糟糕的散列函数经常是性能问题的罪魁祸首。

6.2 基于拉链法的散列表

前面我们提到的散列函数能将键转化为数组索引。散列算法的第二步是碰撞处理，也就是处理两个或多个键的散列值相同的情况，一种直接的办法是将大小为M的数组中的每个元素指向一条链表，链表中的每个结点都存储了散列值为该元素的索引的键值对，这种方法也称之为拉链法。

因为发生冲突的元素都被存储在链表中，我们希望尽可能选择足够大的M，使得所有链表都尽可能短以保证高效的查找。因为基于拉链法的散列表查找分两步：1是根据散列值找到对应的链表，2是遍历链表找到对应的key。

拉链表的一种实现方法是使用我们前面构建的无序链表作为数组元素，这样也可以复用无序链表的put,get方法。

因为我们要用M条链表保存N个键，无论键在各个链表中的分布如何，链表的平均长度都是N/M。

标准索引用例基于拉链法的散列表如图3.4.3：

基于拉链法的散列表的代码实现

public class SeparateChainingHashST <Key,Value>{

    private int N;  //键值对总数
    private int M; //散列表的大小
    private  SequentialSearchST<Key,Value>[] st;

    public SeparateChainingHashST(){
        this(1000);
    }
    public SeparateChainingHashST(int M){
        //创建M条链表
        this.M=M;
        st = new SequentialSearchST[M];
        for(int i=0;i<M;i++){
            st[i]=new SequentialSearchST<>();
        }
    }

    private int hash(Key key){
        return (key.hashCode() & 0x7fffffff)%M;
    }

    public Value get(Key key){
        return  st[hash(key)].get(key);
    }

    public void put(Key key,Value value){
        st[hash(key)].put(key,value);
    }

    public void delete(Key key){
        st[hash(key)].delete(key);
    }

    public boolean contains(Key key){
        return st[hash(key)].contains(key);
    }

    public Iterable<Key> keys(){
        Queue<Key> queue=new Queue<>();
        for(int i=0;i<M;++i){
            Queue<Key> tem=new Queue<>();
            tem= (Queue<Key>) st[i].keys();
            for(Key key:tem){
                queue.enqueue(key);
            }
        }
        return queue;
    }
}

1 删除操作

要删除散列表中的一个键值对，先用散列值找到含有该键的SequentialSearchST对象，然后调用该对象的delete方法即可。

2 有序性相关的操作

散列的最主要目的在于均匀地将键散布开来，因此在计算散列后键的顺序信息就丢失了。如果应用需要快速找到最大或者最小的键，或是查找某个范围内的键，或者其他有序性的操作，散列表都不是合适的选择，因为这些操作的运行时间是线性的。

基于拉链法的散列表的 实现简单，在键的顺序并不重要的应用中，它可能是最快的也是最广泛的实现。下面，我们介绍另一种解决碰撞冲突的有效方法。

6.3 基于线性探测法的散列表

实现散列表的另一种方式就是用大小为M的数组保存N个键值对，其中M>N，我们需要依赖数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为开放地址散列表。

开放地址散列表中最简单的方法叫做线性探测法：当碰撞发生时(当一个键的散列值已经被另一个不同的键占用)，我们直接检查散列表的下一个位置(将索引值+1并取余，形成一个循环)。这样的线性探测可能会产生三种结果：

• 命中：该位置的键和被查找的键相同
• 未命中：键为空(该位置没有键)
• 继续查找，该位置的键和被查找的键不同

我们首先用散列函数找到键在数组中的索引，检查其中的键和被查找的键是否相同，如果不同则继续查找(将索引+1，到达数组结尾折回数组的开头)，知道找到该键或者遇到一个空元素，如图3.4.6，我们将检查一个数组位置是否含有被查找的键的操作称作探测。

开放地址类的散列表的核心思想是：在实现中使用了并行数组，一条保存键，一条保存值。

图3.4.6

基于线性探测的符号表的代码实现

public class LinearProbingHashST <Key,Value>{


    private int N; //键值对的总数
    private int M=16; //线性探测表的大小
    private Key[] keys; //键
    private Value[] vals; //值
    public LinearProbingHashST(){
        keys = (Key[]) new Object[M];
        vals = (Value[]) new Object[M];
    }

    public LinearProbingHashST(int cap){
        keys= (Key[]) new Object[cap];
        vals= (Value[]) new Object[cap];
    }

    private int hash(Key key){
        return (key.hashCode() & 0x7fffffff)%M;
    }

    private void resize(int cap){
        LinearProbingHashST<Key,Value> tem=new LinearProbingHashST<>(cap);
        for(int i=0;i<M;i++){
            if(keys[i]!=null){
                tem.put(keys[i],vals[i]);
            }
        }
        keys = (Key[]) new Object[cap];
        vals = (Value[]) new Object[cap];
        keys= tem.keys;
        vals=tem.vals;
        M=tem.M;
    }

    public void put(Key key,Value val){
        if(N>=M/2){
            resize(2*M);
        }
        int i;
        for(i=hash(key);keys[i]!=null;i=(i+1)%M){
            if(key.equals(keys[i])){
                vals[i]=val;
                return;
            }
        }
        keys[i]=key;
        vals[i]=val;
        N++;
    }

    public Value get(Key key){
        for(int i=hash(key);keys[i]!=null;i=(i+1)%M){
            if(keys[i].equals(key)){
                return vals[i];
            }
        }
        return null;
    }

    public boolean contains(Key key){
        for(int i=hash(key);keys[i]!=null;i=(i+1)%M){
            if(key.equals(keys[i])){
                return true;
            }
        }
        return false;
    }

    public void delete(Key key){
        if(!contains(key)){
            return ;
        }
        int i=hash(key);
        while(!key.equals(keys[i])){
            i=(i+1)%M;
        }
        keys[i]=null;
        vals[i]=null;
        i=(i+1)%M;
        while (keys[i]!=null){
            Key temKey =keys[i];
            Value temValue=vals[i];
            keys[i]=null;
            vals[i]=null;
            N--;  //先删除再插入
            put(temKey,temValue);
            i=(i+1)%M;
        }
        N--; //键值对数目减1
        if(N>0 && N==M/8){
            resize(M/2);
        }
    }
}

每次查一个键，先计算它的散列值，从它的散列值开始顺序查找，如果找到则命中，如果遇到空元素则为命中。

1 删除操作

如何从基于线性探测的散列表中删除一个键？考虑直接将该键所在的位置设为null，发现是不行的，因为这破坏了同一键簇是连在一起的特性，使得在此位置之后的元素无法被查找。

例如，假设在轨迹图(3.4.6)的例子中，我们需要用这种方法删除键C，然后查找H，H的散列值为4，但它实际存储在这一簇键的结尾，也就是7号位置，如果我们将5号位置设为null，get方法将无法找到H。

因此，我们需要将簇中被删除键的右侧的所有键重新插入散列表。删除操作如下：

public void delete(Key key){
    if(!contains(key)){
        return ;
    }
    int i=hash(key);
    while(!key.equals(keys[i])){
        i=(i+1)%M;
    }
    keys[i]=null;
    vals[i]=null;
    i=(i+1)%M;
    while (keys[i]!=null){
        Key temKey =keys[i];
        Value temValue=vals[i];
        keys[i]=null;
        vals[i]=null;
        N--;  //先删除再插入
        put(temKey,temValue);
        i=(i+1)%M;
    }
    N--; //键值对数目减1
    if(N>0 && N==M/8){
        resize(M/2);
    }
}	

在拉链法中，散列表的性能依赖于$\alpha=N/M$的，因为拉链法需要遍历一条链。

而线性探测法的性能也依赖于$\alpha=N/M$，但意义有所不同，我们将$\alpha$称为散列表的使用率，$\alpha$是表中已被占用空间的比例，它是不可能大于1的，因为M>N。事实上，我们是不允许$\alpha$达到1的，也就是散列表被沾满，此时未命中的查找导致无限循环。

为了保证性能，我们会动态调整数组的大小来保证使用率在1/8到1/2之间。

2 键簇

线性探测的平均成本取决于元素在插入数组后聚集成的一组连续的条目，也叫作键簇。显然，短小的键簇才能保证较高的效率。随着插入的键越来越多，这个要求越来越难满足，较长的键簇会越来越多，如图3.4.8。

研究表明：当散列表快满的时候查找所需的探测次数是巨大的，当使用率小于1/2探测预计次数只有1.5到2.5之间，因此，我们考虑动态调整散列表数组的大小。

6.4 调整数组大小

我们可以使用resize方法保证使用率永远都不会超过1/2，如下：

private void resize(int cap){
    LinearProbingHashST<Key,Value> tem=new LinearProbingHashST<>(cap);
    for(int i=0;i<M;i++){
        if(keys[i]!=null){
            tem.put(keys[i],vals[i]);
        }
    }
    keys = (Key[]) new Object[cap];
    vals = (Value[]) new Object[cap];
    keys= tem.keys;
    vals=tem.vals;
    M=tem.M;
}

调用resize方法保证散列表最多为半满状态。

拉链法和线性探测法的区别主要在于：拉链法为每个键值对都分配了一小块内存(Node)而线性探测为整张表使用了两个很大的数组。

​

通过对散列表的分析，期望散列表能够支持和数组大小无关的常数级别的查找和插入操作是可能的。对于任意的符号表实现，这个期望都是理论上的最优性能，但散列表并非就是万能的。因为：

• 每种类型的键都需要一个优秀的散列函数
• 性能保证来自于散列函数的质量
• 散列函数的计算有可能复杂且昂贵
• 难以支持有序性操作

所以，选择以何种方式(无序链表？有序数组？二叉查找树，红黑树？散列表)实现我们的符号表还是要取决于我们具体应用的所需要的操作和对性能内存的限制。

7 应用

7.1 选择符号表的哪种实现

表3.5.1总结了本章多个命题的性质得到的各种符号表算法的性能特点，从表中可以知道，对于典型的应用程序，应该在散列表和二叉查找树之间进行选择。

相对于二叉查找树而言，散列表的优点在于代码更加简单，且查找时间更优。二叉查找树相对于散列表的优点是在于抽象结构更简单，不需要设计散列函数，红黑树可以保证最坏情况下的性能且它能支持的操作更多(如有序性操作的rank，select，范围查找等)。

7.2 用例

符号表的使用非常的广泛，可以用作字典类，索引类等等，还有白名单和黑名单，反向索引等等

典型的字典类应用如图3.5.3

典型的索引类应用如图3.5.4

典型的反向索引如图3.5.5

完结…

参考资料：《算法4》