Trie 字典树/前缀树

wiki 定义
在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

和并查集的区别

并查集主要解决的问题是网络连接问题,集合的包含合并问题.而Trie主要通过空间换取时间,将需要查询的字符串拆解为一个个字符存储在节点中,实现每次查询是否包含字符串只需要付出O(K)(K 为字符串的长度) 的时间复杂度.

两者实际都是一种为了解决特定问题的多路树结构.

笔记内容

数据结构笔记-6.jpg

代码示例



# include <iostream>
# include <map>
# include <string>
class Node{
    private:
    
        bool isWord;
        map<char,Node*> next;
    public:
        Node(bool isWord=false)
        {
            this->isWord=isWord;
            
        }
        void addMap(char c)
        {
            next[c]=new Node();
        }
        bool findNode(char c)
        {
            return next.find(c)!=next.end();
        }
        inline void setWord(){isWord=true;}
        inline bool isTrue(){return isWord;}
        inline void clrWord(){isWord=false;}
        inline Node * Next(char c){return next[c];}
        inline map<char,Node*> *getNext(){return &next;}
        
};
class Trie{
  public:
    Trie()
    {
        root=new Node();
        size=0;
        
    }
    inline int getSize(){return size;}
    void add(string word)
    {
        Node* cur=root;
        for(int i=0;i<word.length();i++)
        {
            if(!cur->findNode(word[i]))
                cur->addMap(word[i]);
            cur=cur->Next(word[i]);
        }
        cur->setWord();
        size++;
    }
    bool contains(string word)
    {
        Node *cur=root;
        for(int i=0;i<word.length();i++)
        {
            if(!cur->findNode(word[i]))
                return false;
            cur=cur->Next(word[i]);
        }
        return cur->isTrue();
    }
    bool searchPrefix(string prefix)  //查找前缀 
    {
        Node *cur=root;
        for(int i=0;i<prefix.length();i++)
        {
            if(!cur->findNode(prefix[i]))
                return false;
            cur=cur->Next(prefix[i]);
        }
        return true;
    }
    bool searchMode(string word)  //模式查找
    {
        return match(root,word,0);
    }
    void delWord(string word)
    {
        if(contains(word))
            del(root,word,0);   
    }
  private:
    void del(Node *node,string word,int index)
    {
       if(index>word.length()||node==NULL)
       {
           return ;
       }
       del(node->Next(word[index]),word,index+1);

               if(node->getNext()->size())
               {
                   if(index==word.length());
                    node->clrWord();
               }else
               {
                   if(node!=root)
                   {
                   delete node;
                   *node=NULL;
                   }
               }

       }
    bool match(Node *node,string word,int index)
    {
        if(!node)
            return false;
        if(index==word.length())
            return node->isTrue();
        if(word[index]!='.'){
            if(!node->findNode(word[index]))
                return false;
            return match(node->Next(word[index]),word,index+1);
        
        }else
        {
            for(map<char,Node*>::iterator it=node->getNext()->begin();
                it!=node->getNext()->end();it++)
                {
                
                     if(match((*it).second,word,index+1))
                             return true;
                }
            return false;
        }
    }
  private:
    Node *root;
    int size;
};
int main()
{
    Trie tree;

    tree.add("heo");
    tree.delWord("heo");
    cout<<tree.searchMode("h.o");
    
    return 0;
}