单词查找树

和各种查找树一样，单词查找树也是由链接和结点所组成的数据结构，这些链接可能为空，也可能指向其他结点。每个结点都只可能有一个指向它的结点，称为它的父结点（根结点除外）。每个结点都含有R条链接，其中R为字母表的大小。单词查找树一般含有大量空链接，因此在绘制一幅单词查找树时，一般会忽略空链接。每个结点也含有一个相应的值，可以是空也可以是符号表中某个键所关联的值。具体来说，我们将每个键所关联的值保存在该键的最后一个字母所对应的结点中。

单词查找树的查找操作
从根结点开始，首先经过的是键的首字母所对应的链接；在下一个结点中沿着第二个字符所对应的链接继续前进；以此类推直到达到键的最后一个字母所指向的结点或是遇到一条空链接：

• 键的尾字符所对应的结点中值非空。这是一次命中的查找——键所对应的值就是尾字符结点中所保存的值。
• 键的尾字符所对应的结点中的值为空。这是一次未命中的查找——符号表中不存在被查找的键。
• 查找结束与一条空链接。这也是一次未命中的查找。

单词查找树中的插入操作
和二叉查找树一样，再插入前要进行一次查找：在单词查找树中意味着沿着被查找的键的所有字符到达树中表示尾字符的结点或是一个空链接：

• 在到达键的尾字符之前就遇到了一个空链接。在这种情况下，单词查找树中不存在与键的尾字符对应的结点，因此需要为键中还未被检查的每个字符创建一个对应的结点并将键值保存到最后一个字符中。
• 在遇到空链接之前就到达了键的尾字符。在这种情况下，将该结点的值设为键所对应的值。

基于单词查找树的符号表

public class TrieST<Value>{
    private static int R = 256;      //基数
    private Node root;            //单词查找树的根结点
    private static class Node{
        private Object val;
        private Node[] next = new Node[R];
    }
    public Value get(String key){
        Node x = get(root, key, 0);
        if(x == null) return null;
        return (Value) x.val;
    }
    private Node get(Node x, String key, int d){
    //返回以x作为根结点的子单词查找树中与key关联的值
        if(x == null) return null;
        if(d = key.length()) return x;
        char c = key.charAt(d);        //找到第d个字符所对应的子单词查找树
        return get(x.next[c], key, d+1);
    }
    public void put(String key, Value val)
    { root = put(root, key, val, 0); }
    private Node put(Node x, String key, Value val, int d){
    //如果key存在于以x为根结点的子单词查找树中则更新与它相关联的键值
        if( x == null) x = new Node();
        if(d == key.length()) { x.val = val; return x; }
        char c = key.charAt(d);      //找到第d个字符所对应的子单词查找树
        x.next[c] = put(x.next[c], key, val, d+1);
        return x;
    }
}

查找所有键
先考虑如何得到单词查找树的大小。单词查找树的大小通过size()方法返回，有以下三种实现选择：

• 即时实现：用一个实例变量N保存键的数量。
• 更加即时的实现： 用结点的实例变量保存子单词查找树中键的数量，在递归的put()和delete()方法调用之后更新它们。
• 延时递归实现：遍历单词查找树中的所有结点并记录非空值结点的总数。

