【数据结构】Trie树

发布时间:2017-7-1 11:42:02编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"【数据结构】Trie树 ",主要涉及到【数据结构】Trie树 方面的内容,对于【数据结构】Trie树 感兴趣的同学可以参考一下。

数据结构——Trie树

概念

Trie树,又称字典树、前缀树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

Trie树的结构如下图所示:

Trie树中的节点数据结构如下:

  • 当前字符
  • 子节点数组(如果全为小写字母的话,子节点数量固定为26个,根据字符来确定在数组中的位置,如'a'的下标为0,'z'为25)
  • 是否为一个单词的结尾(标红的节点)
  • 出现次数

特点:root节点不存储字符。

代码实现

public class Trie {    private Node root;    class Node{        int count;        char ch;        Node[] child;        boolean isEnd;        public Node() {            this.count = 1;            this.child = new Node[26];            this.isEnd = false;        }    }    /** Initialize your data structure here. */    public Trie() {        this.root = new Node();    }    /** Inserts a word into the trie. */    public void insert(String word) {        if (null == word || "".equals(word)) return;        if (this.search(word)) return;        Node cur = this.root;        char[] chars = word.toCharArray();        for(char c : chars) {            //根据字符找到在子节点数组中的下标            int pos = c - 'a';            Node child = cur.child[pos];            //如果子节点没有被初始化过则初始化,并设置其字符            if (child == null) {                cur.child[pos] = new Node();                cur.child[pos].ch = c;            }            cur.count++;            //更新cur节点为子节点,向下递归            cur = cur.child[pos];        }        //最后一个字符的节点        cur.isEnd = true;    }    /** Returns if the word is in the trie. */    public boolean search(String word) {        if (null == word || "".equals(word)) return true;        Node cur = this.root;        char[] chars = word.toCharArray();        for (char c : chars) {            int pos = c - 'a';            Node node = cur.child[pos];            if (node == null) return false;            cur = node;        }        return cur.isEnd;    }    /** Returns if there is any word in the trie that starts with the given prefix. */    public boolean startsWith(String prefix) {        if (null == prefix || "".equals(prefix)) return true;        Node cur = this.root;        char[] chars = prefix.toCharArray();        for (char c : chars) {            int pos = c - 'a';            Node node = cur.child[pos];            if (node == null) return false;            cur = node;        }        return cur.count > 0;    }    public static void main(String[] args) {        Trie trie = new Trie();        trie.insert("a");        trie.insert("adc");        trie.insert("aer");        System.out.println(trie.search("a"));        System.out.println(trie.startsWith("a"));    }}

结果:

208. Implement Trie (Prefix Tree)

超过94%,感觉还不错~


上一篇:Visual Studio 32位64位的问题和如何编译32位64位工程的问题
下一篇:Git进阶用法

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款