Trie—單詞查找樹

l  簡介

Trie，又稱單詞查找樹、前綴樹，是一種哈希樹的變種。應用于字符串的統計與排序，經常被搜索引擎系統用于文本詞頻統計。

含有單詞“tea”“tree”“A”“ZSU”的一棵Trie。

l  性質

n  根節點不包含字符，除根節點外的每一個節點都只包含一個字符。

n  從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串。

n  每個節點的所有子節點包含的字符都不相同。

l  優點

n  查詢快。對于長度為m的鍵值，最壞情況下只需花費O(m)的時間；而BST最壞情況下需要O(m log n)的時間。

n  當存儲大量字符串時，Trie耗費的空間較少。因為鍵值并非顯式存儲的，而是與其他鍵值共享子串。

n  Trie適用于“最長前綴匹配”。

l  操作

n  初始化或清空

遍歷Trie，刪除所有節點，只保留根節點。

n  插入字符串

1.     設置當前節點為根節點，設置當前字符為插入字符串中的首個字符；

2.     在當前節點的子節點上搜索當前字符，若存在，則將當前節點設為值為當前字符的子節點；否則新建一個值為當前字符的子節點，并將當前結點設置為新創建的節點。.

3.     將當前字符設置為串中的下個字符，若當前字符為0，則結束；否則轉2.

n  查找字符串

搜索過程與插入操作類似，當字符找不到匹配時返回假；若全部字符都存在匹配，判斷最終停留的節點是否為樹葉，若是，則返回真，否則返回假。

n  刪除字符串

首先查找該字符串，邊查詢邊將經過的節點壓棧，若找不到，則返回假；否則依次判斷棧頂節點是否為樹葉，若是則刪除該節點，否則返回真。

l 實現
對于字符表大小為S的字符串集，需建立一個S叉樹來代表這些字符串的集合。

l  代碼

trie.h
/**//** 版權所有 (C) 2009 喻揚 中山大學
/* 本程序只作學習用途，未經許可，不得用于任何商業目的。
*/
#include <string.h>

/**//* trie的節點類型 */
template <int Size> //Size為字符表的大小
struct trie_node {
    /**//* 數據成員 */
    bool terminable; //當前節點是否可以作為字符串的結尾
    int node; //子節點的個數
    trie_node *child[Size]; //指向子節點指針

    /**//* 構造函數 */
    trie_node() : terminable(false), node(0) { memset(child, 0, sizeof(child)); }
};

/**//* trie */
template <int Size, typename Index> //Size為字符表的大小，Index為字符表的哈希函數
class trie {
public:
    /**//* 定義類型別名 */
    typedef trie_node<Size> node_type;
    typedef trie_node<Size>* link_type;

    /**//* 構造函數 */
    trie(Index i = Index()) : index(i) {}

    /**//* 析構函數 */
    ~trie() { clear(); }

    /**//* 清空 */
    void clear() {
        clear_node(root);
        for (int i = 0; i < Size; ++i) root.child[i] = 0;
    }

    /**//* 插入字符串 */
    template <typename Iterator>
    void insert(Iterator begin, Iterator end) {
        link_type cur = &root; //當前節點設置為根節點
        for (; begin != end; ++begin) {
            if (!cur->child[index[*begin]]) { //若當前字符找不到匹配，則新建節點
                cur->child[index[*begin]] = new node_type;
                ++cur->node; //當前節點的子節點數加一
            }
            cur = cur->child[index[*begin]]; //將當前節點設置為當前字符對應的子節點
        }
        cur->terminable = true; //設置存放最后一個字符的節點的可終止標志為真
    }

    /**//* 插入字符串，針對C風格字符串的重載版本 */
    void insert(const char *str) { insert(str, str + strlen(str)); }

    /**//* 查找字符串，算法和插入類似 */
    template <typename Iterator>
    bool find(Iterator begin, Iterator end) {
        link_type cur = &root;
        for (; begin != end; ++begin) {
            if (!cur->child[index[*begin]]) return false;
            cur = cur->child[index[*begin]];
        }
        return cur->terminable;
    }

    /**//* 查找字符串，針對C風格字符串的重載版本 */
    bool find(const char *str) { return find(str, str + strlen(str)); }

    /**//* 刪除字符串 */
    template <typename Iterator>
    bool erase(Iterator begin, Iterator end) {
        bool result; //用于存放搜索結果
        erase_node(begin, end, root, result);
        return result;
    }

    /**//* 刪除字符串，針對C風格字符串的重載版本 */
    bool erase(char *str) {    return erase(str, str + strlen(str)); }

    /**//* 按字典序遍歷單詞樹 */
    template <typename Functor>
    void traverse(Functor &execute = Functor()) {
        visit_node(root, execute);
    }

private:
    /**//* 訪問某結點及其子結點 */
    template <typename Functor>
    void visit_node(node_type cur, Functor &execute) {
        execute(cur);
        for (int i = 0; i < Size; ++i) {
            if (cur.child[i] == 0) continue;
            visit_node(*cur.child[i], execute);
        }
    }
    /**//* 清除某個節點的所有子節點 */
    void clear_node(node_type cur) {
        for (int i = 0; i < Size; ++i) {
            if (cur.child[i] == 0) continue;
            clear_node(*cur.child[i]);
            delete cur.child[i];
            cur.child[i] = 0;
            if (--cur.node == 0) break;
        }
    }

    /**//* 邊搜索邊刪除冗余節點
       返回值用于向其父節點聲明是否該刪除該節點 */
    template <typename Iterator>
    bool erase_node(Iterator begin, Iterator end, node_type &cur, bool &result) {
        if (begin == end) { //當到達字符串結尾：遞歸的終止條件
            result = cur.terminable; //如果當前節點可以作為終止字符，那么結果為真
            cur.terminable = false; //設置該節點為不可作為終止字符，即刪除該字符串
            return cur.node == 0; //若該節點為樹葉，那么通知其父節點刪除它
        }
        if (cur.child[index[*begin]] == 0) return result = false; //當無法匹配當前字符時，將結果設為假并返回假，
                                                                  //即通知其父節點不要刪除它
        else if (erase_node(++begin--, end, *(cur.child[index[*begin]]), result)) { //判斷是否應該刪除該子節點
            delete cur.child[index[*begin]]; //刪除該子節點
            cur.child[index[*begin]] = 0; //子節點數減一
            if (--cur.node == 0 && cur.terminable == false) return true; //若當前節點為樹葉，那么通知其父節點刪除它
        }
        return false; //其他情況都返回假
    }

    /**//* 根節點 */
    node_type root;

    /**//* 將字符轉換為索引的轉換表或函數對象 */
    Index index;
};

l  參考資料