本文概述

• C++
• C
• Java
• python
• C#

Trie是一种高效的信息检索数据结构。使用Trie，可以使搜索复杂度达到最优限度(密钥长度)。如果我们将键存储在二叉搜索树中，一个良好平衡的BST所需要的时间将与M * log N成比例，其中M是最大字符串长度，N是树中键的数量。使用Trie，我们可以在O(M)时间内搜索密钥。然而，罚款是在Trie存储要求上(请参阅Trie的申请以了解更多详情)

文章图片
每个Trie节点由多个分支组成。每个分支表示键的一个可能字符。我们需要将每个键的最后一个节点标记为单词节点的结尾。Trie节点字段isEndOfWord用于区分节点作为单词节点的结尾。用一个简单的结构来表示英语字母表的节点可以如下所示:
// Trie节点
struct TrieNode
【Trie插入和搜索实现原理和代码实现】{
struct TrieNode * children [ALPHABET_SIZE];
// 如果节点的isEndOfWord为真, 表示单词的末尾
bool isEndOfWord;
};
将密钥插入Trie是一种简单的方法。输入键的每个字符都作为一个单独的Trie节点插入。请注意孩子们是指向下一级Trie节点的指针(或引用)的数组。关键字符充当数组的索引孩子们。如果输入键是新键或现有键的扩展, 则需要构造键的不存在节点, 并将单词的结尾标记为最后一个节点。如果输入键是Trie中现有键的前缀, 我们只需将键的最后一个节点标记为单词的结尾即可。密钥长度确定Trie深度。
搜索键类似于插入操作, 但是, 我们仅比较字符并向下移动。搜索可能由于字符串的结尾或Trie中缺少关键字而终止。在前一种情况下, 如果isEndofWord最后一个节点的字段为true, 则密钥存在于trie中。在第二种情况下, 搜索不会终止, 而不会检查键的所有字符, 因为该键不在Trie中。
下图说明了如何使用以下示例中给出的键构造trie,

root /\\ tab ||| hny ||\| esye / || irw ||| ree | r

在图片中, 每个字符都是类型trie_node_t。例如, 根是trie_node_t类型, 它是子级一种, b和?填充后, root的所有其他节点将为NULL。类似地, 下一级别的" a"只有一个孩子(" n"), 所有其他孩子均为NULL。叶节点在蓝色.
插入和搜索费用O(key_length), 但是Trie的内存要求是O(ALPHABET_SIZE * key_length * N)其中N是Trie中的键数。有效表示Trie节点(例如压缩的Trie, 三元搜索树等)以最小化trie的内存要求。
C++

//C++ implementation of search and insert //operations on Trie #include < bits/stdc++.h> using namespace std; const int ALPHABET_SIZE = 26; //trie node struct TrieNode { struct TrieNode *children[ALPHABET_SIZE]; //isEndOfWord is true if the node represents //end of a word bool isEndOfWord; }; //Returns new trie node (initialized to NULLs) struct TrieNode *getNode( void ) { struct TrieNode *pNode =new TrieNode; pNode-> isEndOfWord = false ; for ( int i = 0; i < ALPHABET_SIZE; i++) pNode-> children[i] = NULL; return pNode; }//If not present, inserts key into trie //If the key is prefix of trie node, just //marks leaf node void insert( struct TrieNode *root, string key) { struct TrieNode *pCrawl = root; for ( int i = 0; i < key.length(); i++) { int index = key[i] - 'a' ; if (!pCrawl-> children[index]) pCrawl-> children[index] = getNode(); pCrawl = pCrawl-> children[index]; }//mark last node as leaf pCrawl-> isEndOfWord = true ; }//Returns true if key presents in trie, else //false bool search( struct TrieNode *root, string key) { struct TrieNode *pCrawl = root; for ( int i = 0; i < key.length(); i++) { int index = key[i] - 'a' ; if (!pCrawl-> children[index]) return false ; pCrawl = pCrawl-> children[index]; }return (pCrawl != NULL & & pCrawl-> isEndOfWord); }//Driver int main() { //Input keys (use only 'a' through 'z' //and lower case) string keys[] = { "the" , "a" , "there" , "answer" , "any" , "by" , "bye" , "their" }; int n = sizeof (keys)/sizeof (keys[0]); struct TrieNode *root = getNode(); //Construct trie for ( int i = 0; i < n; i++) insert(root, keys[i]); //Search for different keys search(root, "the" )? cout < < "Yes\n" : cout < < "No\n" ; search(root, "these" )? cout < < "Yes\n" : cout < < "No\n" ; return 0; }

C

//C implementation of search and insert operations //on Trie #include < stdio.h> #include < stdlib.h> #include < string.h> #include < stdbool.h> #define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])//Alphabet size (# of symbols) #define ALPHABET_SIZE (26)//Converts key current character into index //use only 'a' through 'z' and lower case #define CHAR_TO_INDEX(c) ((int)c - (int)'a')//trie node struct TrieNode { struct TrieNode *children[ALPHABET_SIZE]; //isEndOfWord is true if the node represents //end of a word bool isEndOfWord; }; //Returns new trie node (initialized to NULLs) struct TrieNode *getNode( void ) { struct TrieNode *pNode = NULL; pNode = ( struct TrieNode *) malloc ( sizeof ( struct TrieNode)); if (pNode) { int i; pNode-> isEndOfWord = false ; for (i = 0; i < ALPHABET_SIZE; i++) pNode-> children[i] = NULL; }return pNode; }//If not present, inserts key into trie //If the key is prefix of trie node, just marks leaf node void insert( struct TrieNode *root, const char *key) { int level; int length = strlen (key); int index; struct TrieNode *pCrawl = root; for (level = 0; level < length; level++) { index = CHAR_TO_INDEX(key[level]); if (!pCrawl-> children[index]) pCrawl-> children[index] = getNode(); pCrawl = pCrawl-> children[index]; }//mark last node as leaf pCrawl-> isEndOfWord = true ; }//Returns true if key presents in trie, else false bool search( struct TrieNode *root, const char *key) { int level; int length = strlen (key); int index; struct TrieNode *pCrawl = root; for (level = 0; level < length; level++) { index = CHAR_TO_INDEX(key[level]); if (!pCrawl-> children[index]) return false ; pCrawl = pCrawl-> children[index]; }return (pCrawl != NULL & & pCrawl-> isEndOfWord); }//Driver int main() { //Input keys (use only 'a' through 'z' and lower case) char keys[][8] = { "the" , "a" , "there" , "answer" , "any" , "by" , "bye" , "their" }; char output[][32] = { "Not present in trie" , "Present in trie" }; struct TrieNode *root = getNode(); //Construct trie int i; for (i = 0; i < ARRAY_SIZE(keys); i++) insert(root, keys[i]); //Search for different keys printf ( "%s --- %s\n" , "the" , output[search(root, "the" )] ); printf ( "%s --- %s\n" , "these" , output[search(root, "these" )] ); printf ( "%s --- %s\n" , "their" , output[search(root, "their" )] ); printf ( "%s --- %s\n" , "thaw" , output[search(root, "thaw" )] ); return 0; }

Java

