基于Trie树实现搜索功能

灰太狼 2023-07-07 12:45 15阅读 0赞

Trie，又称单词查找树或键树，是一种树形结构。  
一组单词，inn, int, at, age, adv, ant, 我们可以得到下面的Trie。我们目前这个功能主要输入i就能获取 到输入（i,in,inn,int）等同的结果。用这种方式做一下示例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZhamluZ19mZWl5dWU_size_16_color_FFFFFF_t_70]  
1、通过list和map来存放想要内容，这种方式的优点在于。在遍历当前下面子节点的时候，能够通过hash索引，不用通过去遍历，速度更快。缺点也是很明显，map和list的所占用的空间很大，这种方式也是通过不断添加子树。那对于输入关键字前缀不能输入过长，这会造成整个树过高。造成空间消耗很大。

public class Trie<T> {
        /**
         * 存储当前树的输出的内容
         */
        private List<T> children;
        /**
         * 存放当前树下面的子节点树
         */
        private Map<String, Trie<T>> childMap;
    
        /**
         * 添加搜索的前缀和想要获取到的内容
         * @param keys
         * @param t
         */
        public synchronized void add(char[] keys, T t) {
            if (null == children) {
                children = new ArrayList<T>();
            }
            
            if (null == keys || keys.length == 0) {
                return;
            }
            
            if(!children.contains(t)){
                children.add(t);
            }
            if (keys.length > 0) {
                if (CollectionUtils.isEmpty(childMap)) {
                    childMap = new HashMap<String, Trie<T>>();
                }
                Trie<T> child = childMap.get(String.valueOf(keys[0]));
                if (null == child) {
                    child = new Trie<T>();
                }
                childMap.put(String.valueOf(keys[0]), child);
                child.add(Arrays.copyOfRange(keys, 1, keys.length), t);
            }
        }
    
        /**
         * 通过输入前缀 获取到想要的内容
         * @param keys
         * @return
         */
        public List<T> listAllWords(char[] keys) {
              //递归遍历出口，当遍历到最后子节点的时候添加的内容
            if (null == keys || keys.length == 0) {
                return children;
            }
    
            String currentVertexKey = String.valueOf(keys[0]);
    
            if (CollectionUtils.isEmpty(childMap)) {
                return null;
            }
    
            Trie<T> currentTrie = childMap.get(currentVertexKey);
            if (Objects.isNull(currentTrie)) {
                return null;
            }
            //递归遍历子节点的数据
            return currentTrie.listAllWords(Arrays.copyOfRange(keys, 1, keys.length));
        }
    
        public static void main(String[] args) {
            Trie<String> trie = new Trie<>();
            trie.add("中国大庆".toCharArray(), "大庆");
            trie.add("中国青岛".toCharArray(), "青岛");
            List<String> strLst = trie.listAllWords("中国大".toCharArray());
            System.out.println(strLst);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZhamluZ19mZWl5dWU_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200223172531138.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZhamluZ19mZWl5dWU=,size_16,color_FFFFFF,t_70