松鼠的窝 2018-02-12
字典树
是干嘛用的呢?
for example, Luogu P2580
快速的查找一个字符串有没有出现过,这是trie的本能。
那么,trie是如何工作的呢?请看下图:
这个图可以表示
a
,an
,do
,dog
,zoo
,zed
六个单词
为什么呢?
如果一个节点是黑色,就表示从根目录一直到这个节点的值连起来是存在的单词。
什么意思?比如,g
是黑色,他表示的就是
d
+o
+g
= dog
那为什么点z
的儿子o
不能表示单词zo
呢?
因为他是白色的。。。
very easy,yes?
所以,我们来想一想他的时间&空间复杂度(假设存储的是小写字母)---
时间复杂度:$ O(len Word) $
空间复杂度:$ O(26^{len Word}) $
所以,trie树不但时空复杂度小,还支持精确查找。
#define MAX_NUM 26 enum NODE_TYPE{ COMPLETED, UNCOMPLETED }; struct Node { enum NODE_TYPE type; char ch; struct Node* child[MAX_NUM]; //26-tree->a, b ,c, .....z }; struct Node* ROOT; //tree root struct Node* createNewNode(char ch){ // create a new node struct Node *new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->ch = ch; new_node->type == UNCOMPLETED; int i; for(i = ; i < MAX_NUM; i++) new_node->child[i] = NULL; return new_node; } void initialization() { //intiazation: creat an empty tree, with only a ROOT ROOT = createNewNode(' '); } int charToindex(char ch) { //a "char" maps to an index<br> return ch - 'a'; } int find(const char chars[], int len) { struct Node* ptr = ROOT; int i = ; while(i < len) { if(ptr->child[charToindex(chars[i])] == NULL) { break; } ptr = ptr->child[charToindex(chars[i])]; i++; } return (i == len) && (ptr->type == COMPLETED); } void insert(const char chars[], int len) { struct Node* ptr = ROOT; int i; for(i = ; i < len; i++) { if(ptr->child[charToindex(chars[i])] == NULL) { ptr->child[charToindex(chars[i])] = createNewNode(chars[i]); } ptr = ptr->child[charToindex(chars[i])]; } ptr->type = COMPLETED; }