文档章节

trie树【简化的】1

大大美女女
 大大美女女
发布于 2013/10/10 17:44
字数 516
阅读 67
收藏 2

Trie

又称单词查找树,Trie,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较。

Trie树最典型直观的应用:


热词提示中的应用

 

现在以只包含小写英文字母的英文单词的trie树做下说明:

        

Trie树的结构:

例如只有四个字符串:

abc  d  da  dda

则结构为:


 

 

Trie树的时空复杂度:

 

查找和插入的时间复杂度均为o(n), n为字符个数,假设只有26个小写英文字母, n26,如果为2000个汉字,n2000

 

 

Trie树的空间复杂度:

空间复杂度较高,是一个典型的空间换时间的结构,假设每个词平均长度为5,则空间复杂度为n^5

 

 上代码:此代码只处理包含26个小写英文字符情况:

#ifndef _TRIE_H_
#define _TRIE_H_


#include <string.h>
#include <iostream>

using namespace std;

const int kMaxBranchSize = 26;

struct TrieNode {
  bool is_word;
  TrieNode* next[kMaxBranchSize];
  TrieNode() : is_word(false) {
    for (int i = 0; i < kMaxBranchSize; i++) {
      next[i] = NULL;
    }
  }
};



class Trie {
  public:
    Trie() {
      root_ = new TrieNode();
    }

    ~Trie() {
      DeleteTrie(root_);
    }
  public:
    void DeleteTrie(TrieNode* root) {
      for (int i = 0; i < kMaxBranchSize; i++) {
        if (root->next[i] != NULL) {
          DeleteTrie(root->next[i]);
        }
      }
      if (root != NULL) {
        delete root;
        root = NULL;
      }
    }

    int Insert(const char* word) {
      if (NULL == word) {
        return -1;
      }
      TrieNode* now_node = root_;
      if (now_node == NULL) {
        return -2;
      }
      while (*word) {
        if (now_node->next[*word-'a'] == NULL) {
          TrieNode* tmp = new TrieNode();
          now_node->next[*word-'a'] = tmp;
        }
        now_node = now_node->next[*word-'a'];
        word++;
      }
      now_node->is_word = true;
      return 0;
    }

    int Search(const char* word) {
      if (NULL == word) {
        return -1;
      }
      TrieNode* node = root_;
      if (node == NULL) {
        return -2;
      }
      while (*word&&node != NULL) {
        node = node->next[*word - 'a'];
        word++;
      }

      if (node != NULL && node->is_word) {
        return 1;
      }

      return 0;

    }

  private:
    Trie(const Trie&);
    Trie& operator= (const Trie&);
  private:
    TrieNode* root_;

};


#endif

有趣有爱有价值:http://www.qihu100.com

 

#include "trie.h"

int main(int argc, char* argv[]) {
  Trie t;
  t.Insert("a");         
  t.Insert("ab");
  char * c = "abc";
  t.Insert(c);
  t.Insert("cba");
  if (t.Search("cba")) {
    cout<< "hehe" << endl; 
  }
  if (t.Search("cbad")) {
    cout<< "haha" << endl; 
  }
}

© 著作权归作者所有

共有 人打赏支持
大大美女女
粉丝 18
博文 60
码字总数 24479
作品 0
昌平
程序员
私信 提问
树结构—Trie树

很有段时间没写此系列了,今天我们来说Trie树,Trie树的名字有很多,比如字典树,前缀树等等。 一:概念 下面我们有and,as,at,cn,com这些关键词,那么如何构建trie树呢? 从上面的图中,我们...

亚特兰缇斯
2015/09/08
196
0
可持久化 trie 的简单入门

可持久化 $trie$ ....又是一个表里不一的东西..... 可持久化 $trie$ 的介绍: 和主席树类似的,其实可持久化就是体现在前缀信息的维护上(搞不懂这怎么就叫做可持久化了...) $trie$ (字典树...

Judge_Cheung
08/18
0
0
Trie 树实现与应用

Trie树 基本概念  Trie树又称字典树,它是用来查询字符串的一种数据结构。它每一个节点都有26个子节点,所以是26叉树。优点查询字符串的时候速度快,缺点浪费大量空间。  当一个字符串长为...

sdoyuxuan
01/24
0
0
“1000万字符串,去掉重复”的一些思考和java实现

题目:1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串。请怎么设计和实现? 大数据的字符串处理我一般想到了trie树和hashmap,jdk里有hashmap的实现,所以想先...

努力的C
2017/10/10
0
0
非法词判断

一个大文件,里面存储了一批非法词,每行一个词。 需求是,我随便给你一句话,能快速的判断出这句话是否包含了非法词,具体哪些非法词? 第一个关注点->算法 //////////////////////////////...

小矩阵
2015/11/24
27
0

没有更多内容

加载失败,请刷新页面

加载更多

Function函数式接口

Function函数式接口传入一个参数,返回一个值。 然后我们使用这个写个demo看看: 输出: 接口内部还有两个default方法和一个static方法,然后我们先看一下static方法 返回一个始终返回其输入...

woshixin
9分钟前
0
0
开发者和架构师之间最大的区别是什么?

1、开发者和架构师之间最大的区别是什么? 架构师和开发者一样,也经常写代码,简单的说,开发者和架构师之间最大的区别就是技术领导力。 软件架构师的角色需要理解最重要的架构驱动力是什么...

James-
40分钟前
1
0
java框架学习日志-4

补充一些spring配置文件的方法。 设置别名: <!--通过name直接设置别名--> <bean name="user2" class="cn.sxt.factory.UserDynamicFactory"> </bean> <!--有id的情况下也可以设置......

白话
42分钟前
2
0
20181213 上课截图

小丑鱼00
59分钟前
1
0
nginx+php-fpm配置后页面显示空白的解决方法以及用nginx和php-fpm解决“502 Bad Gateway”问题

https://stackoverflow.com/questions/15423500/nginx-showing-blank-php-pages For reference, I am attaching my location block for catching files with the .php extension: location ~......

Yao--靠自己
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部