Post

Trie

Posted
By 8 min read

大致思想, 一颗 n 叉树, 从根结点至一个合法结点的路径所构成的字符串为该合法结点所代表的字符串. 其中 n 为树存储的字符集大小.

结点定义

就普通多叉树的结点定义, 在此基础上增加一个标记用来判断当前结点是否合法( 构成字符串 )

1
2
3
4
5
6

struct node
{
    bool isEnd;
    vector<node *> child;
    node(int nodeNums = 26) : isEnd(false), child(nodeNums, nullptr) {}
};

插入

就普普通通多叉树插入咯, 遇到 nullptr 就动态开点, 最后的结点打上标记为合法结点

1
2
3
4
5
6
7
8
9
10
11

void insert(const string &s)
{
    auto cur = root;
    for (auto &ch : s)
    {
        if (cur->child[ch - 'a'] == nullptr)
            cur->child[ch - 'a'] = new node();
        cur = cur->child[ch - 'a'];
    }
    cur->isEnd = true;
}

查询

能够查询许多信息, 举两个例, 大体思想都是沿着查询字符串进行遍历

存在性查询

1
2
3
4
5
6
7
8
9
10
11

bool exist(const string &s)
{
    auto cur = root;
    for (auto &ch : s)
    {
        if (cur->child[ch - 'a'] == nullptr)
            return false;
        cur = cur->child[ch - 'a'];
    }
    return cur->isEnd;
}

前缀查询

你如果要查最长前缀的话, 就不提前返回即可, 甚至你可以直接输出一个前缀数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

string findShortestPrefix(const string &s)
{
    string res;
    auto cur = root;
    for (auto &ch : s)
    {
        if (cur->child[ch - 'a'] == nullptr)
            return "";
        cur = cur->child[ch - 'a'];
        res += ch;
        if (cur->isEnd)
            return res;
    }
    if (cur->isEnd)
        return res;
    else
        return "";
}

删除

针对删除的结点是否是叶子结点, 有不一样的删除操作. 若是叶子结点被删除, 那么路径上的上一个合法结点后的所有结点应当被删除; 若删除结点非叶子结点, 那么只需要将合法标志移除无需删除结点.

可以转换成, 在单链表中, 删除 (prev, end] 这个区间内的结点. 其中 prev 记录的是上一个最近的合法结点, end 为要删除的合法叶子结点.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

bool remove(const string &s)
{
    auto cur = root;
    auto prev = root;
    int prevIdx = -1;
    for (int idx = 0; idx < s.size(); ++idx)
    {
        if (cur->child[s[idx] - 'a'] == nullptr)
            return false;
        cur = cur->child[s[idx] - 'a'];
        if (cur->isEnd && idx != s.size() - 1)
            prev = cur, prevIdx = idx;
    }
    if (!cur->isEnd)
        return false;
    cur->isEnd = false;
    for (int next = 0; next < 26; ++next)
    {
        if (cur->child[next] != nullptr)
            return true;
    }
    cur = prev->child[s[++prevIdx] - 'a'];
    auto next = cur;
    for (int idx = prevIdx + 1; idx < s.size() - 1; ++idx)
    {
        next = cur->child[s[idx] - 'a'];
        delete cur;
        cur = next;
    }
    delete cur;
    return true;
}

说实话, 翻了无数论坛(半个月), 没找到一个老老实实回收内存空间的 Trie 结点删除, 更别提写着优雅”官方可靠”的回收了. 省力的就对删除结点赋 nullptr, 但我感觉不对阿, 你只是把指针地址”置零”, 没有真的回收内存阿. 可能是觉得实现链表的中间链删除回收很麻烦? 事实上自己写下来感觉挺简单的, 毕竟链表结构大家都学过, 大一课设肯定也敲过呗.

事实上, 由于本人”完美主义病”犯了, 中间一味追求优雅写法, 导致我写了小半个月. 实际上, 根据本人总结的链表相关思想: 疯狂开指针, 别小气, 很快就能写好.

实际工程应用

这都是奇技淫巧! ——非著名计算机大牛树懒懒

了解了一下, 确实如此. 考虑到工程中通常需要支持一个较大的字符集, 整个 Trie 树必然存在极大空间浪费. 同时, 当存在部分较长字符串时, 整个树深将大大增加, 会造成硬盘随机 IO 次数增加( 参考待考 ). 不考虑前缀匹配的话, 哈希表可以做到更快更小.

在更广泛的应用, 如模糊匹配时, 通常使用 Elasticsearch 引擎, 这玩意儿通过倒排索引实现, 感觉可以额外开新章学习学习这个玩意儿.

下述代码能通过 Leetcode 实现Trie树一题, 下列实现是该题的超集, 能通过主函数的测试, 感觉没啥问题.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

class Trie
{
private:
    struct node
    {
        bool isEnd;
        vector<node *> child;
        node(int nodeNums = 26) : isEnd(false), child(nodeNums, nullptr) {}
    };
    node *root;

public:
    void insert(const string &s)
    {
        auto cur = root;
        for (auto &ch : s)
        {
            if (cur->child[ch - 'a'] == nullptr)
                cur->child[ch - 'a'] = new node();
            cur = cur->child[ch - 'a'];
        }
        cur->isEnd = true;
    }
    bool exist(const string &s)
    {
        auto cur = root;
        for (auto &ch : s)
        {
            if (cur->child[ch - 'a'] == nullptr)
                return false;
            cur = cur->child[ch - 'a'];
        }
        return cur->isEnd;
    }
    bool remove(const string &s)
    {
        auto cur = root;
        auto prev = root;
        int prevIdx = -1;
        for (int idx = 0; idx < s.size(); ++idx)
        {
            if (cur->child[s[idx] - 'a'] == nullptr)
                return false;
            cur = cur->child[s[idx] - 'a'];
            if (cur->isEnd && idx != s.size() - 1)
                prev = cur, prevIdx = idx;
        }
        if (!cur->isEnd)
            return false;
        cur->isEnd = false;
        for (int next = 0; next < 26; ++next)
        {
            if (cur->child[next] != nullptr)
                return true;
        }
        cur = prev->child[s[++prevIdx] - 'a'];
        auto next = cur;
        for (int idx = prevIdx + 1; idx < s.size() - 1; ++idx)
        {
            next = cur->child[s[idx] - 'a'];
            delete cur;
            cur = next;
        }
        delete cur;
        return true;
    }
    string findShortestPrefix(const string &s)
    {
        string res;
        auto cur = root;
        for (auto &ch : s)
        {
            if (cur->child[ch - 'a'] == nullptr)
                return "";
            cur = cur->child[ch - 'a'];
            res += ch;
            if (cur->isEnd)
                return res;
        }
        if (cur->isEnd)
            return res;
        else
            return "";
    }
    Trie(int charSize = 26) : root(new node(charSize)) {}
    ~Trie() {}
};

int main()
{
    Trie trie;
    trie.insert("appl");
    trie.insert("app");
    trie.insert("branch");
    cout << trie.exist("ap") << " " << trie.exist("appl") << endl;
    cout << trie.findShortestPrefix("appleJing") << endl;
    cout << trie.remove("bran") << endl;
    cout << trie.remove("appl") << endl;
    cout << trie.exist("ap") << endl;
    cout << trie.exist("appl") << endl;
    cout << trie.exist("app") << endl;
    cout << trie.remove("app") << endl;
    cout << trie.exist("app") << endl;
    return 0;
}
Data Structure, Trie
data structure trie
This post is licensed under CC BY 4.0 by the author.