← 返回学习路线

SYSTEM

字典树

Java基础字典树system
src/content/notes/system/字典树.md

字典树

基本介绍

Trie 树,也叫字典树,是一种专门处理字符串匹配的树形结构,用来解决在一组字符串集合中快速查找某个字符串的问题,Trie 树的本质就是利用字符串之间的公共前缀,将重复的前缀合并在一起

  • 根节点不包含任何信息
  • 每个节点表示一个字符串中的字符,从根节点到红色节点的一条路径表示一个字符串
  • 红色节点并不都是叶子节点

注意:要查找的是字符串“he”,从根节点开始,沿着某条路径来匹配,可以匹配成功。但是路径的最后一个节点“e”并不是红色的,也就是说,“he”是某个字符串的前缀子串,但并不能完全匹配任何字符串


实现Trie

通过一个下标与字符一一映射的数组,来存储子节点的指针

时间复杂度是 O(n)(n 表示要查找字符串的长度)

public class Trie {
    private TrieNode root = new TrieNode('/');

    //插入一个字符
    public void insert(char[] chars) {
        TrieNode p = root;
        for (int i = 0; i < chars.length; i++) {
            //获取字符的索引位置
            int index = chars[i] - 'a';
            if (p.children[index] == null) {
                TrieNode node = new TrieNode(chars[i]);
                p.children[index] = node;
            }
            p = p.children[index];
        }
        p.isEndChar = true;
    }

    //查找一个字符串
    public boolean find(char[] chars) {
        TrieNode p = root;
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            if (p.children[index] == null) {
                return false;
            }
            p = p.children[index];
        }
        if (p.isEndChar) {
            //完全匹配
            return true;
        } else {
            // 不能完全匹配,只是前缀
            return false;
        }
    }


    private class TrieNode {
        char data;
        TrieNode[] children = new TrieNode[26];//26个英文字母
        boolean isEndChar = false;//结尾字符为true
        public TrieNode(char data) {
            this.data = data;
        }
    }
}

优化Trie

Trie 树是非常耗内存,采取空间换时间的思路。Trie 树的变体有很多,可以在一定程度上解决内存消耗的问题。比如缩点优化,对只有一个子节点的节点,而且此节点不是一个串的结束节点,可以将此节点与子节点合并

参考文章:https://time.geekbang.org/column/article/72414