字典树Trie

字典树，又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。关于 Trie 的概念，请看维基百科-Trie，也可以参考百度百科-字典树。

一、典型结构

Trie是一棵字典树，典型的如下图：

二、主要性质

它有3个基本性质：

根节点不包含字符，除根节点外每一个节点都只包含一个字符；

从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；

每个节点的所有子节点包含的字符都不相同。

三、应用

串的快速检索

最长公共前缀

四、实现

搜索字典树的方法为：

(1) 从根结点开始一次搜索；

(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索，同时把关键词的第二个字母作为首位置；

(3) 递归（2）操作。直到在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。

插入和删除跟查找思路类似。

例：限定输入仅包括小写字母a-z，设计实现一个Trie

分析：由于限定了输入仅包括小写字母a-z，因此可以用0-25来简单映射a-z，维护一个数组nodes[26]来存储后继结点的指针，这就解决了第一个问题；另外给每个结点一个isLast的属性，当其为true时表示到此为止的单词存在于字典中，相反如果为false，表示这个结点仅仅是某个单词的前缀部分中的一个字符。

代码实现：

##Definition for a Trietree node.class TrieNode: def __init__(self): self.nodes = [None]*26 self.isLast = Falseclass Trie: def __init__(self): """ Initialize your data structure here. """ self.root=TrieNode() def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: void """ tmp=self.root while len(word): c=word[0] word=word[1:] if tmp.nodes[ord(c)-ord('a')]==None: tmp.nodes[ord(c)-ord('a')]=TrieNode() tmp=tmp.nodes[ord(c)-ord('a')] tmp.isLast = True def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ if word=='': return True tmp=self.root while len(word): c=word[0] if tmp.nodes[ord(c)-ord('a')]!=None: tmp=tmp.nodes[ord(c)-ord('a')] word=word[1:] else: return False return tmp.isLast def startsWith(self, prefix): """ Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """ if prefix=='': return True tmp=self.root while len(prefix): c=prefix[0] if tmp.nodes[ord(c)-ord('a')]!=None: tmp=tmp.nodes[ord(c)-ord('a')] prefix=prefix[1:] else: return False return True

python学习课程目录