首页 > 代码库 > 字典树简单知识及类实现
字典树简单知识及类实现
什么是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)在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。
(1)在trie树上进行检索总是始于根结点。
(2)取得要查找关键词的第一个字母(例如 a ),并根据该字母选择对应的子树并转到该子树继续进行检索。
(3)在相应的子树上,取得要查找关键词的第二个字母(例如 b),并进一步选择对应的子树进行检索。
(4) ...
(5)在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。
有关Trie树:
在trie树中查找一个关键字的时间和树中包含的结点数无关,而取决于组成关键字的字符数。而二叉查找树的查找时间和树中的结点数有关O(log2n)。
如果要查找的关键字可以分解成字符序列且不是很长,利用trie树查找速度优于二叉查找树。如:
若关键字长度最大是5,则利用trie树,利用5次比较可以从265=11881376个可能的关键字中检索出指定的关键字。而利用二叉查找树至少要进行log2265=23.5次比较。
若关键字长度最大是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 = http://www.mamicode.com/NULL;>
字典树简单知识及类实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。