周报

tire tree

2020年3月28日
Trie tree
1、Trie树（字典树）定义：
又称单词查找树，Trie 树，是一种树形结构，是一种哈希树的变种。

2、应用：
典型应用是用于统计，排序和保存大量的字符串。

3、优缺点：
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

4、基本性质：
1）根节点不表示串，除根节点以外的节点都表示串。
2) 字典树用边表示字母。
3）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
4）每个节点的所有子节点包含的字符都不相同，每个节点最多有26个子节点（包含小写字母）。
5) 有相同前缀的单词公用前缀节点。
6) 整棵树的根节点是空的，便于插入和查找。
7) 定义一个变量count表示在此结束的串的个数
  struct node {
      int number=0;//代表以当前字母为结尾的单词在树里面出现了多少次
      bool flag//标记，看是不是最后一个字母
      struct *node next[maxn];     
  };
    void creat() {
      node *root=new node();
      root->flag=0;
      root->number=0;
      memset(root->next,NULL,sizeof(root->next));
  }


  void insert(node *root,char *word) {
      node *location=root;
      while(*word) {
          if(location->next[*word-'a']==NULL) {
              node *tmp=new node();
              tmp->flag=0;
              memset(tmp->next,NULL,sizeof(tmp->next));
              location->next[*word-'a']=tmp;
          }
          location=location->next[*word-'a'];
          location->number++;
          word++;
      }
      location->flag=1;
  }


  int  search(node *root,char *word) {
      node *location = root;
      while(*word&&location) {
          location = location->next[*word-'a'];
          word++;
      }
      if(location && location->flag){
          return location->number;
    }
      else {
          cout<<"error\n";
          return 0;
      }
  }


  void Delete(node *root) {
      for(int i=0;i<26;i++) {
          if(root->next[i]) {
              Delete(root->next[i]);
          }
      }
      delete root;
  }

Views: 68

发表评论