• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(9.3)Trie字典树的查询

极客笔记 Geekerstar 11个月前 (05-20) 369次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

如何从Trie中查询单词

// 查询单词word是否在Trie中
public boolean contains(String word){

    Node cur = root;
    for(int i = 0 ; i < word.length() ; i ++){
        char c = word.charAt(i);
        if(cur.next.get(c) == null)
            return false;
        cur = cur.next.get(c);
    }
    return cur.isWord;
}

我们简单的在main函数中测试一下

import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {

        System.out.println("Pride and Prejudice");

        ArrayList<String> words = new ArrayList<>();
        if(FileOperation.readFile("pride-and-prejudice.txt", words)){

            long startTime = System.nanoTime();

            BSTSet<String> set = new BSTSet<>();
            for(String word: words)
                set.add(word);

            for(String word: words)
                set.contains(word);

            long endTime = System.nanoTime();

            double time = (endTime - startTime) / 1000000000.0;

            System.out.println("Total different words: " + set.getSize());
            System.out.println("BSTSet: " + time + " s");

            // ---

            startTime = System.nanoTime();

            Trie trie = new Trie();
            for(String word: words)
                trie.add(word);

            for(String word: words)
                trie.contains(word);

            endTime = System.nanoTime();

            time = (endTime - startTime) / 1000000000.0;

            System.out.println("Total different words: " + trie.getSize());
            System.out.println("Trie: " + time + " s");
        }
    }
}

我们还是用以前的例子,测试傲慢与偏见这本书,可以看出用BSTSet是0.2秒,而Trie是0.17秒。

时间性能上,对于这个用例Trie是略高于BSTSet的。对于Trie来说,承载的元素越多,性能就越明显。

核心原因就是对于Trie来说无论是添加操作还是查找操作和集合中有多少个元素字符串是没有关系的,只和添加或查找的那个字符串长度有关。

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(9.3)Trie字典树的查询
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00