Trie树

** 1. 什么是Trie树 **

Trie树,也叫字典树,是一种树形结构,常用于统计、排序和保存大量字符串,利用字符串的公共前缀来减少查询时间,以空间换取时间。

** 2. 基本结构 **

Trie树不同于我们常接触到的二叉树,而是N叉树,例如,如果我们要将许多单词(小写)用Trie树来进行保存,那么此时的Trie树为26叉树,因为总共有2
6个小写字母。
例如:
我们要储存inn int ate age adv ant 这五个单词 ,那么所构成的Trie树为下图所示。
这里写图片描述
在Trie树中,每个字符串都被分为单个字符按照顺序逐层标记于树上。
需要说明三点:
<1>根节点只保存子节点地址,不保存数据
<2>每个节点中并不保存当前前缀的字符串,而是在逻辑上,以从根节点到当前节点的路径来表示。
<3>每个节点中都保存一int值,表示树中所有字符串以当前路径为前缀的字符串的数量。
树节点结构体定义如下:

typedef struct Node
{
    int num;               //保存当前路径为前缀的字符串的总数
    struct Node *next[MAX]; //保存子节点的地址。
}

** 3. 基本操作 **

<1> 添加
从根节点开使,获取需要添加的字符串的第一个字符,根据字符值获取next[]数组中相应子树的地址,并进行跳转。如果子树地址为空则需先新建节点,初始化num=1
,并将新建节点的next数组全部置为空。然后跳转。若不为空,将num++;
从当前节点开始,对字符串的第二个字符进行上述操作。

字符串遍历完,此时添加成功
<2> 查找
对需检索的字符串进行类似上述操作,不同的是若在字符串遍历完毕之前,子树地址为空,表示该字符串并不在此树中。
<3> 删除
一般很少使用,过程细节类似于添加操作。不同处为对num进行减操作。

** 4. 性能 **

Trie主要用于查找。
在Trie树中查找一个关键字的时间和树中包含的结点数无关,而取决于组成关键字的字符数。而二叉查找树的查找时间和树中的结点数有关O(log2n)。
如果要查找的关键字可以分解成字符序列且不是很长,利用Trie树查找速度优于二叉查找树。

** 5. 应用例题 **

hihocoder 1014 Trie树
题目大意:
给定词典,对于每个输入的关键字,输出词典中以该关键字为前缀的字符串总数。
输入
输入的第一行为一个正整数n,表示词典的大小,其后n行,每一行一个单词(不保证是英文单词,也有可能是火星文单词哦),单词由不超过10个的小写英文字母组成,可能
存在相同的单词,此时应将其视作不同的单词。接下来的一行为一个正整数m,表示小Hi询问的次数,其后m行,每一行一个字符串,该字符串由不超过10个的小写英文字母
组成,表示小Hi的一个询问。

在20%的数据中n, m<=10,词典的字母表大小<=2.

在60%的数据中n, m<=1000,词典的字母表大小<=5.

在100%的数据中n, m<=100000,词典的字母表大小<=26.

输出
对于小Hi的每一个询问,输出一个整数Ans,表示词典中以小Hi给出的字符串为前缀的单词的个数。

** 6. 代码 **

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

using namespace std;

typedef struct Node
{
    int num;
    struct Node *next[26];
}tree;


void init(tree *t)
{
    for(int i=0;i<26;i++)
    {
        t->next[i] = NULL;
    }
}

void add(tree *t,char s[])
{
    int len = strlen(s);
    for(int k=0; k<len; k++)
    {
        if(t->next[s[k]-'a'] == NULL)
        {
            tree *z = (tree*)malloc(sizeof(tree));
            init(z);
            z->num = 1;
            t->next[s[k]-'a'] = z;
        }
        else
        {
            t->next[s[k]-'a']->num++;
        }
        t=t->next[s[k]-'a'];
    }
}

int find(tree *t, char str[])
{
    int len = strlen(str);
    for(int i=0;i<len;i++)
    {
        if(t->next[str[i]-'a'] == NULL)
            return 0;
        else
        {
            t = t->next[str[i]-'a'];
        }
    }
    return t->num;
}

int main()
{
    int n;
    scanf("%d",&n);
    char str[10];
    tree *root = (tree*)malloc(sizeof(tree));
    init(root);
    while(n--)
    {
        scanf("%s",str);
        add(root, str);
    }
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",str);
        printf("%d\n",find(root, str));
    }
    return 0;
}