数据结构Trie（前缀树）

　　问题
　　求出给定字符串数组的最大公共前缀〔hello，helloworld，help〕用途
　　自动完成
　　拼写检查
　　ip路由
　　T9文本预测
　　猜字游戏
　　还有其他几种数据结构，例如平衡树和哈希表，它们使我们可以在字符串数据集中搜索单词。那为什么我们需要trie呢？
　　尽管哈希表在查找key时具有O（1）时间复杂度，但在以下操作中效率不高：查找具有公共前缀的所有键。按字典顺序枚举字符串数据集。
　　Trie优于哈希表的另一个原因是，随着哈希表大小的增加，会出现大量哈希冲突，并且搜索时间复杂度可能会恶化到O（n），其中n是插入的键数。在存储许多具有相同前缀的键时，与HashTable相比，Trie可以使用更少的空间。在这种情况下，使用trie的时间复杂度仅为O（m），其中m是key长度。
　　在平衡树中搜索一个键需要O（mlogn）时间复杂度。Trie节点结构
　　Trie是一棵有根的树。其节点具有以下字段：与其子级的最大R链接，其中每个链接对应于数据集字母表中的一个R字符值。在本文中，我们假设R为26，即小写拉丁字母的数量。布尔字段，它指定节点是否对应于键的末尾，或者只是一个键前缀。当前节点下级节点个数（非必须，我们为了解决最长公共串才加上）publicclassTrieNode｛RlinkstonodechildrenprivateTrieNode〔〕privatefinalintR26；privatebooleanisEintsize0；publicTrieNode（）｛linksnewTrieNode〔R〕；｝publicbooleancontainsKey（charch）｛returnlinks〔cha〕！｝publicTrieNodeget（charch）｛returnlinks〔cha〕；｝publicvoidput（charch，TrieNodenode）｛links〔cha〕｝publicvoidsetEnd（）｛isE｝publicbooleanisEnd（）｛returnisE｝publicintgetLinks（）｛｝｝
　　插入查询类publicclassTrie｛privateTrieNpublicTrie（）｛rootnewTrieNode（）；｝Insertsawordintothetrie。publicvoidinsert（Stringword）｛TrieNfor（inti0；iword。length（）；i）｛charcurrentCharword。charAt（i）；if（！node。containsKey（currentChar））｛node。put（currentChar，newTrieNode（））；｝nodenode。get（currentChar）；｝注意这里，设置end的节点是不包含最后一个字符的node。setEnd（）；｝privateTrieNodesearchPrefix（Stringword）｛TrieNfor（inti0；iword。length（）；i）｛charcurLetterword。charAt（i）；if（node。containsKey（curLetter））｛nodenode。get（curLetter）；｝else｛｝｝｝Returnsifthewordisinthetrie。publicbooleansearch（Stringword）｛TrieNodenodesearchPrefix（word）；returnnode！nullnode。isEnd（）；｝publicbooleanstartsWith（Stringprefix）｛TrieNodenodesearchPrefix（prefix）；returnnode！｝publicStringsearchLongestPrefix（Strings）｛TrieNStringBuildersbnewStringBuilder（）；for（charc：s。toCharArray（））｛if（node。containsKey（c）node。getLinks（）1！node。isEnd（））｛sb。append（c）；nodenode。get（c）；｝else｛returnsb。toString（）；｝｝returnsb。toString（）；｝publicstaticvoidmain（String〔〕args）｛String〔〕linknewString〔〕｛hello，helloworld，help｝；TrietrienewTrie（）；for（Strings：link）｛trie。insert（s）；｝System。out。println（trie。searchLongestPrefix（link〔link。length1〕））；｝｝