Trie(prefixtree)实现(Java)

转自出处

关注Trie 这种结构已经很久&＃xff0c;Trie有一个很有趣的用途&＃xff0c;那就是自动提示。而且&＃xff0c;前不久在一次面试里&＃xff0c;也需要用Trie来解答。所以&＃xff0c;在此对这个数据结构进行总结。

Trie&＃xff0c;又称单词查找树或键树&＃xff0c;是一种树形结构。典型应用是用于统计和排序大量的字符串&＃xff08;但不仅限于字符串&＃xff09;&＃xff0c;所以经常被搜索引擎系统用于文本词频统计。它的优点是&＃xff1a;最大限度地减少无谓的字符串比较&＃xff0c;查询效率比哈希表高。

它有3个基本性质&＃xff1a;

1. 根节点不包含字符&＃xff0c;除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点&＃xff0c;路径上经过的字符连接起来&＃xff0c;为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

有了这样一种数据结构&＃xff0c;我们可以用它来保存一个字典&＃xff0c;要查询改字典里是否有相应的词&＃xff0c;是否非常的方便呢&＃xff1f;我们也可以做智能提示&＃xff0c;我们把用户已经搜索的词存在Trie里&＃xff0c;每当用户输入一个词的时候&＃xff0c;我们可以自动提示&＃xff0c;比如当用户输入 ba, 我们会自动提示 bat 和 baii.

现在来讨论Trie的实现。

首先&＃xff0c;我们定义一个Abstract Trie,Trie 里存放的是一个Node。这个类里有两个操作&＃xff0c;一个是插入&＃xff0c;另一个是查询。具体实现放在后面。

关注Trie 这种结构已经很久&＃xff0c;Trie有一个很有趣的用途&＃xff0c;那就是自动提示。而且&＃xff0c;前不久在一次面试里&＃xff0c;也需要用Trie来解答。所以&＃xff0c;在此对这个数据结构进行总结。Trie&＃xff0c;又称单词查找树或键树&＃xff0c;是一种树形结构。典型应用是用于统计和排序大量的字符串&＃xff08;但不仅限于字符串&＃xff09;&＃xff0c;所以经常被搜索引擎系统用于文本词频统计。它的优点是&＃xff1a;最大限度地减少无谓的字符串比较&＃xff0c;查询效率比哈希表高。它有3个基本性质&＃xff1a;根节点不包含字符&＃xff0c;除根节点外每一个节点都只包含一个字符。从根节点到某一节点&＃xff0c;路径上经过的字符连接起来&＃xff0c;为该节点对应的字符串。每个节点的所有子节点包含的字符都不相同。下面这个图就是Trie的表示&＃xff0c;每一条边表示一个字符&＃xff0c;如果结束&＃xff0c;就用星号表示。在这个Trie结构里&＃xff0c;我们有下面字符串&＃xff0c;比如do, dork, dorm等&＃xff0c;但是Trie里没有ba, 也没有sen&＃xff0c;因为在a, 和n结尾&＃xff0c;没有结束符号&＃xff08;星号&＃xff09;。有了这样一种数据结构&＃xff0c;我们可以用它来保存一个字典&＃xff0c;要查询改字典里是否有相应的词&＃xff0c;是否非常的方便呢&＃xff1f;我们也可以做智能提示&＃xff0c;我们把用户已经搜索的词存在Trie里&＃xff0c;每当用户输入一个词的时候&＃xff0c;我们可以自动提示&＃xff0c;比如当用户输入 ba, 我们会自动提示 bat 和 baii.现在来讨论Trie的实现。首先&＃xff0c;我们定义一个Abstract Trie,Trie 里存放的是一个Node。这个类里有两个操作&＃xff0c;一个是插入&＃xff0c;另一个是查询。具体实现放在后面。Node 类的实现
[java] view plaincopyclass Node { char content; // the character in the node boolean isEnd; // whether the end of the words int count; // the number of words sharing this character LinkedList childList; // the child list public Node(char c){ childList &＃61; new LinkedList(); isEnd &＃61; false; content &＃61; c; count &＃61; 0; } public Node subNode(char c){ if(childList !&＃61; null){ for(Node eachChild : childList){ if(eachChild.content &＃61;&＃61; c){ return eachChild; } } } return null; } } 现在我们来看这个Trie类的具体实现。[java] view plaincopypublic class Trie{ private Node root; public Trie(){ root &＃61; new Node(&＃39; &＃39;); } public void insert(String word){ if(search(word) &＃61;&＃61; true) return; Node current &＃61; root; for(int i &＃61; 0; i


时间复杂度分析&＃xff1a;