在C中的O（N）中搜索T

Question

如何遍历C中O（n）时间的trie树我想要做一个for循环循环，如果一个字母是匹配，然后搜索该链表，但会给我n^2次。有什么方法可以加快速度？

谢谢！

Answer 1

什么是在“O（n）”中使用的“n”？如果n表示搜索字符串中的字符数，则可以在O（n）时间内执行以下代码。 for循环的

/* structure of Trie node */ 
struct trieNode { 
    char *value; 
    childNode children(); 
    int childCount; 
} 

/* structure for childnode in a Trie node. Whichi contains 'key' and pointer to child node */ 
struct childNode { 
    char key; 
    trieNode *node; 
} 


/* setup Trie and search string. (not real code) */ 
trieNode root=createTrinode(...) ; /* Setup Trie of your problem. */ 
char* searchString = inputSearchString(...); /* get string for search */ 

int i; 
trieNode curNode; 

curNode = root; 
for i=0 to len(searchString)-1 
{ 
    curNode = findChildren(curNode,searchString(i)); /* findChildren function returns childnode of first argument, whose key is equal to second argument. (Code of findChildren is omitted) */ 
} 

/* curNode is the traversed leaf node by searchStrin */ 

指数是0到n（searchString的长度）-1，因此该代码可以执行JN O（n）的时间。

此代码不考虑serach-string不包含在给定的Trie中的情况。