崔 是一种高效的信息检索工具 崔 val数据结构。使用Trie，搜索复杂度可以达到最佳极限（密钥长度）。如果我们将密钥存储在二叉搜索树中，一个平衡良好的BST将需要与 M*logn ，其中M是最大字符串长度，N是树中的键数。使用Trie，我们可以在O（M）时间内搜索密钥。然而，惩罚取决于Trie存储要求（请参考 Trie的应用 更多细节）
null
![图片[1]-Trie |（插入并搜索）-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/cdn-uploads/Trie.png)
Trie的每个节点都由多个分支组成。每个分支代表键的一个可能字符。我们需要将每个键的最后一个节点标记为单词结束节点。Trie节点字段 伊森多福德 用于将节点区分为词尾节点。表示英语字母表节点的简单结构如下：， //Trie节点 结构三节点 { 结构三节点*子元素[字母表大小]； //如果节点 //表示一个词的结尾 布尔·伊森多福德； }; 将密钥插入Trie是一种简单的方法。输入键的每个字符都作为单独的Trie节点插入。请注意 儿童 是指向下一级trie节点的指针（或引用）数组。关键字符充当数组的索引 儿童 .如果输入键是新的或现有键的扩展，我们需要构造该键的不存在节点，并为最后一个节点标记单词的结尾。如果输入键是Trie中现有键的前缀，我们只需将键的最后一个节点标记为单词的结尾。关键帧长度决定了Trie的深度。
搜索键类似于插入操作，但是，我们只比较字符并向下移动。搜索可能会因字符串结尾或trie中缺少键而终止。在前一种情况下，如果 伊森多福德 最后一个节点的字段为true，则该键存在于trie中。在第二种情况下，搜索终止，而不检查密钥的所有字符，因为该密钥不在trie中。 下图解释了使用下面示例中给出的键构造trie，
root / t a b | | | h n y | | | e s y e / | | i r w | | | r e e | r
在这幅画里，每个角色都是同一类型的 trie_node_t .例如 根 属于trie_node_t类型，它是子对象 A. , B 和 T 如果已填充，则根的所有其他节点都将为空。类似地，下一级的“a”只有一个孩子（“n”），其他所有孩子都为空。叶节点位于 蓝色 .
插入和搜索成本 O（键长） 然而，Trie的内存需求是 O（字母表大小*键长*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->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" : cout << "No" ; search(root, "these" )? cout << "Yes" : cout << "No" ; 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->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" , "the" , output[search(root, "the" )] ); printf ( "%s --- %s" , "these" , output[search(root, "these" )] ); printf ( "%s --- %s" , "their" , output[search(root, "their" )] ); printf ( "%s --- %s" , "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.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 |
Python3
# Python program for insert and search # operation in a Trie class TrieNode: # Trie node class def __init__( self ): self .children = [ None ] * 26 # isEndOfWord is True if node represent the end of the word self .isEndOfWord = False class 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 case return 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 = True def 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.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.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 */ |
Javascript
<script> // Javascript implementation of search and insert operations // on Trie // Alphabet size (# of symbols) let ALPHABET_SIZE = 26; // trie node class TrieNode { constructor() { this .isEndOfWord = false ; this .children = new Array(ALPHABET_SIZE); for (let i = 0; i < ALPHABET_SIZE; i++) this .children[i] = null ; } } let root; // If not present, inserts key into trie // If the key is prefix of trie node, // just marks leaf node function insert(key) { let level; let length = key.length; let index; let pCrawl = root; for (level = 0; level < length; level++) { index = key[level].charCodeAt(0) - 'a' .charCodeAt(0); 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 function search(key) { let level; let length = key.length; let index; let pCrawl = root; for (level = 0; level < length; level++) { index = key[level].charCodeAt(0) - 'a' .charCodeAt(0); if (pCrawl.children[index] == null ) return false ; pCrawl = pCrawl.children[index]; } return (pCrawl.isEndOfWord); } // Driver // Input keys (use only 'a' through 'z' and lower case) let keys = [ "the" , "a" , "there" , "answer" , "any" , "by" , "bye" , "their" ]; let output = [ "Not present in trie" , "Present in trie" ]; root = new TrieNode(); // Construct trie let i; for (i = 0; i < keys.length ; i++) insert(keys[i]); // Search for different keys if (search( "the" ) == true ) document.write( "the --- " + output[1]+ "<br>" ); else document.write( "the --- " + output[0]+ "<br>" ); if (search( "these" ) == true ) document.write( "these --- " + output[1]+ "<br>" ); else document.write( "these --- " + output[0]+ "<br>" ); if (search( "their" ) == true ) document.write( "their --- " + output[1]+ "<br>" ); else document.write( "their --- " + output[0]+ "<br>" ); if (search( "thaw" ) == true ) document.write( "thaw --- " + output[1]+ "<br>" ); else document.write( "thaw --- " + output[0]+ "<br>" ); // This code is contributed by patel2127 </script> |
输出：
the --- Present in triethese --- Not present in trietheir --- Present in triethaw --- Not present in trie
注： 在视频中， 伊森多福德 被称为 岛 . 相关文章：
实践问题：
最近关于Trie的文章 本文由 文基 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
