我最近听说过nedtries并决定尝试实现它们,但是有些事情让我对它的搜索操作的复杂性感到困扰; 我不能忍受为什么他们应该这么快.
根据我的理解,他们的搜索操作的预期复杂性应该是O(m/2),其中m是密钥的大小.如果将它与传统二叉树中搜索操作的复杂性进行比较,则得到:log2(n)> = m/2
设密钥为32位长:log2(n)> = 16 <=> n> = 65536
因此,从65536个项目开始,nedtries应该比二叉树更快.然而,作者声称他们总是比二叉树更快,所以我对其复杂性的假设是错误的,或者在搜索的每一步执行的计算在nedtrie中都要快得多.
那么,它呢？
我只想仔细检查在最坏的情况下Trie数据结构可能具有的总空间。我以为会是O（N * K），其中N是节点总数，K是字母表的大小（指向其他尝试），但是人们一直告诉我这是O（K ^ L），其中K是字母的大小和L是平均单词长度，但是那些空指针会占用Java中的存储空间吗？例如，如果节点之一只有总大小为K的3个分支/点，它是否使用K空间？还是只有3个？以下是Trie的实现Java
class Trie {
private Trie [] tries;
public Trie () {
// A size 256 array of Trie, and they are all null
this.tries = new Trie[256]; // K = 256;
}
}
嗨:)有谁能告诉我为什么以下代码不起作用？程序if(children[word[letter_no] - 'A'] == nullptr)在对应的节点中的行崩溃'B'.但节点被创建,当我尝试调用children[1]构造函数,它的工作原理.但是当它在insert()函数中调用时,它不会......
#include <memory> //shared_ptr
#include <string>
using namespace std;
const int ALPHABET = 26;
class Node {
public:
shared_ptr<Node> children[ALPHABET];
Node() { for (int i = 0; i < ALPHABET; ++i) children[i] = nullptr;}
void insert(const string &word, unsigned letter_no) {
if (letter_no < word.length()) {
if (children[word[letter_no] - 'A'] == nullptr)
children[word[letter_no] - 'A'] = make_shared<Node>();
children[word[letter_no] - 'A']->insert(word, letter_no+1);
}
}
};
int …在C++中使用trie制作字典.在某些输入上给出分段错误.
调试帮助我发现问题出在check函数中.特别是在它退出循环之后,在check isword条件下.
typedef struct node
{
bool is_word;
struct node *children[27];
} node;
node *createNode()
{
// Void -> Node*
// Create a pointer to a node(structure)
// Allocate memory and store address in child pointer
node *child = (node *)malloc(sizeof(node));
// Initialize each node in child to NULL
for (int i = 0; i < N; i++)
{
child->children[i] = NULL;
}
// Initialize the is_word variable
child->is_word = false;
// Return the pointer
return child;
}
bool …我有一个字符串数组，总共（100k）。我需要检查之前是否出现过相同的字符串，如果出现，我所要做的就是返回该字符串。我已经使用嵌套 for 循环编写了代码，但不幸的是我的性能很差。为 (string[100K]) 正确处理函数需要 1.9 分钟，而我希望它在几秒钟内完成。
我关心的不是逻辑。我关心的是 LOOP。如何提高循环的效率。
public string StartMatchingProcess(string[]inputArray)
{
string[] stringArray = inputArray;
string result = string.Empty;
for (long i = 0; i < stringArray.Length; i++)
{
for (long j = 0; j <= i; j++)
{
if(i == j) break;
if (IsPrefix(stringArray[i], stringArray[j]))
{
return stringArray[i];
}
}
}
Console.WriteLine("GOOD SET");
return result;
}
public bool IsPrefix(string string1,string string2)
{
if (AreString1ValuesValid(string1, string2))
{
if (string1 == string2.Substring(0, string1.Length))
{
Console.WriteLine("BAD SET");
Console.WriteLine(string1);
return …目标是创建一个特里数据结构。我见过Tree::Trie并使用过它。只有在读取文件（数据库）后，它才会将数据转换为特里结构。因此，这会使处理速度变慢，因为每次需要查找时，整个数据都会转换为 trie。
有没有一种方法可以让我一次性创建一个特里树并将其用作查找的特里树结构。
我试图解决HackerRank 上的无前缀集问题。我的解决方案仅通过了一半的测试用例。我没有得到我在这里缺少的东西。
\n\n问题陈述：给定 N 个字符串。每个字符串仅包含小写字母a\xe2\x88\x92j（包括两者）。如果没有字符串是另一个字符串的前缀，则N 个字符串的集合被称为GOOD SET ，否则为BAD SET。
例如： , aab, abcde,aabcd是BAD SET，因为aab是 的前缀aabcd。
这是我实现的逻辑。\n
\n\nclass Trie {\n Trie next[] = new Trie[10];\n boolean end[] = new boolean[10];\n}\n\nprivate static void goodOrBad(String[] array, Trie start) {\n for (String string : array) {\n Trie current = start;\n Trie previous = start;\n int index = 0;\n char strArray[] = string.toCharArray();\n …