//Java implementation of search and insert operations //on Trie public class Trie {//Alphabet size (# of symbols) static final int ALPHABET_SIZE = 26 ; //trie node static class TrieNode { TrieNode[] children = new TrieNode[ALPHABET_SIZE]; //isEndOfWord is true if the node represents //end of a word boolean isEndOfWord; TrieNode(){ isEndOfWord = false ; for ( int i = 0 ; i < ALPHABET_SIZE; i++) children[i] = null ; } }; static TrieNode root; //If not present, inserts key into trie //If the key is prefix of trie node, //just marks leaf node static void insert(String key) { int level; int length = key.length(); int index; TrieNode pCrawl = root; for (level = 0 ; level < length; level++) { index = key.charAt(level) - 'a' ; if (pCrawl.children[index] == null ) pCrawl.children[index] = new TrieNode(); pCrawl = pCrawl.children[index]; }//mark last node as leaf pCrawl.isEndOfWord = true ; }//Returns true if key presents in trie, else false static boolean search(String key) { int level; int length = key.length(); int index; TrieNode pCrawl = root; for (level = 0 ; level < length; level++) { index = key.charAt(level) - 'a' ; if (pCrawl.children[index] == null ) return false ; pCrawl = pCrawl.children[index]; }return (pCrawl != null & & pCrawl.isEndOfWord); }//Driver public static void main(String args[]) { //Input keys (use only 'a' through 'z' and lower case) String keys[] = { "the" , "a" , "there" , "answer" , "any" , "by" , "bye" , "their" }; String output[] = { "Not present in trie" , "Present in trie" }; root = new TrieNode(); //Construct trie int i; for (i = 0 ; i < keys.length ; i++) insert(keys[i]); //Search for different keys if (search( "the" ) == true ) System.out.println( "the --- " + output[ 1 ]); else System.out.println( "the --- " + output[ 0 ]); if (search( "these" ) == true ) System.out.println( "these --- " + output[ 1 ]); else System.out.println( "these --- " + output[ 0 ]); if (search( "their" ) == true ) System.out.println( "their --- " + output[ 1 ]); else System.out.println( "their --- " + output[ 0 ]); if (search( "thaw" ) == true ) System.out.println( "thaw --- " + output[ 1 ]); else System.out.println( "thaw --- " + output[ 0 ]); } } //This code is contributed by Sumit Ghosh

python

# Python program for insert and search # operation in a Trieclass TrieNode:# Trie node class def __init__( self ): self .children = [ None ] * 26# isEndOfWord is True if node represent the end of the word self .isEndOfWord = Falseclass Trie:# Trie data structure class def __init__( self ): self .root = self .getNode()def getNode( self ):# Returns new trie node (initialized to NULLs) return TrieNode()def _charToIndex( self , ch):# private helper function # Converts key current character into index # use only 'a' through 'z' and lower casereturn ord (ch) - ord ( 'a' )def insert( self , key):# If not present, inserts key into trie # If the key is prefix of trie node, # just marks leaf node pCrawl = self .root length = len (key) for level in range (length): index = self ._charToIndex(key[level])# if current character is not present if not pCrawl.children[index]: pCrawl.children[index] = self .getNode() pCrawl = pCrawl.children[index]# mark last node as leaf pCrawl.isEndOfWord = Truedef search( self , key):# Search key in the trie # Returns true if key presents # in trie, else false pCrawl = self .root length = len (key) for level in range (length): index = self ._charToIndex(key[level]) if not pCrawl.children[index]: return False pCrawl = pCrawl.children[index]return pCrawl ! = None and pCrawl.isEndOfWord# driver function def main():# Input keys (use only 'a' through 'z' and lower case) keys = [ "the" , "a" , "there" , "anaswe" , "any" , "by" , "their" ] output = [ "Not present in trie" , "Present in trie" ]# Trie object t = Trie()# Construct trie for key in keys: t.insert(key)# Search for different keys print ( "{} ---- {}" . format ( "the" , output[t.search( "the" )])) print ( "{} ---- {}" . format ( "these" , output[t.search( "these" )])) print ( "{} ---- {}" . format ( "their" , output[t.search( "their" )])) print ( "{} ---- {}" . format ( "thaw" , output[t.search( "thaw" )]))if __name__ = = '__main__' : main()# This code is contributed by Atul Kumar (www.facebook.com/atul.kr.007)

C#

