trie树

文章内容来自
Trie树：应用于统计和排序
Trie树

• trie树又称：字典树、单词查找树、前缀树等，总之是一种树状结构

• 实现形式，一幅图就能够说明，如下图所示

  
  QQ截图20140907005657.jpg
  

  对于英文字符串，其每个节点包括26个next指针，每个指针对应一个字母，即每一条边为一个字母，同时每个节点包括一个标识，表征从根节点到该节点的边是否组成了一个单词。其节点结构体如下

const int NUM = 26;
struct trieNode
{
    bool isStr;
    trieNode *next[NUM];
};

• 基本操作：查找、插入、删除

class trie
{
private: trieNode * root;
         int strNum;
public:  bool insert(char *str);
         bool query(char *str);     
         void del(trieNode *root);              //删除整棵树
         int getCount(){return strNum;}
         trie():root(new trieNode()),strNum(0){}
         ~trie(){ del(root); }
};

假设存在字符串str，Trie树的根结点为root。i=0，p=root。
1.插入
1)取str[i]，判断p->next[str[i]-'a']是否为空，若为空，则建立结点temp，并将p->next[str[i]-‘a’]指向temp，然后p指向temp；
若不为空，则p=p->next[str[i]-'a']；
2)i++，继续取str[i]，循环1)中的操作，直到遇到结束符'\0'，此时将当前结点p中的isStr置为true。

bool trie::insert(char *str)
{
    if (str == NULL)
        return false;
    trieNode * p = root;
    while(*str != '\0')
    {
        if (p->next[(*str)-'a'] == NULL)
        {
            p->next[(*str)-'a'] = new trieNode();
            p = p->next[(*str)-'a'];
        }
        else
            p = p->next[(*str)-'a'];
        str++;
    }
    if (p->isStr)
        return false;       //已存在这个单词
    else
    {
        p->isStr = true;
        strNum++;
        return true;
    }
}

2.查找
1)取str[i]，判断判断p->next[str[i]-‘a’]是否为空，若为空，则返回false；若不为空，则p=p->next[str[i]-'a']，继续取字符。
2)重复1)中的操作直到遇到结束符'\0',若当前结点p不为空并且isStr为true，则返回true，否则返回false。

bool trie::query(char *str)
{
    if (str == NULL)
        return false;
    trieNode * p = root;
    while (*str != '\0')
    {
        if (p->next[(*str)-'a'] == NULL)
            return false;
        else
            p = p->next[(*str)-'a'];
        str++;
    }
    return p->isStr;    
}

3.删除
删除可以以递归的形式进行删除。

void trie::del(trieNode *root)
{
    if (root == NULL)
        return;
    for (int i = 0; i < NUM; i++)
    {
        if (root->next[i]!=NULL)
            del(root->next[i]);
    }
    if (root!=trie::root)
        delete root;    
}

简单的验证程序如下

#include <iostream>
#include <string>
#include "trie.h"
using namespace std;
int main()
{
    trie wordtree;
    string str;
    cout<<"输入一个句子:";
    do 
    {
        cin>>str;
        wordtree.insert(const_cast<char *>(str.c_str()));
    } while (str!="exit");
    do 
    {
        cout<<"输入要查找的单词";
        cin>>str;
        if(wordtree.query(const_cast<char *>(str.c_str())))
            cout<<str<<" is exsit"<<endl;
        else
            cout<<str<<" is not exsit"<<endl;
    } while (str!="exit");
    system("pause");    
}

• 用处：统计和排序大量的字符串、文本词频统计等
  字符串检索，词频统计，搜索引擎的热门查询,事先将已知的一些字符串（字典）的有关信息保存到trie树里，查找另外一些未知字符串是否出现过或者出现频率
  举例：
  1）有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
  2）给出N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
  3）给出一个词典，其中的单词为不良单词。单词均为小写字母。再给出一段文本，文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如，若rob是不良单词，那么文本problem含有不良单词。
  4）1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串
  5）寻找热门查询：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是1千万，但是如果去除重复和，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。

字符串最长公共前缀，Trie树利用多个字符串的公共前缀来节省存储空间，反之，当我们把大量字符串存储到一棵trie树上时，我们可以快速得到某些字符串的公共前缀
举例：

1. 给出N 个小写英文字母串，以及Q 个询问，即询问某两个串的最长公共前缀的长度是多少. 解决方案：
   首先对所有的串建立其对应的字母树。此时发现，对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数，于是，问题就转化为了离线 （Offline）的最近公共祖先（Least Common Ancestor，简称LCA）问题。
   而最近公共祖先问题同样是一个经典问题，可以用下面几种方法：1. 利用并查集（Disjoint Set），可以采用采用经典的Tarjan 算法； 2. 求出字母树的欧拉序列（Euler Sequence ）后，就可以转为经典的最小值查询（Range Minimum Query，简称RMQ）问题了；

排序,Trie树是一棵多叉树，只要先序遍历整棵树，输出相应的字符串便是按字典序排序的结果
举例：
给你N 个互不相同的仅由一个单词构成的英文名，让你将它们按字典序从小到大排序输出。

• 优势：在进行字符查找、比较时，可以大幅度的减少字符直接比较的次数。如果在一个字符串集内中有n个字符串中查找一个字符，逐个比较的复杂度为O(L*n)，L为字符串的长度，但是采用trie树可以使复杂度降到O(L)，当然这也是有代价的，时间复杂度降低了，相应的肯定需要更大的空间消耗，万物总是平衡的嘛

• reference
  Trie树：应用于统计和排序
  Trie树