时间：2014.04.05
地点：基地
-------------------------------------------------------------
字典树又叫单词查找树，Trie树，是一种哈希树的变种。常用于统计、排序和保持大量字符串之类的等等。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度减少无谓字符串的比较，从而提高查询效率。这使得它在文本词频统计中应用广泛。
字典树和字典很相似，当要在字典中查找一个单词时，首先看单词的第一个字母是不是在字典的第一层，如果不在说明没有，如果在则继续进入第二层查找第二个字母，如此不断递进。类似的道理还可实现类似的用途。
-------------------------------------------------------------
拿词频统计来说，假设我们有很多单词，而且都小写也不重复，现在要统计出某个字符串为前缀的单词量。
常规解法复杂度分析：
假设单词容量为M，给定的前缀长度为L，对于该前缀，我们搜索每个单词，试图看看这个前缀是不是这个单词的前缀，如果是计数器加1，依照这样的算法时间复杂度为O(M*L)，如果单词的容量较大的话这个算法的代价还是很大的。
更好的方法是利用字典树，字典树1.一方面它利用串的公共前缀，节省内存。2.根节点不包含任何字母。3.其余节点仅包含一个字母。4.每个节点的子节点包含的字母各不相同。一个典型的例子如下：
这颗字典树中存储的单词有abc abcd abd b bcd efg hig。也就是说所有标记为红色实心点的才是单词的结尾字母。
-------------------------------------------------------------
1.根节点不包含字符，除根节点外每一个节点都只包含一个字符
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
3.每个节点的所有子节点包含的字符都不相同。
-------------------------------------------------------------
查找、插入、删除。下面是一个简单的字典树实现和应用。
#include<iostream>
#include<string>
#include<vector>
using namespace std;
struct Node
{
bool is_word=false;
Node* p_next[26];
Node()
{
//for (auto p : p_next) //我的问题，如左边注释部分，我起初使用C++11中的范围语句
//p = nullptr; //去初始化指针数组，但没起作用，不晓得怎么回事，求大侠们解答
for (int i = 0; i <= 26; ++i)
p_next[i] = nullptr;
}
};
class TrieTree
{
public:
void Insert(const string& str);
//Postconditon: Put the given string into the trie
bool Search(const string& str) const;
//Postconditon: If the given string is in the trie return ture,else reurn false
private:
Node* root = nullptr;
};
void TrieTree::Insert(const string& str)
{
if (!root)
root = new Node;
Node* current_position = root;
rsize_t index = 0;
for (auto ch : str)
{
index = ch - ‘a‘;
if (current_position->p_next[index] == nullptr)
current_position->p_next[index] = new Node;
current_position = current_position->p_next[index];
}
current_position->is_word = true;
}
bool TrieTree::Search(const string& str) const
{
Node* current_position = root;
for (auto ch : str)
{
size_t index = ch - ‘a‘;
if (current_position->p_next[index] != nullptr)
{
current_position = current_position->p_next[index];
continue;
}
else
return false;
}
return current_position->is_word;
}
int main()
{
vector<string> vec_str;
string str;
cout << "Please input a serial of string which to construct a trie tree" << endl;
while (cin>>str)
vec_str.push_back(str);
TrieTree my_tree;
for (auto str : vec_str)
my_tree.Insert(str);
string search_target;
cout << "Please input a string which you want to search" << endl;
cin.clear();
while (cin >> search_target)
cout << search_target << " is" << (my_tree.Search(search_target) ?" exist" : " not exist" )<< endl;
}
这样的字典树查找树效率很高，时间复杂度为O(n)。但缺点是存在很多空指针，占用存储空间。所以这中方法采取的是空间换时间的思想。1.从根节点开始搜素
2.取得要查找关键字的第一个字母，并根据该字母选择对应的子树并转到该子树上继续进行检索
3.在相应的子树上，取得要查找关键字的第二个字母并进一步选择对应的子树进行检索
4.不断迭代重复上面过程
5.当关键词所以字母已经被取出，结束查找迭代，完成查找。
-------------------------------------------------------------
a.串的快速检索
给出N个单词组成的熟词表以及一篇全用小写英文写得文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
b.串排序
给定N个互不相同的仅由一个单词构成的英文名，要求将它们按字典序从小到大输出。
c.最长公共前缀
对所有串建立字典树，对于两个串的最长公共前缀的长度即她们所在的节点的公共祖先个数，将问题转化为当时公共祖先问题
总结：一方面，虽然字典树存在很多空指针，但字符串的公共前缀会加以利用尽可能减少存储空间。二方面可以最大限度减少无谓的字符串比较，查询效率很高。在大数据两单词中查找一个字符长度为5的单词是否存在我们也只要5次比较操作即可，这是二叉查找所无法比拟的。
字典树（第四节代码实现中有我的一个语法疑惑，忘高手们解惑啊）,布布扣,bubuko.com
字典树（第四节代码实现中有我的一个语法疑惑，忘高手们解惑啊）
原文：http://blog.csdn.net/u012333003/article/details/22995029