学院的网站建设的意义官方网站模板

学院的网站建设的意义,官方网站模板,广州设计公司前十名,汕头网站上排名Trie树(字典树)学习笔记 什么是Trie树? Trie树是一种树形数据结构,用于高效存储和检索字符串。核心思想是共享公共前缀,所有以相同字符开头的字符串共享同一个节点路径。 名字来源: Trie来自retrieval(检索),读作try 核心特点 根节点不包含字符,其他每个节点包含一…Trie树(字典树)学习笔记什么是Trie树?Trie树是一种树形数据结构,用于高效存储和检索字符串。核心思想是共享公共前缀,所有以相同字符开头的字符串共享同一个节点路径。名字来源:Trie来自retrieval(检索),读作try核心特点根节点不包含字符,其他每个节点包含一个字符从根到某节点的路径上的字符连起来就是该节点对应的字符串每个节点的子节点字符都不相同用isEnd标记是否为完整单词的结尾Java实现(HashMap版本)classTrieNode{MapCharacter,TrieNodechildrennewHashMap();booleanisEndfalse;}classTrie{privateTrieNoderootnewTrieNode();// 插入单词publicvoidinsert(Stringword){TrieNodenoderoot;for(charc:word.toCharArray()){node.children.putIfAbsent(c,newTrieNode());nodenode.children.get(c);}node.isEndtrue;}// 查找完整单词publicbooleansearch(Stringword){TrieNodenoderoot;for(charc:word.toCharArray()){nodenode.children.get(c);if(nodenull)returnfalse;}returnnode.isEnd;}// 查找前缀publicbooleanstartsWith(Stringprefix){TrieNodenoderoot;for(charc:prefix.toCharArray()){nodenode.children.get(c);if(nodenull)returnfalse;}returntrue;}}使用示例TrietrienewTrie();// 插入单词trie.insert(apple);trie.insert(app);trie.insert(application);// 查找完整单词trie.search(app);// true - app是完整单词trie.search(appl);// false - appl不是完整单词trie.search(apple);// true// 查找前缀trie.startsWith(app);// true - 有apple、app、applicationtrie.startsWith(appl);// true - 有apple、applicationtrie.startsWith(banana);// false - 没有这个前缀可视化理解插入 “cat”, “car”, “dog” 后的结构:root / \ c d | | a o / \ | t r g (✓) (✓) (✓)✓ 表示isEnd true,是完整单词查找car: root → c → a → r (✓) → 找到查找ca: root → c → a (✗) → 不是完整单词前缀ca: root → c → a → 路径存在 → true时间复杂度插入: O(m) - m是字符串长度查找: O(m)前缀查找: O(m)空间: O(n×m) - n个字符串,平均长度m典型应用场景搜索引擎自动补全- 用户输入app,提示apple、“application”拼写检查检查单词是否在字典中IP路由表最长前缀匹配词频统计在节点中添加计数器字符串排序按字典序排序大量字符串常见变种1. 带计数的TrieclassTrieNode{MapCharacter,TrieNodechildrennewHashMap();intcount0;// 记录经过该节点的单词数}2. 支持删除的Triepublicbooleandelete(Stringword){returndelete(root,word,0);}privatebooleandelete(TrieNodenode,Stringword,intindex){if(indexword.length()){if(!node.isEnd)returnfalse;node.isEndfalse;returnnode.children.isEmpty();}charcword.charAt(index);TrieNodechildnode.children.get(c);if(childnull)returnfalse;booleanshouldDeletedelete(child,word,index1);if(shouldDelete){node.children.remove(c);returnnode.children.isEmpty()!node.isEnd;}returnfalse;}总结Trie树是处理字符串前缀问题的利器,通过共享公共前缀大幅提升查找效率。HashMap实现既灵活又实用,是面试和实际开发的首选方案。