//C# implementation of search and //insert operations on Trie using System; public class Trie {//Alphabet size (# of symbols) static readonly int ALPHABET_SIZE = 26; //trie node class TrieNode { public TrieNode[] children = new TrieNode[ALPHABET_SIZE]; //isEndOfWord is true if the node represents //end of a word public bool isEndOfWord; public TrieNode() { isEndOfWord = false ; for ( int i = 0; i < ALPHABET_SIZE; i++) children[i] = null ; } }; static TrieNode root; //If not present, inserts key into trie //If the key is prefix of trie node, //just marks leaf node static void insert(String key) { int level; int length = key.Length; int index; TrieNode pCrawl = root; for (level = 0; level < length; level++) { index = key[level] - 'a' ; if (pCrawl.children[index] == null ) pCrawl.children[index] = new TrieNode(); pCrawl = pCrawl.children[index]; }//mark last node as leaf pCrawl.isEndOfWord = true ; }//Returns true if key //presents in trie, else false static bool search(String key) { int level; int length = key.Length; int index; TrieNode pCrawl = root; for (level = 0; level < length; level++) { index = key[level] - 'a' ; if (pCrawl.children[index] == null ) return false ; pCrawl = pCrawl.children[index]; }return (pCrawl != null & & pCrawl.isEndOfWord); }//Driver public static void Main() { //Input keys (use only 'a' //through 'z' and lower case) String []keys = { "the" , "a" , "there" , "answer" , "any" , "by" , "bye" , "their" }; String []output = { "Not present in trie" , "Present in trie" }; root = new TrieNode(); //Construct trie int i; for (i = 0; i < keys.Length ; i++) insert(keys[i]); //Search for different keys if (search( "the" ) == true ) Console.WriteLine( "the --- " + output[1]); else Console.WriteLine( "the --- " + output[0]); if (search( "these" ) == true ) Console.WriteLine( "these --- " + output[1]); else Console.WriteLine( "these --- " + output[0]); if (search( "their" ) == true ) Console.WriteLine( "their --- " + output[1]); else Console.WriteLine( "their --- " + output[0]); if (search( "thaw" ) == true ) Console.WriteLine( "thaw --- " + output[1]); else Console.WriteLine( "thaw --- " + output[0]); } }/* This code contributed by PrinciRaj1992 */

输出：

the --- Present in trie these --- Not present in trie their --- Present in trie thaw --- Not present in trie

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

推荐阅读

• 

  健康码申诉多久有结果
• 

  脑卒中|它比癌症死亡率还高，每21秒就有1人因它死去！预防方法却很简单
• 

  酸枣仁泡水喝正确方法和用量 酸枣仁泡水喝正确方法
• 

  爱普生nx410清零
• 

  2017-2018学年八年级英语教学工作总结
• 

  民国时期的军阀孙传芳是怎么死的
• 

  佳能痰盂镜头 尼康小痰盂镜头半幅
• 

  遇到松下三匹变频空调外机不转怎么办？3个处理方法帮助你
• 

  苹果id锁定是什么意思（苹果ld锁定的意思）
• 

  如何提高文笔和写作能力 怎么提高写作水平
• 

  烧开的艾叶水能连续泡几天吗
• 

  外出烧烤必备烧烤食材清单
• 

  魔域手游9月14日更新内容介绍 全新功能寄售行上线
• 

  舷组词 汉字舷组词
• 

  68531异常指标分析
• 

  这一世，只为你
• 

  梦见打牌赢钱是什么意思
• 

  什么是即席分析,smartview即席分析
• 

  水中毒是怎么引起的
• 

  逃离塔科夫霰弹枪技能效果介绍 霰弹枪技能特效是什么

• 算法题（雨水捕获问题介绍和解决）
• JP Morgan Chase＆Co面试经历|S3（实习）
• 算法设计（最大滑动窗口-大小为k的所有子数组的最大值 S2）
• 机器学习中的聚类是什么（如何理解？）
• 如何使用Google Colab（详细步骤图解）
• Python中的手写方程式求解器详细实现
• python开发的常见问题S12（列表和元组）
• 三星（SRIB）实习面试经验
• win7任务栏透明度怎样设置？