正在查看旧版本。 查看 当前版本.

与当前比较 查看页面历史记录

版本 1 当前 »

也称前缀树或Trie树，用于高效存储和检索指定的字符串或字符串前缀是否存在于指定的字符串集合中。字典树一般用于搜索词自动补全或拼写提示。通过在树结点中附加出现次数的信息，也可以用于统计词频，比如给出前缀，返回前5个搜索最频繁的搜索词。

字典树的三个基本性质：

  1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。

字典树支持以下操作：

  1. void insert(string word)：插入字符串word。
  2. bool search(string word)：返回字符串word是否存在于前缀树中。
  3. bool startWith(string prefix)：返回指定的前缀是否存在于前缀树中。
  4. vector<string> listStartWith(string prefix)：返回指定前缀的全部字符串。这个接口也可以设计成返回出现次数最多的前n个字符串。

以下是一个字典树的模板：

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() : children(26), isEnd(false) {}
    

    void insert(string word) {
        Trie* node = this;
        for (char ch : word) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }
};


例题：

  • 无标签