寫在前

• 什么是字典樹？

  1. Trie樹，即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。Trie 一詞來自 retrieval，發(fā)音為 /tri:/ "tree"，也有人讀為 /tra?/ "try"。
  2. 典型應(yīng)用是用于統(tǒng)計和排序大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是：最大限度地減少無謂的字符串比較。

  Trie的核心思想是空間換時間，利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。

• 基本性質(zhì)

  1. 根節(jié)點不包含字符，除根節(jié)點外每一個節(jié)點都只包含一個字符。

  2. 從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應(yīng)的字符串。

  3. 每個節(jié)點的所有子節(jié)點包含的字符都不相同。

• 復(fù)雜度分析

  1.插入和查詢的效率很高，時間復(fù)雜度都為O(m)，其中 m 是待插入/查詢的字符串的長度。

  注：關(guān)于查詢，會有人說 hash 表時間復(fù)雜度是O(1)不是更快？但是，哈希搜索的效率通常取決于 hash 函數(shù)的好壞，若一個壞的 hash 函數(shù)導致很多的沖突，效率并不一定比Trie樹高。

  2.最壞的空間復(fù)雜度實現(xiàn)方式可以到S^L，其中S為字符集L為最長長度

• Trie樹的應(yīng)用

  • 字符串檢索：事先將已知的一些字符串（字典）的有關(guān)信息保存到 Trie 里，查找另外一些未知字符串是否出現(xiàn)過或者出現(xiàn)頻率。
  • 字符串最長公共前綴：Trie 利用多個字符串的公共前綴來節(jié)省存儲空間，反之，當我們把大量字符串存儲到一棵 Trie 上時，我們可以快速得到某些字符串的公共前綴。
  • 排序：Trie 樹是一棵多叉樹，只要先序遍歷整棵樹，輸出相應(yīng)的字符串，便是按字典序排序的結(jié)果。
  • 作為其他數(shù)據(jù)結(jié)構(gòu)和算法的輔助結(jié)構(gòu)：如后綴樹，AC自動機等。

基本實現(xiàn)

前綴樹創(chuàng)建

假設(shè)有b，abc，abd，bcd，abcd，efg，hii 這6個單詞,那我們創(chuàng)建trie樹就得到。

可以看出，Trie樹的關(guān)鍵字一般都是字符串，而且Trie樹把每個關(guān)鍵字保存在一條路徑上，而不是一個結(jié)點中。另外，兩個有公共前綴的關(guān)鍵字，在Trie樹中前綴部分的路徑相同。

前綴樹的主要操作就是插入和查詢，即將一個字符串加入集合中和查詢集合中有沒有這個字符串。每個字符加兩個變量，path 定義節(jié)點經(jīng)過的次數(shù)，end 定義最后一個插入的節(jié)點

public class TrieNode {
    private int path;
    private int end;
    private TrieNode[] nexts;
    
    public TrieNode() {
        path = 0;
        end = 0;
        nexts = new TrieNode[26];
    }
}

前綴樹插入

private TrieNode root;  // 根節(jié)點

public TrieNode {
    root = new TrieNode();
}

/**
    往前綴樹中插入字符串(這里只包含26個小寫字母)
*/
private void insert(String word) {
    if (word == null) {
        return;
    }
    int n = word.length();
    char[] chs = word.toCharArray();
    TrieNode node = root;
    int index = 0;
    
    for (int i = 0; i < n; i++) {
        index = chs[i] - 'a';
        if (node.nexts[index] == null) {
            node.nexts[index] = new TrieNode();    // 創(chuàng)建當前字符
        }
        node = node.nexts[index];
        node.path++;
    }
    node.end++;
}

前綴樹查詢

/**
    1、查詢前綴樹某字符串出現(xiàn)的次數(shù)，返回結(jié)尾字符出現(xiàn)的次數(shù)，即node.end
    2、查詢以某字符串為前綴的數(shù)量，返回每個字符被劃過的次數(shù)，即node.path
    如果不存在返回-1，類似插入操作！
*/
private int searchCount(String str) {
    if (str == null) {
        return -1;
    }
    int n = str.length();
    char[] chs = str.toCharArray();
    TrieNode node = root;
    int index = 0;
    
    for (int i = 0; i < n; i++) {
        index = chs[i] - 'a';
        if (node.nexts[index] == null) {
            return -1;    
        }
        node = node.nexts[index];  
    }
    return node.end;    // 返回以當前關(guān)鍵字結(jié)尾的字符串的個數(shù)
    //return node.path;  //插字符串時到達幾次
}

/**
    3、查詢集合中是否存在某個字符串，同理
*/
private boolean search(String str) {
    if (str == null) {
        return false;
    }
    int n = str.length();
    char[] chs = str.toCharArray();
    TrieNode node = root;
    int index = 0;
    
    for (int i = 0; i < n; i++) {
        index = chs[i] - 'a';
        if (node.nexts[index] == null) {
            return false;    
        }
        node = node.nexts[index];  
    }
    return true;   
}

案例分析

T208 前綴樹

代碼實現(xiàn)：

class Trie {

    class TrieNode {
        boolean isEnd;
        TrieNode[] nexts = new TrieNode[26];
    }

    TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode(); 
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        if (word == null) {
            return;
        }
        TrieNode node = root;
        int index = 0;

        for (int i = 0; i < word.length(); i++) {
            index = word.charAt(i) - 'a';
            if (node.nexts[index] == null) {
                node.nexts[index] = new TrieNode();
            }
            node = node.nexts[index];
        }
        node.isEnd = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        if (word == null) {
            return false;
        }
        TrieNode node = root;
        int index = 0;
 
        for (int i = 0; i < word.length(); i++) {
            index = word.charAt(i) - 'a';
            if (node.nexts[index] == null) {
                return false;
            }
            // 指針移動
            node = node.nexts[index];
        }
        return node.isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        if (prefix == null) {
            return false;
        }
        TrieNode node = root;
        int index = 0;
 
        for (int i = 0; i < prefix.length(); i++) {
            index = prefix.charAt(i) - 'a';
            if (node.nexts[index] == null) {
                return false;
            }
            node = node.nexts[index];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

T421 數(shù)組最大異或值

待補充。。。