本文概述
Trie是一种高效的信息检索数据结构。使用Trie,可以使搜索复杂度达到最优限度(密钥长度)。如果我们将键存储在二叉搜索树中,一个良好平衡的BST所需要的时间将与M * log N成比例,其中M是最大字符串长度,N是树中键的数量。使用Trie,我们可以在O(M)时间内搜索密钥。然而,罚款是在Trie存储要求上(请参阅Trie的申请以了解更多详情)
每个Trie节点由多个分支组成。每个分支表示键的一个可能字符。我们需要将每个键的最后一个节点标记为单词节点的结尾。Trie节点字段isEndOfWord用于区分节点作为单词节点的结尾。用一个简单的结构来表示英语字母表的节点可以如下所示:
// Trie节点
struct TrieNode
{
struct TrieNode * children [ALPHABET_SIZE];
// 如果节点的isEndOfWord为真, 表示单词的末尾
bool isEndOfWord;
};
将密钥插入Trie是一种简单的方法。输入键的每个字符都作为一个单独的Trie节点插入。请注意孩子们是指向下一级Trie节点的指针(或引用)的数组。关键字符充当数组的索引孩子们。如果输入键是新键或现有键的扩展, 则需要构造键的不存在节点, 并将单词的结尾标记为最后一个节点。如果输入键是Trie中现有键的前缀, 我们只需将键的最后一个节点标记为单词的结尾即可。密钥长度确定Trie深度。
搜索键类似于插入操作, 但是, 我们仅比较字符并向下移动。搜索可能由于字符串的结尾或Trie中缺少关键字而终止。在前一种情况下, 如果isEndofWord最后一个节点的字段为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类型, 它是子级一种, 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 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 ! = 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
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。