底层实现数据结构:字典树(前缀树) - Cache One

目录



整体结构思维导图


在这里插入图片描述
-------------------------------------------------------------------------------- 回到目录

字典树的应用


典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串)。

它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

字典树图示:
在这里插入图片描述

与普通树的比较:
在这里插入图片描述

-------------------------------------------------------------------------------- 回到目录

源码详解


存储结构

  • path 为经过这个结点的字母的次数。
  • end 为统计以这个结点结尾的字符串的数量。
  • next 为儿子结点,之所以用数组来存储是因为字母分大小写字母,若只有小写字母,就开辟26个空间,若还包含大写则开52个空间。
    该数组存储整数来表示字符,比如存c,则字符的整数转换法:c - ‘a’
public class Trie {

    private class Node{
        public int path;
        public int end;
        public Node[] next;	

        public Node() {
            path = 0;
            end = 0;
            next = new Node[26];
        }
    }

    private Node root;

    public Trie() {
        root = new Node();
    }
}

path 和 end 图示:
在这里插入图片描述
上面这棵树包含的字符串有:
cat、dog、deer、pan、panda
-------------------------------------------------------------------------------- 回到目录

字符串的插入

  • 对字符串遍历每个字符,算出每个字符对应整数的值(每个字符固定对应一个数字),这个值为数组的索引。
  • 若没有该字符则新建一个节点存放。对每个字符,节点的 path 都要 + 1。
  • 若遍历完了一个完整的字符串,则让 end + 1。
    public void insert(String word){
        if(word == null)
            return ;
            
        Node cur = root;
        int index = 0;
        for(int i = 0; i < word.length(); i++){
            index = word.charAt(i) - 'a';
            if(cur.next[index] == null){
                cur.next[index] = new Node();
            }
            cur = cur.next[index];
            cur.path++; 
        }
        cur.end++;
    }

-------------------------------------------------------------------------------- 回到目录

字符串的删除

  • 如果 path 是1,直接删除完后面的节点。
  • 否则将结点的 path-- 就行。
  public void remove(String word){
        if(word == null)
            return;
        if(!search(word)) //不包含这个字符串
            return;
            
        Node cur = root;
        int index = 0;
        for(int i = 0; i < word.length(); i++){
            index = word.charAt(i) - 'a';
            if(cur.next[index].path-- == 0){
                cur.next[index] = null; //释放掉下面的这棵树
                return ;
            }
            cur = cur.next[index];
        }
        cur.end--; //最后这个字符串也要--
    }

-------------------------------------------------------------------------------- 回到目录

查询字符串

  • 查找过程中如果树里没有当前字符,则直接返回0,否则返回 end 。
    在这里插入图片描述
    比如要查找是否有 dear,因为前缀 de 相同,所以查找路线是 “deer”的那条路径,当查找到 ‘a’ 时,因为路径没有‘a’,所以直接返回0表示不存在 dear 这个字符串。
	//统计某个字符串的数量
    public int count(String word){
        if(word == null)
            return 0;
            
        Node cur = root;
        int index = 0;
        for(int i = 0; i < word.length(); i++){
            index = word.charAt(i) - 'a';
            if(cur.next[index] == null)
                return 0;
            cur = cur.next[index];
        }
        return cur.end;
    }

	//查询是否有某个字符串
    public boolean search(String word){
        return count(word) > 0;
    }

-------------------------------------------------------------------------------- 回到目录

查询前缀

  • 返回 path,因为 path 记录的是在添加字符串的时候,每个字符经过的次数。
	//统计以某个字符串为前缀的字符串数量
    public int prefixNum(String prefix){
        if(prefix == null)
            return 0;
            
        Node cur = root;
        int index = 0;
        for(int i = 0; i < prefix.length(); i++){
            index = prefix.charAt(i) - 'a';
            if(cur.next[index] == null)
                return 0;
            cur = cur.next[index];
        }
        return cur.path; 
    }
    
	//是否有某个前缀(以某个字符串开头)
    public boolean startsWith(String prefix){
        return prefixNum(prefix) > 0;
    }

-------------------------------------------------------------------------------- 回到目录

完整源码



public class Trie {

    private class Node{
        public int path;
        public int end;
        public Node[] next;	

        public Node() {
            path = 0;
            end = 0;
            next = new Node[26];
        }
    }

    private Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String word){
        if(word == null)
            return ;
            
        Node cur = root;
        int index = 0;
        for(int i = 0; i < word.length(); i++){
            index = word.charAt(i) - 'a';
            if(cur.next[index] == null){
                cur.next[index] = new Node();
            }
            cur = cur.next[index];
            cur.path++; 
        }
        cur.end++;
    }

    public void remove(String word){
        if(word == null)
            return;
        if(!search(word)) //不包含这个字符串
            return;
            
        Node cur = root;
        int index = 0;
        for(int i = 0; i < word.length(); i++){
            index = word.charAt(i) - 'a';
            if(cur.next[index].path-- == 0){
                cur.next[index] = null; //释放掉下面的这棵树
                return ;
            }
            cur = cur.next[index];
        }
        cur.end--; //最后这个字符串也要--
    }

    public int count(String word){
        if(word == null)
            return 0;
            
        Node cur = root;
        int index = 0;
        for(int i = 0; i < word.length(); i++){
            index = word.charAt(i) - 'a';
            if(cur.next[index] == null)
                return 0;
            cur = cur.next[index];
        }
        return cur.end;
    }

	//查询是否有某个字符串
    public boolean search(String word){
        return count(word) > 0;
    }

	//统计以某个字符串为前缀的字符串数量
    public int prefixNum(String prefix){
        if(prefix == null)
            return 0;
            
        Node cur = root;
        int index = 0;
        for(int i = 0; i < prefix.length(); i++){
            index = prefix.charAt(i) - 'a';
            if(cur.next[index] == null)
                return 0;
            cur = cur.next[index];
        }
        return cur.path; 
    }
    
	//是否有某个前缀(以某个字符串开头)
    public boolean startsWith(String prefix){
        return prefixNum(prefix) > 0;
    }

}

-------------------------------------------------------------------------------- 回到目录

更多字典树:

  • 压缩字典树
    在这里插入图片描述

为您推荐