数据结构之——Trie树 及应用

数据结构之——Trie树

数据结构 

      Trie树，又称单词查找树，典型用于统计和排序大量字符串，查询效率比哈希表高。(空间复杂度高)

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

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

 

Trie树的结构体：

struct Trie_Node
{
    int id;//数据域
    Trie_Node *next[26];//孩子结点
    Trie_Node()
    {
        id = -1;
        memset(next,0,sizeof(next));
    }
}*root;

 

Trie树的更新操作(插入、查询某字符串的数据)

int getNum(char *t)
{
    Trie_Node *p = root;
    int i = 0,del;
    while(t[i] != '\0')
    {
        del = t[i] - 'a';
        if(p->next[del] == NULL)
            p->next[del] = new Trie_Node();//动态建树，也可以换成静态
        p = p->next[del];
        i++;
    }
    if(p->id == -1)
        p->id = num++;
    return p->id;
}

 

POJ2513

题目大意：有n根筷子(n=250000)，每根筷子两头涂有颜色。现在问能否将所有筷子连起来，并且每两根筷子的连接点颜色都相同。

分析：题意不难理解，现在做一个转换：将每种颜色作为一个结点，每根筷子两头的颜色之间连有一条边。这样，就形成了下面的图：

 

     这样问题就转化为：要求全部走完且经过每条边一次且仅一次，即一笔画问题。 这就成了欧拉路的判断：

1.判断该图是否连通；

2.该图的每个点的度要么全为偶数，要么有且仅有两个度为奇数。

判断图是否是连通图，可以用并查集。计算每个点的度，就是统计单词出现的次数。因此联想到用Trie树统计单词出现的次数，每次将单词在Trie树中查找，若该单词在trie树中第一次出现，则给它一个标号(相当于hash)。

 

POJ3630(1056)

题目大意：给出n个电话号码(n=10000)，每个电话号码长度不超过10。要求是否满足：每个电话号码不能是其它号码的前缀。

分析：在Trie树中放置一个标志位，表示从根节点到该结点是否是已经输入的号码。

bool findAndInsert(char *t)
{
    Trie_Node *p = root;
    int i = 0,del;
    while(t[i] != '\0')
    {
        if(p->exist)
            return true;        //别的字符串是当前字符串的前缀
        del = t[i] - '0';
        if(p->next[del] == NULL)
        {
            p->next[del] = &node[nodeNum];
            nodeNum++;
        }
        p = p->next[del];
        i++;
    }
    for(i = 0; i < 10; i++)      //当前字符串是别的字符串的前缀
    {
        if(p->next[i] != NULL)
            return true;
    }
    p->exist = true;
    return false;
}

 

POJ2001

题目大意：现在人们喜欢用缩写，比如carbon可以缩写为carb，但不能缩写为car。因为有car这个准确的单词。给你n个单词(n=1000)，每个单词长度不超过20。求出每个单词的最短缩写。

分析：在Trie树中加入一个计数器num，表示以这个字符串为前缀的单词有几个。在查询时，根据传入的单词一层层的往下找，找到num=1就说明这个是第一次被使用，停止输出。

#include <iostream>
const int MAX = 1001;
char str[MAX][21];
int nodeNum;

struct Trie_Node
{
    int num;    //to remember how many words can reach here
    Trie_Node *next[26];
    Trie_Node()
    {
        num = 0;
        memset(next,NULL,sizeof(next));
    }
};
Trie_Node node[MAX*10],head;

void insert(char *t)
{
    int i=0,del;
    Trie_Node *p = &head;
    while(t[i] != '\0')
    {
        del = t[i] - 'a';
        if(p->next[del] == NULL)
        {
            p->next[del] = &node[nodeNum];
            nodeNum++;
        }
        p->next[del]->num++;
        p = p->next[del];
        i++;
    }
}

void query(char *t)
{
    int i = 0;
    Trie_Node *p = &head;
    while(t[i] != '\0')
    {
        printf("%c",t[i]);
        p = p->next[t[i]-'a'];
        if(p->num == 1)
            break;
        i++;
    }
    printf("\n");
}

int main()
{
    int i = 0;
    nodeNum = 1;
    while(scanf("%s",str[i]) != EOF)
    {
        insert(str[i]);
        i++;
    }
    for(int j = 0; j < i; j++)
    {
        printf("%s ",str[j]);
        query(str[j]);
    }
    return 0;
}