trie树【简化的】1
trie树【简化的】1
大大美女女 发表于4年前
trie树【简化的】1
  • 发表于 4年前
  • 阅读 62
  • 收藏 2
  • 点赞 0
  • 评论 0

【腾讯云】如何购买服务器最划算?>>>   

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; 
  }
}
标签: trie树 字典树
共有 人打赏支持
粉丝 18
博文 60
码字总数 24479
×
大大美女女
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: