Trie树

数据结构

字数统计: 437阅读时长: 2 min

 2021/04/05   Share

Trie树

Trie树：

Trie的典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

类的写法：

class Trie {
    private:
        bool isEnd;
        Trie* next[26];
    public:
        /** Initialize your data structure here. */
        Trie() {
            isEnd = false;
            memset(next, 0, sizeof(next));
        }

        /** Inserts a word into the trie. */
        void insert(string word) {
            Trie* node = this;
            for (char c : word) {
                if (node->next[c - 'a'] == nullptr) {
                    node->next[c - 'a'] = new Trie();
                }
                node = node->next[c - 'a'];
            }

            node->isEnd = true;
        }

        /** Returns if the word is in the trie. */
        bool search(string word) {
            Trie* node = this;
            for (char c : word) {
                if (node->next[c - 'a'] == nullptr) {
                    return false;
                }
                node = node->next[c - 'a'];
            }
            return node->isEnd;
        }

        /** Returns if there is any word in the trie that starts with the given prefix. */
        bool startsWith(string prefix) {
            Trie* node = this;
            for (char c : prefix) {
                if (node->next[c - 'a'] == nullptr) {
                    return false;
                }
                node = node->next[c - 'a'];
            }
            return true;
        }
};

结构体写法：

struct node {
    bool isEnd;
    node* next[26];
    node() {
        isEnd = false;
        memset(next, 0, sizeof(next));
    }
};
void insert(string word, node* root) {
    node* t = root;
    for (char c : word) {
        if (t->next[c - 'a'] == nullptr) {
            t->next[c - 'a'] = new node;
        }
        t = t->next[c - 'a'];
    }
    t->isEnd = true;
}
bool search(string word, node* root) {
    node* t = root;
    for (char c : word) {
        if (t->next[c - 'a'] == nullptr) {
            return false;
        }
        t = t->next[c - 'a'];
    }
    return t->isEnd;
}
bool startsWith(string prefix, node* root) {
    node* t = root;
    for (char c : prefix) {
        if (t->next[c - 'a'] == nullptr) {
            return false;
        }
        t = t->next[c - 'a'];
    }
    return true;
}

原文作者：F_JustWei

原文链接：http://139.196.79.90/2021/04/05/Trie%E6%A0%91/

发表日期：April 5th 2021, 4:57:24 pm

更新日期：April 22nd 2021, 12:24:26 am

Next Post

TCP与UDP
Previous Post

二叉树的遍历

CATALOG

1. Trie树

