当前位置:   article > 正文

字典树/前缀树Trie(附Java代码)_java 字典树

java 字典树

在计算机科学中,trie,又称前缀树字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。Trie这个术语来自于retrieval(检索)。根据词源学,trie的发明者Edward Fredkin把它读作/ˈtriː/ “tree”。但是,其他作者把它读作/ˈtraɪ/ “try”。
trie中的通常是字符串,但也可以是其它的结构。trie的算法可以很容易地修改为处理其它结构的有序序列,比如一串数字或者形状的排列。比如,bitwise trie中的键是一串比特,可以用于表示整数或者内存地址。

1.字典树Trie

  • 只有一个根节点,且根节点本身不存储任何键数据;
  • 每个节点拥有不确定数目的孩子节点,具体取决于由该节点可以发散出多少分支,比如a开头的单词都可以从a出发,也就是作为a的子孙节点;
  • 当从根节点到当前节点的路径所构成的单词为合法单词,则需进行如下工作:1)标记当前节点为“终止”节点,表示根节点到此节点可表示一个完整单词,该节点并不一定是叶子结点,也有可能为内部节点,比如app和apple在字典树中的体现;2)将完整单词记录在当前节点中;
  • 字典树常用于解决字符串前缀匹配问题、词频统计问题;

1.1 字典树举例

比如有四个单词:app、apple、bit、cat,根据他们构建字典树如下:
在这里插入图片描述

2.代码实现

力扣208. 实现 Trie (前缀树)
Trie(发音类似 “try”)或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。请你实现 Trie 类:

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false 。

2.0 代码结构

Trie代码实现中主要涉及四个内容:

  • root节点,本身不存储任何内容,拥有孩子节点;
  • 孩子节点可能有多个,可使用数组(明确孩子节点的数量)或哈希表(孩子节点的数量未知)进行存储,孩子节点本身也是一个Trie树,与root节点不同的是,该节点存储对应的键值;
  • 如果到达某个节点时,可表示一个完整的合法单词,则将其标记为“终止”节点,用于字典树查找操作;
  • 也可在终结节点处记录完整单词的内容;

2.1方式一:使用数组存储孩子节点

  • 此处假设所有单词只有小写字母组成,所以每个节点的孩子节点数目最多为26个(其实有些浪费空间);
  • 在如上假设下,某个节点的孩子节点中,children[ch-‘a’]则表示以当前字符ch为键的孩子节点;
    class Trie {
    	// 存储孩子节点
        Trie[] children;
        // 标记该节点是否为终止节点
        boolean isEnd;
        public Trie() {
        	// 初始化
            children=new Trie[26];
        }

		// 数据插入操作
        public void insert(String word) {
            // 当前根节点
            Trie cur=this;
            // 当前根节点的孩子节点
            Trie[] branches=cur.children;
            char[] chs=word.toCharArray();
            // 依次遍历当前单词的所有字符
            for(int i=0;i<chs.length;i++){
//                int index=chs[i]-'a';
//                if(branches[index]!=null){
//                    cur=branches[index];
//                    branches=cur.children;
//                }else{                // 说明该字符已经存在
//                    branches[index]=new Trie();
//                    cur=branches[index];
//                    branches=cur.children;
//                }
				// 确定孩子节点的位置
                int index=chs[i]-'a';
                // 说明该字符不存在,则对该孩子节点进行初始化
                if(branches[index]==null){
                    branches[index]=new Trie();
                }
                // 调整当前根节点为该孩子节点
                cur=branches[index];
                branches=cur.children;
            }
            // 单词遍历结束,此时cur指向该单词最后一个字符所在节点,将其标记为终止节点
            cur.isEnd=true;
        }
		
		// 
        public boolean search(String word) {
            // 当前根节点
            Trie cur=this;
            Trie[] branches=children;
            char[] chs=word.toCharArray();
            for(int i=0;i<chs.length;i++){
                int index=chs[i]-'a';
				// 如果该字符存在,则一直向下搜索,直到遍历完整个单词
                if(branches[index]!=null){
                    cur=branches[index];
                    branches=cur.children;
                }else{ // 说明该字符不存在
                    return false;
                }
            }
            // 此时cur指向单词的最后一个字符对应的节点,如果该节点是终止节点则说明该单词存在
            return cur.isEnd;
        }

        public boolean startsWith(String prefix) {
            // 当前根节点
            Trie cur=this;
            Trie[] branches=cur.children;
            char[] chs=prefix.toCharArray();
            for(int i=0;i<chs.length;i++){
                int index=chs[i]-'a';
                // 说明该字符已经存在
                if(branches[index]!=null){
                    cur=branches[index];
                    branches=cur.children;
                }else{
                    return false;
                }
            }
            // 此时cur指向单词的最后一个字符对应的节点,说明整个字符串都存在,也就是以该字符串开头的单词都存在
            return true;
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81

2.2方式二:使用HashMap存储孩子节点

class Trie {
        HashMap<Character,Trie> children;
        boolean isEnd;
        String value;
        public Trie() {
            children=new HashMap<>();
        }

        public void insert(String word) {
            Trie cur=this;
            HashMap<Character,Trie> branches=cur.children;
            char[] chs=word.toCharArray();
            for(int i=0;i<chs.length;i++){
                if(!branches.containsKey(chs[i])){
                    branches.put(chs[i],new Trie());
                }
                cur=branches.get(chs[i]);
                branches=cur.children;
            }
            cur.isEnd=true;
            cur.value=word;
        }

        public boolean search(String word) {
            Trie cur=this;
            HashMap<Character,Trie> branches=cur.children;
            char[] chs=word.toCharArray();
            for(int i=0;i<chs.length;i++){
                if(branches.containsKey(chs[i])){
                    cur=branches.get(chs[i]);
                    branches=cur.children;
                }else{
                    return false;
                }
            }
            return cur.isEnd;
        }

        public boolean startsWith(String prefix) {
            Trie cur=this;
            HashMap<Character,Trie> branches=cur.children;
            char[] chs=prefix.toCharArray();
            for(int i=0;i<chs.length;i++){
                if(branches.containsKey(chs[i])){
                    cur=branches.get(chs[i]);
                    branches=cur.children;
                }else{
                    return false;
                }
            }
            return true;
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53

参考资料:

  • 爱学习的饲养员;
  • 维基百科;
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/码创造者/article/detail/994777
推荐阅读
相关标签
  

闽ICP备14008679号