public int size()
{ return size(root); }
private int size(Node x){
{
    if( x == null ) return 0;
    int cnt = 0;
    if( x.val != null) cnt++;
    for( char c = 0; c <R; c++)
        cnt += size(next[c]);
    return cnt;
}

延时实现很有指导意义但应尽量避免，因为它会给用例造成性能上的问题。
因为字符和键是被隐式的表示在单词查找树中，所以使用例能遍历符号表的所有键就变得有些困难。我们用一个类似于size()的私有递归方法collect()来完成。它维护了一个字符串用来保存从根结点出发的路径中的一系列字符。每当我们在collect()调用访问一个结点时，方法的第一个参数就是该结点，第二个参数则是和该结点相关联的字符串。在访问一个结点时，如果它的值为空，我们就将和它相关联的字符串加入到队列中，然后递归的访问它的链接数组指向的所有可能的字符结点。在每次调用之前，都将链接对应的字符添加到当前键的末尾作为调用的参数键。用collect()方法为API中的keys()和keysWithPrefix()方法收集符号表中的所有键。

public Iterable<String> keys()
{ return keysWithPrefix(""); }
public Iterable<String> keysWithPrefix(String pre){
    Queue<String> q = new Queue<String>();
    collect(get(root, pre, 0), pre, q);
    return q;
}
private void collect(Node x, String pre, Queue<String> q){
    if(x == null) return;
    if(x.val != null) q.enqueue(pre);
    for(char c = 0; c<R; c++)
        collect(x.next[c], pre+c, q);
}

通配符匹配
我们可以用一个类似的过程实现keysThatMatch(),但需要为collect()方法添加一个参数来指定匹配的模式。如果模式中含有通配符，就需要递归调用处理所有的链接，否则就只需要处理模式中指定字符的链接即可。

public Iterable<String> keysThatMatch(String pat){
    Queue<String> q = new Queue<String>();
    collect(root, "", pat, q);
    return q;
}
private void collect(Node x, String pre, String pat, Queue<String> q){
    int d = pre.length();
    if(x == null) return;
    if(d == pat.length() && x.val != null)  q.enqueue(pre);
    if(d == pat.length()) return;
    char next = pat.charAt(d);
    for(char c =0; c<R; c++)
        if(next == '.' || next == c)
            collect(x.next[c], pre+c, pat, q);
}

最长前缀
为了找到给定字符串的最长键前缀，就需要使用一个类似于get()的递归方法。它会记录查找路径上所找到的最长键长度（将它作为递归方法的参数在遇到值非空的结点时更新它）。查找会在被查找的字符串遇到空链接时终止。

public String longestPrefixOf(String s){
    int length = search(root, s, 0, 0);
    return s.substring(0, length);
}
private int search(Node x, String s, int d, int length){
    if(x == null) return length;
    if(x.val != null) length = d;
    if(d == s.length()) return length;
    char c = s.charAt(d);
    return search(x.next[c], s, d+1, length);
}

删除操作
从一棵单词查找树中删去一个键值对的第一步是找到该键所对应的结点并将它的值设为空。如果该结点含有一个非空的链接指向某个子结点，就不需要其他操作。如果它的所有链接均为空，那就需要从数据结构中删去这个结点。如果删去它使得它的父结点也为空，那就继续删除它的父结点，并以此类推。

public void delete(String key)
{ root = delete(root, key, 0); }
private Node delete(Node x, String key, int d){
    if( x == null) return null;
    if(d == key.length())
        x.val = null;
    else{
        char c = key.charAt(d);
        x.next[c] = delete(x.next[c], key, d+1);
    }
    if(x.val != null) return x;
    for( char c =0; c<R; c++)
        if(x.next[c] != null) return x;
    return null;
}

---

三向单词查找树
在三向单词查找树中，每个结点都含有一个字符，三条链接和一个值。这三条链接分别对应着当前字母小于，等于和大于结点字母的所有键。在于之前R向单词查找树等价的三向查找树中，字符是显示的保存在结点中的——只有沿着中间链接前进时才会根据字符找到表中的键。

查找与插入操作
用三向单词查找树实现符号表API中的查找和插入操作很简单。在查找时，我们首先比较键的首字母和结点中的字母。如果键的首字母较小，就选择左链接；如果较大，就选择右链接；如果相等，则选择中链接。然后，递归的使用相同的算法。如果遇到了一个空链接或是当键结束时值为空，那么查找未命中；如果键结束时结点的值非空则查找命中。在插入一个新键时，首先进行查找操作，然后和在单词查找树中一样，在树中补全键末尾的所有结点。

public class TST<Value>{
    private Node root;          //树的根结点
    private class Node{
        char c;                        //字符
        Node left, mid, right;      //左中右子三向查找树
        Value val;                  //和字符相关联的值
    }
    public  Value get(String key)    //和单词查找树相同
    private Node get(Node x, String key, int d){
        if( x == null) return null;
        char c = key.charAt(d);
        if( c < x.c)    return get(x.left, key, d);
        else if(c > x.c)    return get(x.right, key, d);
        else if(d< key.length() - 1)  
            return get(x.mid, key, d+1);
        else return x;
    }
    public void put(String key, Value val)
    { root = put(root, key, val, 0); }
    private Node put(Node x, String key, Value val, int d){
        char c = key.charAt(d);
        if( x == null) { x = new Node(); x.c = c; }
        if( c < x.c)  x.left = put(x.left, key, val, d);
        else if( c > x.c) x.right = put(x.right, key, val, d);
        else if( d<key.length() -1)
            x.mid = put(x.mid, key, val, d+1);
        else x.val = val;
        return x;
    }
}