算法&数据结构系列 — Trie树(字典树)

松鼠的窝

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;
}

字典树数据结构