Trie—單詞查找樹

l  簡介

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

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

l  性質

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

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

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

l  優(yōu)點

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

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

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

l  操作

n  初始化或清空

遍歷Trie，刪除所有節(jié)點，只保留根節(jié)點。

n  插入字符串

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

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

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

n  查找字符串

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

n  刪除字符串

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

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

l  代碼

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

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

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

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

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

    /**//* 析構函數(shù) */
    ~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; //當前節(jié)點設置為根節(jié)點
        for (; begin != end; ++begin) {
            if (!cur->child[index[*begin]]) { //若當前字符找不到匹配，則新建節(jié)點
                cur->child[index[*begin]] = new node_type;
                ++cur->node; //當前節(jié)點的子節(jié)點數(shù)加一
            }
            cur = cur->child[index[*begin]]; //將當前節(jié)點設置為當前字符對應的子節(jié)點
        }
        cur->terminable = true; //設置存放最后一個字符的節(jié)點的可終止標志為真
    }

    /**//* 插入字符串，針對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);
        }
    }
    /**//* 清除某個節(jié)點的所有子節(jié)點 */
    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;
        }
    }

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

    /**//* 根節(jié)點 */
    node_type root;

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

l  參考資料