问题标签 [ternary-search-tree]

我正在尝试将字符插入三元搜索树，请帮我解决这个分段错误？？这是我正在做的插入尝试，在运行这个我得到分段错误（核心转储）请帮我解决为什么会这样？

我为 20000 个单词实现了三元搜索树。我想知道一种算法来找到最长的公共前缀（至少由 2 个单词共享的前缀）？无论如何要在树中找到最长的公共前缀？（没有三元搜索树）

使用三叉树的 FSA 与将转换表实现为搜索树（例如 std::map）的 trie 有什么区别？看起来两者都具有读取一个符号的 O(log k) 复杂度和 O(S) 内存复杂度，其中 k 是字母大小，S 是所有接受的输入字符串的长度之和。

如果我们不需要自动机在运行时更改，那么最好的选择不是使用（符号，状态）转换对的排序向量以及二进制搜索吗？

我认为二叉搜索树是最简单的例子，但我真的想知道如何探索三叉搜索树或各种尝试。我对这些没有任何经验，但我了解添加和搜索它们的概念。

我的问题是，当我找到一个与我的输入匹配的节点（例如自动完成）时，我如何有效地收集所有子节点？

所以我正在尝试进行三元搜索尝试。现在，我只处理插入功能。我已经在线了解了三元搜索树的基本思想。我知道一个根节点有 3 个叶子，如果字符出现在根之前，它会向左，之后 - 右，如果它与根匹配，它会进入中间叶子。所以我的主要目标是制作一个程序，可以为拼写错误的用户输入的单词建议单词。但目前我只是在做三元搜索尝试。我使用 trie 制作字典，使用它检查用户输入的单词以建议下一个最佳选择。但是现在，只是将一些字符输入到三元树中，当我显示它时，它应该按顺序显示。我不是 100% 确定我关于中间叶子的逻辑。现在我的程序在运行时，给我一些与输入的最后一个字符有关的垃圾无限值。我不知道我哪里出错了。有人可以指出我在哪里犯了错误吗？另外，你能告诉我我写的任何逻辑是否错误吗？我的意思是，你不必给我代码或任何东西，因为一旦我知道我哪里出错了，我觉得我有能力自己做，但是如果有人可以帮助我找到我的错误，那会帮助我很多！

整个代码：

我正在使用 Geany 文本编辑器，并且在 Linux Mint 上。我遇到了一个问题，当我点击显示功能时，编译器只会打印我无限输入的最后一个字符。任何帮助都会非常有帮助！谢谢！

我想将单词字典转换为二进制文件。经过一段时间的搜索，我发现三元搜索树是我使用的最佳选择。我找不到如何将其序列化为文件。每个节点将有一个 char 值、3 个指针（对于三个孩子 - 低、相等、高）和另一个字段（用于保存其他信息）我怎样才能序列化它？谢谢

我目前正试图了解 Trie 的变化，并想知道是否有人能够澄清几点。（我对这个问题的答案感到很困惑Tries vs ternary search trees for autocomplete?，尤其是在第一段中）。

根据我的阅读，以下内容是否正确？假设我们在数据结构中存储了 n 个元素，L 是我们要搜索的字符串的长度：

• Trie 将其键存储在叶节点上，如果我们的搜索结果为正，则意味着它将执行 O(L) 比较。然而，对于未命中的情况，平均性能为 O(log2(n))。

• 类似地，基数树（R = 2^r）将键存储在叶节点，并将执行 O(L) 比较以获得正命中。然而，未命中会更快，并且平均发生在 O(logR(n)) 中。

• 三元搜索 Trie 本质上是一个带有操作 <、>、= 的 BST，并且每个节点中都存储了一个字符。我们不比较节点处的整个密钥（与 BST 一样），而是只比较该节点处密钥的一个字符。总的来说，假设我们的字母大小是 A，那么如果有命中，我们必须（最多）执行 O(L*A) = O(L) 比较。如果没有命中，我们平均有 O(log3(n))。

关于基数树，如果我们的字母表是 {0,1} 并且我们设置 R = 4，对于二进制字符串 0101，我们只需要两次比较，对吧？因此，如果我们的字母表的大小是 A，我们实际上只会执行 L * (A / R) 比较？如果是这样，那么我猜这只是 O(L)，但我很好奇这是否是正确的推理。

感谢大家提供的任何帮助！

三叉搜索树需要 O(log(n)+k) 比较，其中 n 是字符串数，k 是要搜索的字符串的长度，二叉搜索树需要 log(n) 比较，那么为什么 TST 比 BST 快？

我正在使用三元搜索树。以下代码应该让您大致了解树的外观。每个叶子都包含一个指向链表的指针，该链表包含指向头节点的指针。每个叶子最多可以有 3 个节点。因此，在根叶填充了 3 个数据值之后，如果下一个值小于第一个节点，则将其插入左侧，如果大于则将其插入右侧，如果在中间，则将其插入插入中心孩子。

我目前正在尝试创建一个将树和 int 值作为输入的函数。然后它检查树中的每一个叶子，看看是否有叶子等于 int 值，如果是，它将返回 1，否则返回 0。

以下是我的代码

谁能建议我哪里出了问题以及如何解决这个问题？

How can I go about listing the words a TST contains in an alphabetical order?

Unlike BSTs where an in-order traversal will do the trick, this won't work TST. Neither would pre-order nor post-order traversals.

More so, the nodes of TST contain alphabets not words as opposed to the nodes of some BST implementation. And there are some alphabets which not be included when moving from the left nodes to right nodes.

I can seem to get my head around it.

The figure below show the list of words of a TST in alphabetical order.

Image from: http://www.geeksforgeeks.org/ternary-search-tree/