摘要：謝路云單詞查找樹(shù)查找所需要的單詞的時(shí)間和鍵的長(zhǎng)度成正比查找未命中只需檢查若干個(gè)單詞單詞查找樹(shù)單詞查找樹(shù)基本性質(zhì)每個(gè)鏈接對(duì)應(yīng)一個(gè)字符每個(gè)結(jié)點(diǎn)可能有一個(gè)值有值，說(shuō)明存在從根結(jié)點(diǎn)到這個(gè)結(jié)點(diǎn)的字符串。它的存在是為了簡(jiǎn)化查詢(xún)。

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

查找所需要的單詞的時(shí)間和鍵的長(zhǎng)度成正比

查找未命中只需檢查若干個(gè)單詞

每個(gè)鏈接對(duì)應(yīng)一個(gè)字符

每個(gè)結(jié)點(diǎn)可能有一個(gè)值

有值，說(shuō)明存在從根結(jié)點(diǎn)到這個(gè)結(jié)點(diǎn)的字符串。

沒(méi)有值，說(shuō)明不存在從根結(jié)點(diǎn)到這個(gè)結(jié)點(diǎn)的字符串。沒(méi)有對(duì)應(yīng)的鍵值。它的存在是為了簡(jiǎn)化查詢(xún)。

查找

命中： 對(duì)應(yīng)結(jié)點(diǎn)有值（注意不單單是指向該對(duì)應(yīng)結(jié)點(diǎn)d鏈接存在，并且該結(jié)點(diǎn)一定要有值！）

未命中： 沒(méi)有值 or 鏈接為空

結(jié)點(diǎn)的表示

每個(gè)結(jié)點(diǎn)下面有R個(gè)鏈接，一個(gè)鏈接對(duì)應(yīng)一個(gè)字符

鍵隱式地保存在結(jié)點(diǎn)里

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); //神來(lái)之筆
        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++) //這個(gè)效率簡(jiǎn)直了。。。爛到爆炸
            collect(x.next[c], pre + c, q);
    }
}

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

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

方法collect：遞歸用

結(jié)構(gòu)差異

不含通配符的結(jié)構(gòu)。keysWithPrefix(); get(); collect();

含通配符的結(jié)構(gòu)。keysWithPrefix(); collect();

為什么結(jié)構(gòu)和之前不一樣呢？因?yàn)間et方法要重寫(xiě)。直接把重寫(xiě)的get方法歸并進(jìn)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=="." 就要遍歷接在當(dāng)前字符后面的所有字符！??！
                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āng)前搜索的是第d位字符，返回的是具有最長(zhǎng)length位前綴的子字符
    private int search(Node x, String s, int d, int length) {
        if (x == null) // 查到單詞樹(shù)的盡頭了
            return length;
        if (x.val != null) // 如果存在這個(gè)單詞，就更新length值
            length = d;
        if (d == s.length()) // 查到字符串的盡頭了（一定要先做上一步）
            return length;
        char c = s.charAt(d);
        return search(x.next[c], s, d + 1, length); //遞歸搜索下一位
    }

依舊是神一般的遞歸思路

如果它的鏈接不為空

刪去這個(gè)結(jié)點(diǎn)的值即可

如果它的所有鏈接都為空

刪去這個(gè)結(jié)點(diǎn)

檢查這個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)的所有鏈接是否為空

不為空，結(jié)束

為空，刪去父結(jié)點(diǎn)并檢查父結(jié)點(diǎn)的父結(jié)點(diǎn)是否為空
……循環(huán)如此

    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()) //找到了的話(huà)就將該結(jié)點(diǎn)的值刪去
            x.val = null;
        else {
            char c = key.charAt(d);
            x.next[c] = delete(x.next[c], key, d + 1); //依舊是神一般的遞歸思路
        }
        if (x.val != null) //如果該結(jié)點(diǎn)有值，則不管當(dāng)前結(jié)點(diǎn)鏈接是否為空，該結(jié)點(diǎn)都在樹(shù)里，不能被刪去。
            return x;
        for (char c = 0; c < R; c++) //否則就看該結(jié)點(diǎn)鏈接是否為空（即該結(jié)點(diǎn)沒(méi)有值）
            if (x.next[c] != null) //如果當(dāng)前結(jié)點(diǎn)鏈接不為空，則返回當(dāng)前結(jié)點(diǎn)
                return x; 
        return null; //否則返回為空。（因?yàn)槭欠祷厣弦粚舆f歸， 即把自己置為空，也即刪除了自己）
    }

字母表大小為R，N個(gè)隨機(jī)鍵組成的單詞查找樹(shù)中

時(shí)間：

查找和插入最差時(shí)間為：鍵的長(zhǎng)度+1

查找未命中的平均時(shí)間為：log_RN （查找未命中的時(shí)間和鍵的長(zhǎng)度無(wú)關(guān)）

空間

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

鏈接

一棵單詞查找樹(shù)的鏈接總數(shù)為RN到RNw之間，w為鍵的平均長(zhǎng)度

當(dāng)所有鍵較短時(shí)，鏈接總數(shù)接近RN

當(dāng)所有鍵較長(zhǎng)時(shí)，鏈接總數(shù)接近RNw

縮小R能節(jié)省大量空間

避免空間消耗

每個(gè)結(jié)點(diǎn)含有一個(gè)字符，三個(gè)鏈接（小于，等于，大于），可能含有一個(gè)值

字符是顯式保存在每個(gè)結(jié)點(diǎn)中

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