Trie

字典樹的介紹來自维基百科，自由的百科全书
（重定向自字典树）

Trie，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

性质

它有3个基本性质：

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

图示

这是一个Trie结构的例子： Trie example.svg

在这个Trie结构中，保存了A、to、tea、ted、ten、i、in、inn这8个字符串，仅占用8个字节（不包括指针占用的空间）。

 

 

以下是我自己寫的Trie的代碼：

 

#include <fstream>
/*
NOIP必备资料： Retrieval Tree 字典树
本程序为字典树的基本操作，包含字典树的建立、插入、删除的操作
本程序在GCC下编译通过并能正确工作
欢迎交流：zyfworks@gmail.com
*/

using namespace std;
const int sonnum=26; //子节点个数
const char base='a';

struct Trie
{
    bool isStr; //该处是否插入过一个字符串
    struct Trie *son[sonnum];//子节点
};

Trie *NewTrie() //Create a new node 建立一个新的字典树
{
    Trie *temp=new Trie;
    temp->isStr=false;
    for (int i=0;i<sonnum;i++)
        temp->son[i]=NULL;  //初始化子节点
    return temp;
}

void Insert(Trie *pnt,char *s,int len) //Insert a new word to Trie Tree
{                                      //向字典树插入一个新的字符串
    Trie *temp=pnt;
    for (int i=0;i<len;i++)
    {
        if (temp->son[s[i]-base]==NULL)
            temp->son[s[i]-base]=NewTrie();
        temp=temp->son[s[i]-base];
    }
    temp->isStr=true;
}

bool check(Trie *pnt,char *s,int len)  //测试字典树中是否存在某个字符串
{
    Trie *temp=pnt;
    for (int i=0;i<len;i++)
        if (temp->son[s[i]-base]!=NULL)
            temp=temp->son[s[i]-base];
        else return false;
    return temp->isStr;
}

void DeleteWord(Trie *pnt,char *s,int len)//从字典树中删除某个字符串
{
    Trie *temp=pnt;
    for (int i=0;i<len;i++)
        if (temp->son[s[i]-base]!=NULL)
            temp=temp->son[s[i]-base];
        else return;
    temp->isStr=false;
}

int main()
{
    Trie *Tree;
    Tree=NewTrie();
    ifstream fin("trie.in");
    ofstream fout("trie.out");
    char s[100];
    int m;
    fin>>m;
    for (int i=0;i<m;i++)
    {
        fin>>s;
        Insert(Tree,s,strlen(s));  //插入字符串
    }
    
    
    fin>>m;
    for (int i=0;i<m;i++)
    {
        fin>>s;
        DeleteWord(Tree,s,strlen(s)); //删除字符串
    }
    
    
    fin>>m;
    for (int i=0;i<m;i++)
    {
        fin>>s;
        fout<<check(Tree,s,strlen(s))<<endl;//测试字符串是否存在
    }
    return 0;
}