理解trie树

简介

TrieTree又称作字典树或前缀树（下称Trie），是一种专门用于处理字符串的树。
对比其其他树查询字符串的时间复杂度，Trie的时间复杂度十分的低。

• 平均查询时间复杂
  • 常规的树结构：O(logn)
  • Trie:O(M),M为字符串长度

思路

假设我们的字典可以插入26个字母作为元素组成的字符串，则每个节点都可拥有26个子节点，并把把字符（元素）存储在边上。

上面输入了3个字符串,可以看出若查找ab，只需要2次

• 插入
  • 遍历各个字符，判断是否存在，若不存在，则创建

• 删除

而我们可以在Trie的节点上增加某些数据项就可以扩展其功能。
这里我们写2个

• 具体功能
  1. 查询有多少词使用某前缀
     • 在插入时，让每个节点上记录其经过的次数（Path）,
  2. 查询某词汇是否存在，并返回插入次数。
     • 在插入时，让最后一个字节的节点记录当前插入的次数（End）。

实现

public static class TrieNode {

        public int path;
        public int end;
        public TrieNode[] nexts;

        public TrieNode(){
            path = 0;
            end = 0;
            nexts = new TrieNode[26];
        }
    }

    public static class Trie {

        private TrieNode root;

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

        //1.查询有多少词是使用该前缀
        public int prefixNumber(String prefix) {

            if(prefix == null)
                return 0;
            char[] chars = prefix.toCharArray();
            TrieNode node = root;
            int index = 0;
            for(int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';
                node = node.nexts[index];
                if(node == null) {
                    return 0;
                }
            }
            return node.path;
        }

        //2.查询该词是否存在/插入次数
        public int search(String word) {

            //空字符串变为字符数组长度为0
            if(word == null) {
                return 0;
            }
            TrieNode node = root;
            char[] chars = word.toCharArray();
            int index = 0;
            for(int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';
                node = node.nexts[index];
                if(node == null) {
                    return 0;
                }
            }
            return node.end;
        }

        //插入
        public void insert(String word) {
            if(word == null)
                return;
            char[] chars = word.toCharArray();
            TrieNode node = root;
            int index = 0;
            for(int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';
                if(node.nexts[index] == null) {
                    node.nexts[index] = new TrieNode();
                }
                node = node.nexts[index];
                node.path++;
            }
            node.end++;
        }

        //删除
        public void delete(String word) {
            if(search(word) != 0) {
                char[] chars = word.toCharArray();
                TrieNode node = root;
                int index = 0;
                for(int i = 0; i < chars.length; i++) {
                    index = chars[i] - 'a';
                    node = node.nexts[index];
                    //当有同一前缀多个词时，想删除其中一个，
                    //可判断前缀后的节点（后半部分），其path必定为1。所以只要找到一个节点path - 1<=0就是后半部分了。
                    //直接不要即可。
                    if(node.path - 1 < 0) {
                       node.nexts[index] = null;
                       return;
                    }
                    node.path--;
                }
                node.end--;
            }
        }
    }