摘要：謝路云單詞查找樹查找所需要的單詞的時間和鍵的長度成正比查找未命中只需檢查若干個單詞單詞查找樹單詞查找樹基本性質每個鏈接對應一個字符每個結點可能有一個值有值，說明存在從根結點到這個結點的字符串。它的存在是為了簡化查詢。

Algorithms Fourth Edition
Written By Robert Sedgewick & Kevin Wayne
Translated By 謝路云
Chapter 5 Section 2 單詞查找樹

查找所需要的單詞的時間和鍵的長度成正比

查找未命中只需檢查若干個單詞

每個鏈接對應一個字符

每個結點可能有一個值

有值，說明存在從根結點到這個結點的字符串。

沒有值，說明不存在從根結點到這個結點的字符串。沒有對應的鍵值。它的存在是為了簡化查詢。

查找

命中： 對應結點有值（注意不單單是指向該對應結點d鏈接存在，并且該結點一定要有值！）

未命中： 沒有值 or 鏈接為空

結點的表示

每個結點下面有R個鏈接，一個鏈接對應一個字符

鍵隱式地保存在結點里

public class TrieST {
    private static int R = 256; // radix
    private Node root; // root of trie

    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;
    }
    
    // Return value associated with key in the subtrie rooted at x.
    private Node get(Node x, String key, int d) { 
        if (x == null)
            return null;
        if (d == key.length())
            return x;
        char c = key.charAt(d); // Use dth key char to identify subtrie.
        return get(x.next[c], key, d + 1);
    }

    public void put(String key, Value val) {
        root = put(root, key, val, 0);
    }
    
    // Change value associated with key if in subtrie rooted at x.
    private Node put(Node x, String key, Value val, int d) { //神一般的遞歸思想
        if (x == null)
            x = new Node();
        if (d == key.length()) {
            x.val = val;
            return x;
        }
        char c = key.charAt(d); // Use dth key char to identify subtrie.
        x.next[c] = put(x.next[c], key, val, d + 1); //神來之筆
        return x;
    }

    public Iterable keys() {
        return keysWithPrefix("");
    }

    public Iterable keysWithPrefix(String pre) {
        Queue q = new Queue();
        collect(get(root, pre, 0), pre, q);
        return q;
    }

    private void collect(Node x, String pre, Queue 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);
    }
}

方法keys：返回一個Queue，里面有所有的字符串

方法keysWithPrefix(String pre)：返回一個Queue，里面有所有以給定字符串pre開頭的所有字符串

方法collect：遞歸用

結構差異

不含通配符的結構。keysWithPrefix(); get(); collect();

含通配符的結構。keysWithPrefix(); collect();

為什么結構和之前不一樣呢？因為get方法要重寫。直接把重寫的get方法歸并進collect方法里去了。

    public Iterable keysThatMatch(String pat) {
        Queue q = new Queue();
        collect(root, "", pat, q);
        return q;
    }

    public void collect(Node x, String pre, String pat, Queue q) {
        int d = pre.length(); 
        // begin修改于原get方法()和collect方法()
        if (x == null) // get&collect
            return;
        if (d == pat.length() && x.val != null) // 前collect，后get
            q.enqueue(pre);
        if (d == pat.length())// get
            return; 
        // end 修改于原get方法()和collect方法()
        
        char next = pat.charAt(d);
        for (char c = 0; c < R; c++)
            if (next == "." || next == c) //如果next=="." 就要遍歷接在當前字符后面的所有字符！！！
                collect(x.next[c], pre + c, pat, q); //還是神一般的遞歸想法
    }

private Node get(Node x, String key, int d) { 
        if (x == null)
            return null;
        if (d == key.length())
            return x;
        char c = key.charAt(d); // Use dth key char to identify subtrie.
        return get(x.next[c], key, d + 1);
    }

    public String longestPrefixOf(String s) {
        int length = search(root, s, 0, 0);
        return s.substring(0, length);
    }

    //當前搜索的是第d位字符，返回的是具有最長length位前綴的子字符
    private int search(Node x, String s, int d, int length) {
        if (x == null) // 查到單詞樹的盡頭了
            return length;
        if (x.val != null) // 如果存在這個單詞，就更新length值
            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，N個隨機鍵組成的單詞查找樹中

時間：

查找和插入最差時間為：鍵的長度+1

查找未命中的平均時間為：log_RN （查找未命中的時間和鍵的長度無關）

空間

與 R和所有鍵的字符總數之積 成正比

鏈接

一棵單詞查找樹的鏈接總數為RN到RNw之間，w為鍵的平均長度

當所有鍵較短時，鏈接總數接近RN

當所有鍵較長時，鏈接總數接近RNw

縮小R能節省大量空間

避免空間消耗

每個結點含有一個字符，三個鏈接（小于，等于，大于），可能含有一個值

字符是顯式保存在每個結點中

public class TST {
    private Node root; // root of trie

    private class Node {
        char c; // character
        Node left, mid, right; // left, middle, and right subtries
        Value val; // value associated with string
    }

    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) {
        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;
    }
}