Trie

摘要: 经典的 Trie 的实现，附代码模板和应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们以力扣 208 作为模板题来学习一下 Trie 的建树，插入和查找。并形成代码模板。

模板题

• 208. 实现 Trie (前缀树)

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

提示：

1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数 总计 不超过 3 * 1e4 次

示例：
输入
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 True
trie.search(“app”); // 返回 False
trie.startsWith(“app”); // 返回 True
trie.insert(“app”);
trie.search(“app”); // 返回 True

算法：Trie

Trie 的背景

Trie 是一颗度 m >= 2 的树(N叉树)，其每一层分支不是依赖整个 key 的值确定的，而是有 key 的一个分量决定的。例如：

• key 是单词，节点只包含单独的字母
• key 是数值，节点只含一个数位

以字符串为例:

• 在第 0 层，表示空字符串
• 在第 i 层，所有 key 根据它们的第 i 个字符，划分到互不相交的子树中，每个节点(子树)都表示以其根节点中 key 的开头的一个字符串，它是 key 的一个前缀。

Trie 3 条性质：

• 根节点不含字符，其它节点包含一个字符。
• 根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
• 每个节点的所有子节点包含的字符各不相同。

Trie 将集合，子集，元素之间的层次关系表示的很清楚，这对搜索有好处。Trie 有广泛的应用，例如自动补全，拼写检查等等。

Trie 的节点定义

