【数据结构】--- 字典树
💖前言
🎄字典树
🏆定义
字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),查找搜索引擎中用于分词,词频分析,自动补全机制…
查找效率高:核心是利用公共前缀减少查询时间
☀️图例介绍
上面这棵Trie树包含的字符串集合是{in, inn, int, tea, ten, to}。树中的每一条边上都标识有一个字符。这些字符可以是任意一个字符集中的字符。比如对于都是小写字母的字符串,字符集就是’a’-‘z’;对于都是数字的字符串,字符集就是’0’-‘9’;对于二进制字符串,字符集就是0和1。
-
比如上图中框住节点的路径字符串是inn,
-
上图中框住节点的路径字符串是ten。 终结点与集合中的字符串是一一对应的。
⭐️代码实现字典树
/** * @author: guochao.bj@fang.com * @createDate: 2022/2/5 18:03 */ class TreeNode{ char data; //当前节点的字母 boolean isEnd=false; //是否为叶子节点 TreeNode[] childs; //子节点 public TreeNode(){ childs=new TreeNode[26]; isEnd=false; } } public class Test { /** * 创建字典树 * @param node * @param str * @return void * @author guochao.bj@fang.com * @date 2022/2/5 */ public static void creatTireTree(TreeNode node,String str){ //单词小写 char[] chars = str.toCharArray(); for (int i = 0; i < chars.length; i++) { int i1 = chars[i] - a; //字符转0~25的数字 使用ascII 值 if (node.childs[i1]==null){ node.childs[i1]= new TreeNode(); node.childs[i1].data=chars[i]; } node=node.childs[i1]; //切换跟节点 } node.isEnd=true; } /** * 字典树查找 * @param str * @param node * @return boolean * @author guochao.bj@fang.com * @date 2022/2/5 */ public static boolean find(String str,TreeNode node){ char[] chars = str.toCharArray(); for (int i = 0; i < chars.length; i++) { int i1 = chars[i] - a; //字符转0~25的数字 使用ascII 值 if (node.childs[i1]!=null){ node=node.childs[i1]; //切换节点 }else { return false; } } return node.isEnd; } public static void main(String[] args) { String[] aa={ "java","sql","php","ps","js"}; TreeNode root = new TreeNode(); for (String s : aa) { creatTireTree(root,s); } System.out.println("创建完成"); System.out.println(find("java",root)); System.out.println(find("jav",root)); } }
🔥字典树分析
查找时间复杂度为:O(N)
内存分析:内存消耗大,26的次方;
纯字典树不适合中日韩文,不适合IK分词。如果要使用需要使用字典树变种:双数组Tire树;
下一篇:
【数据结构】前缀树Trie