Trie树
概述
在Google中随意搜索，如下所示：
他会自动显示相关的搜索，不知道有没有想过这个功能是如何实现的呢？面对海量的数据，它怎么能在我输入的同时，如此快速的检索到相关内容呢？当我查找资料后，就遇到了它，Trie树。
What？
Trie树是个什么玩意呢？为啥他能快速进行检索？Trie树也叫字典树。因为它的结构和我们用到的字典基本差不多。
想想，你在字典中差“how”这个单词的动作是怎样的？先找到h，然后在h的基础上找o，再找w。用树来存储这个过程就是这样的：
没毛病。如果存储：how, hello, kan, know这几个单词，如下所示：
简单易懂。在其中查找字符，就跟查字典一样，一级一级往下找就行了。
比如查找单词，“ho”，当找到o时，发现o不是叶子节点，说明“ho”是某个单词的前缀，并不是完整的单词。
看到有人拿Trie树和红黑树、哈希表做对比，红黑树我还没整明白，但是哈希表我知道啊。这俩有可比性么？我觉得没有，完全就是两种数据结构，打眼一看，就知道他们的侧重点不同。很明显Trie树适合进行前缀匹配，而哈希表适合进行精确匹配啊。哦，还有一个，哈希表很多语言都有现成的实现，如HashMap，但Trie树貌似没有。
How
Trie树看着挺厉害的。那如何实现呢？刚才说了，哈希表很多有现成的实现，但Trie树没有，所以要想使用，就得自己来实现。
Trie树说到底还是树结构。其结构体如下：
struct TrieNode{ char data; // 保存字符 TrieNode children[26]; // 子节点}使用Python写一个简单实现，其他语言也大同小异吧。都需要实现什么功能呢？
- 将字符串加入
- 匹配字符串
class Trie:
class TrieNode: """ 树的节点 """ def __init__(self, data): self.data = data self.children = {}
def __init__(self): self.root = self.TrieNode(None)
def insert_str(self, string): """ 讲字符串添加进trie树中 :param string: 字符串 """ tmp_trie_node = self.root for c in list(string): # 这里使用字母的顺序作为key，方便查找 index = ord(c) - ord('a') if not tmp_trie_node.children.get(index): tmp_trie_node.children[index] = self.TrieNode(c) tmp_trie_node = tmp_trie_node.children[index]
def is_match_str(self, string): """ 查询字符串是否在树中 :param string: :return: """ tmp_trie_node = self.root for c in list(string): index = ord(c) - ord('a') if not tmp_trie_node.children.get(index): return False tmp_trie_node = tmp_trie_node.children[index] return True
if __name__ == '__main__': trie = Trie() for string in ['how', 'hello', 'kan', 'know']: trie.insert_str(string) print(trie.is_match_str('hello')) print(trie.is_match_str('hess'))很简单的一个小demo
可以看的出来，Trie树在构建的时候，需要扫描所有字符串，但是在查找的时候就很快速了。
why
说了半天，Trie树算是简单的说完了。回到开篇的问题上，使用Trie树是如何进行搜索的？
比如我们输入“h”，就可以把“h”为前缀的单词展示出来，再输入“he”，就把“he”为前缀的单词展示出来。
输入单词后，展示相关的搜索句子，也是同样的道理。当然，搜索引擎会对其进行优化，比如匹配的相关内容有很多，从中选择哪些？等等。以上只是一个雏形的雏形。
Trie树不光可以用在搜索上，类似的场景有很多，比如输入法的自动补全、IDE的自动补全等等。怎么都是自动补全，应该还是有其他场景的，只是我只想到了这些。