Trie 字典树

关注
发布于: 2020 年 06 月 06 日
基础理论什么是字典树为了能够快速的找到一个单词，大佬们提出了一个用空间换时间的数据结构用来存储单词。具体表现为
用一颗树来存储单词
多叉树每一条边代表一个字母，
根到叶子表示一个字符串
最后叶子节点可以存频次信息
图解
比如 我们如何存储but 和 cat 两个单词。
首先我们确定每一个节点：里面有isEnd 和一个指向子节点的数组。长为26（26个字母）。对于每一个字母，如果有单词对应这个字母，就存储一个树节点。否则为空。
典型的字典树运用场景﻿
单词推导， 输入you 自动推导youtube，
﻿
代码实现Tried 的存储结构 树结构boolean isEnd()TreeNode[] children // 一个字母表26长度的数组，如果第i位存在字母，则，下一个字母可以为'a'+i;
﻿
Treid 字典树的基本原子操作
构造一个TreeNode 点
public TreeNode() { children = new TreeNode[26];}
判断当前是否包含某这个字母
public boolean containsKey(char ch) { return children[ch - 'a'] != null; }在当前节点 获取char ch，也就是说或者当前节点的字母
public char get(char ch) { return children[ch - 'a']}
在当前节点插入一个node
public void put(char ch, TreeNode node) { children[ch - 'a'] = node; }
将当前点设为终点
public void setEnd() { isEnd = true;}判断当前Node 是不是endpublic boolean isEnd() {return isEnd;}
﻿
Tried树的常用操作
增加单词 见代码
查找单词 见代码
查找满足某一给前缀的所有单词 见代码
﻿
class Trie {
    class TreeNode{
        private boolean isEnd = false;
        private final int R = 26;
        TreeNode[] children;
        public TreeNode() {
            children = new TreeNode[R];
        }
        public TreeNode get(char ch) {
            return children[ch - 'a'];
        }
        public void put(char ch, TreeNode node) {
            children[ch - 'a'] = node;
        }
        public void setEnd() {
            isEnd = true;
        }
        public boolean isEnd() {
            return isEnd;
        }
    }
    private TreeNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TreeNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TreeNode temp = root;
        for (int i = 0; i < word.length() ; i++) {
            char ch = word.charAt(i);
            if (temp.get(ch) == null) {
                TreeNode chNode = new TreeNode();
                temp.put(ch, chNode);
            }
            temp = temp.get(ch);
        }
        temp.setEnd();
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TreeNode temp = root;
        for (int i = 0; i < word.length() ; i++) {
            char ch = word.charAt(i);
            if (temp.get(ch) == null) {
                return false;
            }
            temp = temp.get(ch);
        }
        // 对于 dad 和 daddy 怎么存的 dad 的isEnd 是什么
        // 按照我这种方法dad 的isEnd 是false
        // 那就和下面的寻找前缀没有区别了
        if(temp.isEnd() == true) {
            return true;
        } else {
            return false;
        }
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TreeNode temp = root;
        for (int i = 0; i < prefix.length() ; i++) {
            char ch = prefix.charAt(i);
            if (temp.get(ch) == null) {
                return false;
            }
            temp = temp.get(ch);
        }
        // 对于 dad 和 daddy 怎么存的 dad 的isEnd 是什么
        // 按照我这种方法dad 的isEnd 是false
        return true;
    }
}
思维导图
﻿
发布于: 2020 年 06 月 06 日阅读数: 71
12583

关注
还未添加个人签名 2019.11.29 加入
还未添加个人简介
发布
暂无评论
创作场景

Trie 字典树

基础理论

什么是字典树

图解

典型的字典树运用场景

代码实现

思维导图

12583

评论
