Trie树使用实例
序
本文简单介绍下apache collection4中的PatriciaTrie的使用。
Trie树
Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构。
- 应用 经常被搜索引擎系统用于文本词频统计。同时，它也是很多算法和复杂数据结构的基础，如后缀树，AC自动机等
- 优点 最大限度地减少无谓的字符串比较，查询效率比哈希表高。
- 缺点 如果系统中存在大量字符串且这些字符串基本没有公共前缀，则相应的trie树将非常消耗内存，这也是trie树的一个缺点。
maven
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-collections4</artifactId>
<version>4.1</version>
</dependency>使用
@Test
public void testContains(){
PatriciaTrie<Double> t = new PatriciaTrie<Double>();
t.put("ronak", 100.0);
t.put("ronald", 90.0);
t.put("rat", 50.0);
t.put("robert", 200.0);
t.put("bat", 44.0);
t.put("batman", 440.0);
System.out.println(t.containsKey("ronak"));
System.out.println(t.selectKey("ro"));
System.out.println(t.prefixMap("r"));
System.out.println(t.prefixMap("ro"));
System.out.println(t.prefixMap("ron"));
}输出
true
robert
{rat=50.0, robert=200.0, ronak=100.0, ronald=90.0}
{robert=200.0, ronak=100.0, ronald=90.0}
{ronak=100.0, ronald=90.0}doc
- 数据结构之Trie树
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2017-08-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