按照 Trie 的性质，节点定义如下。其中有一个常数规定字母的个数，一个 vector<TrieNode*> 维护的指向子节点(子树)的指针`。一个结束标记，表示该节点表示的前缀是否是一个词。

struct TrieNode {
    const int ALPHABETS = 26;
    vector<TrieNode*> children;
    bool terminal;
    TrieNode()
    {
        terminal = false;
        children = vector<TrieNode*>(ALPHABETS, nullptr);
    }
    ~TrieNode(){}
};

除了以上定义中用 vector 以外，维护子节点指针还有哈希映射这一种主流方式：

unordered_map<char, TrieNode*> children;

下面是这两种维护子节点的实现方式的优缺点对比。

unordered_map 的好处：

• 由于只存储需要的子节点，因此节省了空间。
• 通过相应的字符来访问特定的子节点比 vector 的方式更为容易

unordered_map 的坏处：

• 比使用 vector 稍慢一些。
• 不同字符的子节点的顺序不受控制

vector<TrieNode*> 的好处：

• 访问子节点速度快。因为在大多数情况下，很容易将一个字符转换为索引。
• 可以根据对应的字符自定义子节点的顺序

vector<TrieNode*> 的坏处：

• 存储了很多用不到的子节点指针，可能会导致空间的浪费。

Trie 的插入(建树)

插入时候，根据当前节点值(字母)和待插入字符串对应位置的字母之间的关系，确定目标字符串需要去往哪个子节点。

例如在 Trie 中插入一个字符串 s：

• 从根节点开始。根据 s[0] 选择一个子节点，并进入，此时若该子节点不存在，则进入之前先添加一个新的子节点。
• 进入第 i 个节点(从0开始计)，根据 S[i] 选择子节点。进入第 i + 1 个节点。
• 直到遍历完 S 中的所有字符并到达末尾。 此时末端节将表示字符串 s 的节点。将该点的 terminal 标记设置为 true。

void insert(string word) {
    TrieNode *iter = root;
    for(const char c: word)
    {
        if(!(iter -> children[c - 'a']))
            (iter -> children)[c - 'a'] = new TrieNode();
        iter = (iter -> children)[c - 'a'];
    }
    iter -> terminal = true;
}

以上通过对比待插入值和节点值的关系确定去往的子树的策略，与二叉查找树的插入一样。

Trie 的查找

查找分为两种，一种是查找前缀，一种是查找单词。

查找前缀

查找前缀接口bool startsWith(string prefix)，根据需求，也可以返回所有持有目标前缀的单词。

因为节点的后代都与该节点相对应字符串有共同前缀。因此可以高效搜索以特定前缀开头的任何单词。

查找单词

查找单词接口bool search(string word)。

过程与查找前缀类似，根据给定的前缀沿着树形结构搜索下去。一旦找不到想要的子节点(根据当前字符得到的目标子节点为空)，搜索失败。

遍历完待查找字符串且到达的末尾字符所在节点，若该节点的终止标记为 true，则搜索成功，查找的单词存在，否则搜索仍然失败。

代码（模板）

c++，子节点用 vector 实现

struct TrieNode {
    const int ALPHABETS = 26;
    vector<TrieNode*> children;
    bool terminal;
    TrieNode()
    {
        terminal = false;
        children = vector<TrieNode*>(ALPHABETS, nullptr);
    }
    ~TrieNode(){}
};

class Trie {
public:
    Trie() 
    {
        root = new TrieNode();
    }

    ~Trie() 
    {
        delete_sub_tree(root);
    }

    void insert(string word) 
    {
        TrieNode *iter = root;
        for(const char c: word)
        {
            if(!(iter -> children[c - 'a']))
                (iter -> children)[c - 'a'] = new TrieNode();
            iter = (iter -> children)[c - 'a'];
        }
        iter -> terminal = true;
    }

    bool search(string word) 
    {
        const TrieNode* iter = find(word);
        return iter && iter -> terminal;
    }

    bool startsWith(string prefix) 
    {
        return find(prefix) != nullptr;
    }

private:
    TrieNode *root;

    void delete_sub_tree(TrieNode *node)
    {
        for(TrieNode *child: node -> children)
            if(child)
                delete_sub_tree(child);
        delete node;
        node = nullptr;
    }

    const TrieNode* find(const string& prefix) const
    {
        const TrieNode* iter = root;
        for(const char c: prefix)
        {
            iter = (iter -> children)[c - 'a'];
            if(iter == nullptr) break;
        }
        return iter;
    }
};

c++，子节点用 unordered_map 实现

struct TrieNode
{
    bool terminal;
    unordered_map<char, TrieNode*> children;
    TrieNode()
    {
        terminal = false;
        children = unordered_map<char, TrieNode*>();
    }
    ~TrieNode(){}
};

class Trie
{
public:
    Trie()
    {
        root = new TrieNode();
    }

    ~Trie()
    {
        if(root)
            delete_sub_tree(root);
        delete root;
        root = nullptr;
    }

    void insert(const string& word)
    {
        TrieNode *iter = root;
        for(const char& ch: word)
        {
            if((iter -> children).count(ch) == 0)
                (iter -> children)[ch] = new TrieNode();
            iter = (iter -> children)[ch];
        }
        iter -> terminal = true;
    }

    bool search(string word)
    {
        const TrieNode* iter = find(word);
        return iter && iter -> terminal;
    }

    bool startsWith(string prefix)
    {
        return find(prefix) != nullptr;
    }

private:
    TrieNode *root;

    void delete_sub_tree(TrieNode* node)
    {
        auto it = (node -> children).begin();
        while(it != (node -> children).end())
        {
            TrieNode *child = it -> second;
            if(child)
                delete_sub_tree(child);
            delete child;
            child = nullptr;
            ++it;
        }
    }

    const TrieNode* find(const string& prefix) const
    {
        TrieNode* iter = root;
        for(const char c: prefix)
        {
            if((iter -> children).count(c) == 0)
                return nullptr;
            iter = (iter -> children)[c];
        }
        return iter;
    }
};

Python，子节点用 list 实现

ALPHABETS = 26;

class TrieNode:
    def __init__(self):
        self.terminal = False
        self.children = [None] * ALPHABETS

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node_iter = self.root
        for c in word:
            if node_iter.children[ord(c) - ord('a')] is None:
                node_iter.children[ord(c) - ord('a')] = TrieNode()
            node_iter = node_iter.children[ord(c) - ord('a')]
        node_iter.terminal = True

    def search(self, word: str) -> bool:
        node_iter = self._find(word)
        return node_iter is not None and node_iter.terminal

    def startsWith(self, prefix: str) -> bool:
        return self._find(prefix) is not None

    def _find(self, prefix):
        node_iter = self.root
        for c in prefix:
            node_iter = (node_iter.children)[ord(c) - ord('a')]
            if node_iter is None:
                break
        return node_iter

Python，子节点用 dict 实现

class TrieNode:
    def __init__(self):
        self.terminal = False
        self.children = dict()

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node_iter = self.root
        for c in word:
            if c not in node_iter.children:
                node_iter.children[c] = TrieNode()
            node_iter = node_iter.children[c]
        node_iter.terminal = True

    def search(self, word: str) -> bool:
        node_iter = self._find(word)
        return node_iter is not None and node_iter.terminal

    def startsWith(self, prefix: str) -> bool:
        return self._find(prefix) is not None

    def _find(self, prefix):
        node_iter = self.root
        for c in prefix:
            if c not in node_iter.children:
                return None
            node_iter = (node_iter.children)[c]
        return node_iter

---