Trie树
又称单词查找树，，是一种，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约，最大限度地减少无谓的字符串比较。
Trie树最典型直观的应用：
热词提示中的应用
现在以只包含小写英文字母的英文单词的trie树做下说明：
Trie树的结构：
例如只有四个字符串：
abc d da dda
则结构为：
Trie树的时空复杂度：
查找和插入的时间复杂度均为o(n), n为字符个数，假设只有26个小写英文字母， n为26，如果为2000个汉字，n为2000
Trie树的空间复杂度：
空间复杂度较高，是一个典型的空间换时间的结构，假设每个词平均长度为5，则空间复杂度为n^5
上代码：此代码只处理包含26个小写英文字符情况：
#ifndef _TRIE_H_#define _TRIE_H_#include#include 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
有趣有爱有价值:
#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; }}