字典树简单知识及类实现

什么是trie树?

◇ trie树是一种用于快速检索的多叉树结构。

◇ 和二叉查找树不同,在trie树中,每个结点上并非存储一个元素。

◇ trie树把要查找的关键词看作一个字符序列。并根据构成关键词字符的先后顺序构造用于检索的树结构。

◇在trie树上进行检索类似于查阅英语词典。

一棵m度的trie树或者为空,或者由m棵m度的trie树构成。

例如,电子英文词典,为了方便用户快速检索英语单词,可以建立一棵trie树。例如词典由下面的单词构成:a、b、c、aa、ab、ac、ba、ca、aba、abc、baa、bab、bac、cab、abba、baba、caba、abaca、caaba

在trie树上进行查找

例如在上面的trie树中查找单词 aba

(1)在trie树上进行检索总是始于根结点。

(2)取得要查找关键词的第一个字母(例如 a ),并根据该字母选择对应的子树并转到该子树继续进行检索。

(3)在相应的子树上,取得要查找关键词的第二个字母(例如 b),并进一步选择对应的子树进行检索。

(4) ...

(5)在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。

有关Trie树:

在trie树中查找一个关键字的时间和树中包含的结点数无关,而取决于组成关键字的字符数。而二叉查找树的查找时间和树中的结点数有关O(log2n)。

如果要查找的关键字可以分解成字符序列且不是很长,利用trie树查找速度优于二叉查找树。如:

若关键字长度最大是5,则利用trie树,利用5次比较可以从265=11881376个可能的关键字中检索出指定的关键字。而利用二叉查找树至少要进行log2265=23.5次比较。

Trie的类实现及解析:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define MAXN 10010
#define RST(N)memset(N, 0, sizeof(N))
using namespace std;

const int char_num = 26;

class Trie {
public:
    Trie();
    int trie_search(const char* word, char* entry) const;
    int insert(const char* word, char* entry);
    int remove(const char* word, char* entry);
protected:
    struct Trie_node {
        char *data;
        Trie_node *branch[char_num];  //指向各個子樹的指針
        Trie_node();
    };
    Trie_node *root;
};

Trie::Trie() : root(NULL) {};

Trie::Trie_node::Trie_node()
{
    data = NULL;
    for(int i=0; i<char_num; i++) branch[i]=NULL;
}

int Trie::trie_search(const char *word, char *entry) const  //检索
{
    int position = 0;
    char char_code;
    Trie_node *location = root;
    while(location != NULL && *word != 0) {
        if(*word>='a' && *word<='z') char_code = *word-'a';
        else if(*word>='A' && *word<='Z') char_code = *word-'A';
        else return 0;    //不合法單詞
        location = location->branch[char_code];
        position++, word++;
    }
    if(location != NULL && location->data != NULL) {
        strcpy(entry, location->data);
        return 1;
    }
    return 0;
}

int Trie::insert(const char *word, char *entry)   //插入
{
    int result = 1, position = 0;
    if(root == NULL) root = new Trie_node;
    char char_code;
    Trie_node *location = root;
    while(location != NULL && *word != 0) {
        if(*word>='a' && *word<='z') char_code = *word-'a';
        else if(*word>='A' && *word<='Z') char_code = *word-'A';
        else return 0;   //不合法單詞
        if(location->branch[char_code] == NULL)
            location->branch[char_code] = new Trie_node;
        location = location->branch[char_code];
        position++, word++;
    }
    if(location->data != NULL) result = 0;
    else {
        location->data = new char(strlen(entry)+1);
        strcpy(location->data, entry);
    }
    return result;
}

int main()
{
    Trie t;
    char entry[100];
    t.insert("a", "DET");           t.insert("abacus","NOUN");
    t.insert("abalone","NOUN");     t.insert("abandon","VERB");
    t.insert("abandoned","ADJ");    t.insert("abashed","ADJ");
    t.insert("abate","VERB");       t.insert("this", "PRON");
    if (t.trie_search("this", entry))
        cout<<"'this' was found. pos: "<<entry<<endl;
    if (t.trie_search("abate", entry))
        cout<<"'abate' is found. pos: "<<entry<<endl;
    if (t.trie_search("baby", entry))
        cout<<"'baby' is found. pos: "<<entry<<endl;
    else
        cout<<"'baby' does not exist at all!"<<endl;
    return 0;
}

时间: 10-12

字典树简单知识及类实现的相关文章

字典树简单运用--》去亿万条城市三字码数据中Check是否存在某个城市三字码

前言:不知不觉来C***P半年了,过得也算是不好不坏.遇到过出问题只会推给开发,一直抱怨却提不出方案的业务:也遇到过大V开头(可以问度娘)的水的冒泡的开发. 有两件小事和大家分享一下: 1)我们组的接口调用某个外部接口,有些条件下该外部接口会直接把exception(堆栈信息,代码物理路径也有..)抛给我们,我邮件给相关的测试和开发, 不出意外,没有回复:后来不知道他们搞什么鬼,想让我们把这个exception也Log下来... 2)说起这个大V开头的,也是我们要调用的某个外部接口的开发.简单描

HDU4825/5536 [01 字典树/简单字典树更新]

Xor Sum Time Limit: 1000 MS Zeus 和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包含了N个正整数,随后 Prometheus 将向 Zeus 发起M次询问,每次询问中包含一个正整数 S ,之后 Zeus 需要在集合当中找出一个正整数 K ,使得 K 与 S 的异或结果最大.Prometheus 为了让 Zeus 看到人类的伟大,随即同意 Zeus 可以向人类求助.你能证明人类的智慧么? Input 输入包含若干组测试数

字符串hash与字典树

title: 字符串hash与字典树 date: 2018-08-01 22:05:29 tags: acm 算法 字符串 概述 这篇主要是关于字符串里的 字符串hash 和 字符串字典树,,两个都是简单的套模板的东西,,,理解基本思想就行了,,,对了,,还有一个字典树的的变形--01字典树: 字符串hash 如何求一个字符串的hash值 字符串hash的作用就是将 字符串有效的转化为一个整数 ,,这个转化过程利用的是一个 hash函数 例如,,我们选hash函数为 \(hash[i]=(has

Phone List(简单的字典树插入操作)

Phone List Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11655    Accepted Submission(s): 3970 Problem Description Given a list of phone numbers, determine if it is consistent in the sense th

HDU 1247 简单字典树

Hat’s Words Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 7359    Accepted Submission(s): 2661 Problem Description A hat’s word is a word in the dictionary that is the concatenation of exactly

/*字典树*/一些简单题

原理很简单,,,,,肯定能看懂,,,我觉得实现费点劲..... 我的模板: #include <iostream> #include<bits/stdc++.h> using namespace std; #define  MAX  26 typedef struct TrieNode { int nCount;  // 该节点前缀 出现的次数 struct TrieNode *next[MAX]; //该节点的后续节点 } TrieNode; TrieNode Memory[10

LA、Remember the Word (字典树, 简单dp)

传送门 题意: 给你一个初始串 S,strlen(s) <= 3e5  然后给你 n 个单词. n <= 4000,  每个单词的长度不超过 100 : 问你这个初始串,分割成若干个单词的连接的方案:(这些单词必须是给定的n个单词中的任意一个,一个单词可以被使用多次.) 解: 将 n 个单词建个字典树: dp[ i ] 表示,S的 0 ~ i - 1 切割成若干个 单词的方案数: 枚举S, 枚举到 当前位置 i: 然后就在字典树找,以 S 的 i + 1 开始的, 能不能找到一个单词与之匹配:

字典树的简单实现

Trie树,又称为字典树,是一种树形结构,是一种哈希树的变种,是一种用于快速检索的多叉树数据结构. 用于保存大量的字符串.它的优点是:利用字符串的公共前缀来节约存储空间. Trie的核心思想是空间换时间.利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的. 它有3个基本性质: 1.根节点不包含字符,除根节点外每一个节点都只包含一个字符. 2.从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串. 3.每个节点的所有子节点包含的字符都不相同. 搜索字典项目的方法为: (1)

hdu1251 简单字典树

之前去省赛打酱油,遇到一题二进制相关的题目,当时都没做出.后来几个学长找规律打表,然后做:老族长说要用到字典树思想. 也应该学习学习字典树.随手拿水题,看题解,看代码,还是懂了字典树: 内存消耗真的大.. #include<stdio.h> #include<stdlib.h> #include<string.h> #define maxn 26//26个字母 struct trie { trie *next[maxn];//向下26个字母扩展 int v;//记录个数