进大厂必会的数据结构——前缀树/字典树

  • Post author:
  • Post category:其他



目录


前缀树的定义


常见应用


基本原理


如何实现


代码验证


前缀树的定义

前缀树又称字典数树,Trie树(读作try),是哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计,也可用来做自动补全和拼写检查。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

常见应用

例如,在百度中搜索“为什么”,百度就会自动帮你补全一些常见的搜索问题。这些热词是怎么保存的呢?如果是用简单的线性表,就会需要大量重复的查找,效率较低;我们希望一个数据结构能够将相同前缀的字符串存放在一起,这样在查找的时候就可以快速取出了。

基本原理

它的原理非常简单,属于一看就会,一写就错的那种。如下图所示:例如我们有下列几个字符串:ad,ak,akp,akr和bp,我们如何构建前缀树呢?从根节点开始,比较字符串的每一个字符是否在树的当前节点有对应的边,如果有则路由到该边指向的下一节点,继续比较下一个字符。如ak节点:就是0->1->4对应的边组成;akr节点:就是0->1->4->7对应的边组成。可以看到所有的节点如果是字符串的末尾的字符都标为黑色,这是为了区分字符串前缀和字符串(如ak,既是字符串,又是akr和akp的前缀),在后面的代码上也有体现。

前缀树的主要操作是插入和查找,一般很少进行删除,即便是删除也是伪删除,即将一个变量置为删除,而不会释放其空间,这是因为物理上的删除将要改变前缀树已有的结构,牺牲性能。因此前缀树是一个只增不减的树。

如何实现

考虑实现该树的数据结构,首先要能保存当前节点的子节点的指针,建议使用指针数组来完成,例如要处理的是小写字母组成的字符,就可以用包含26个节点指针的数组。我们可以这样约定,如果某个字母存在,则指针数组对应的下标将指向该字母对应的节点,否则该下标的节点指向空。如字母c存在,则children[‘c’-‘a’] = next_ptr,否则children[‘c’-‘a’] = null。同时我们要能记录该节点是否是终节点,以区分字符串和字符串前缀,一个bool型变量即可。

 vector<Trie*> children; // 指针数组
 bool end;               // 是否为终点

首先来考虑如何向前缀树中插入一个字符串:从根节点node开始,遍历node的26个子节点,如果节点存在,则node指向该子节点,考虑下一节点和下一个字符;如果节点不存在,则子节点指向一个新建的节点,并依次考虑下一字符和新建下一节点。可以用如下伪代码描述:

    node = root
    for i=0...word.size-1:
        if node.children[word[i]-'a'] == null:     // 没有该字符对应的节点,则新建节点
            node.children[word[i]-'a'] = new node
        node = node.children[word[i]-'a']          // 考察下一个节点和下一个字符
    node.end = true    // 最后一个字符设置为终点

下来再来考虑如何判断一个字符或者字符前缀是否存在于树中:以判断前缀为例,只需要从根节点向下遍历,如果遇到某个字符对应的当前节点的下一节点不存在,则查找失败;直至遍历到最后一个字符,则查找成功。判断字符也是一样的操作,只不过最后要考虑最后一个节点的node.end是否为真。伪代码描述如下:

    node = root
    for i=0...word.size-1:
        if node.children[word[i]-'a'] == null:     // 没有该字符对应的节点,则返回失败
            return false
        node = node.children[word[i]-'a']          // 考察下一个节点和下一个字符
    return true    // 查找完全部字符,返回成功

代码验证

我们对Trie类的几个常用函数做进行如下假设:


  • Trie()

    初始化前缀树对象。

  • void insert(String word)

    向前缀树中插入字符串

    word


  • boolean search(String word)

    如果字符串

    word

    在前缀树中,返回

    true

    (即,在检索之前已经插入);否则,返回

    false

  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false

具体实现,以c++为例,实现的函数一个类,可以使用leetcode验证:

208. 实现 Trie (前缀树)

class Trie {
    private:
        vector<Trie*> children; // 指针数组
        bool end;               // 是否为终点

    public:
        /*初始化节点*/
        Trie() {
            this->children = vector<Trie*>(26, NULL);
            this->end = false;
        }
        
        /*插入函数*/
        void insert(string word) {
            // 从根节点开始
            Trie* node = this;
            // 遍历每一个字符和节点
            for(int i=0; i<word.length(); i++){
                // 不存在该节点则新建
                if(node->children[word[i]-'a'] == NULL){
                    node->children[word[i]-'a'] = new Trie();
                }
                // 考察下一个节点
                node = node->children[word[i]-'a'];
            }
            // 最后一个字符设置为终点
            node->end = true;
        }
        
        /*查找字符串是否存在*/
        bool search(string word) {
            // 从根节点开始
            Trie* node = this;
            // 遍历每一个字符和节点
            for(int i=0; i<word.length(); i++){
                // 不存在该节点则失败
                if(node->children[word[i]-'a'] == NULL){
                    return 0;
                }
                // 考察下一节点
                node = node->children[word[i]-'a'];
            }
            // 注意:要为终点才是查找成功,否则只是字符串前缀
            return node->end;
        }
        
        /*查找字符串前缀是否存在*/
        bool startsWith(string prefix) {
            // 从根节点开始
            Trie* node = this;
            // 遍历每一个字符和节点
            for(int i=0; i<prefix.length(); i++){
                // 不存在该节点则失败
                if(node->children[prefix[i]-'a'] == NULL){
                    return 0;
                }
                // 考察下一节点
                node = node->children[prefix[i]-'a'];
            }
            // 查找成功
            return 1;
        }
};



版权声明:本文为yjjgoodbay原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。