问题标签 [ternary-search-tree]

这里据说三叉搜索树中的每个节点都有三个指针。左，右和等于。但是在 {CAT, BUGS, CATS, UP} 的示例树中，如何等于 'C' 的指针指向 'A' ？'C' 和 'A' 不相等对吗？

如果一个节点只能有三个指针，那么三叉树将如何表示一组键，例如 {CAB,CBA,CDA,CEA,CFA} ？

我使用三元搜索树制作了拼写检查器代码。谁能告诉我如何在 TST 中找到下一个可能的单词。例如，如果我想在拼写检查器中搜索单词“Manly”并且 TST 中不存在该单词，那么它给出的输出类似于 DO YOU MEAN: "Man" "Mango" 。.表示可能的近词

我使用三元搜索树 (TST) 制作了一个拼写检查器。谁能告诉我如何在 TST 中找到下一个可能的单词？

例如：如果我想在拼写检查器中搜索“Manly”这个词，并且 TST 中不存在这个词，那么它会输出类似这样的近词：

你的意思是：“男人”“芒果”。

这是实现三元搜索树的代码。任何机构都可以修改以找到最接近的单词。 http://www.geeksforgeeks.org/ternary-search-tree/

我正在尝试编写一个使用排序的整数列表和一个值的三元搜索算法函数。它类似于二分搜索，只是搜索区域在每次迭代中通过选择两个索引 ind1 和 ind2 (ind1 < ind2) 被分成三个较小的区域（长度尽可能相等）：

• 区域 1 包含索引值小于 ind1 的所有项目

• 区域 2 包含索引值大于 ind1 但小于 ind2 的所有项目

• 区域 3 包含索引值大于 ind2 的所有项目

如果可能，这些区域的大小应该相等。如果这不可能，那么Region 1的大小必须大于或等于Region 2的大小，Region 2的大小必须大于或等于Region 3的大小。任意两个区域的大小最多可能相差一个。

我试图遵循的格式是：

如果搜索区域的大小 <= 4

对 v 执行线性搜索

别的

如果 L[ind1] 等于 v，则选择索引 ind1 和 ind2

停止，我们找到了 v else if v < L[ind1]

如果 L[ind2] 等于 v，则重复区域 1 作为新的搜索区域

停止，我们找到了 v else if v < L[ind2]

重复区域 2 作为新的搜索区域，否则

重复区域 3 作为新的搜索区域

~~~~~

除了搜索列表外，我还需要在算法检查时生成步骤。

~~~~~

例如：

ternary_search([6,12,18,22,29,37,38,41,51,53,55,67,73,75,77,81,8 6,88,94], 88) 应该打印：

检查 88 是否等于 38

检查 88 是否小于 38

检查 88 是否等于 75

检查 88 是否小于 75

检查 88 是否等于 81

检查 88 是否小于 81

检查 88 是否等于 88

搜索成功

88 位于索引 17

共进行了 7 次比较

~~~~~ 我写的代码是：

当我打电话时： ternary_search([6,12,18,22,29,37,38,41,51,53,55,67,73,75,77,81,86,88,94], 51)

它打印：

Checking if 51 is less than 38 Checking if 51 is equal to 73 Checking if 51 is less than 73 Checking if 51 is less than 51 Search not successful A total of 1 comparisons were made

什么时候应该打印：

Checking if 51 is equal to 38 Checking if 51 is less than 38 Checking if 51 is equal to 75 Checking if 51 is less than 75 Checking if 51 is equal to 53 Checking if 51 is less than 53 Checking if 51 is equal to 41 Checking if 51 is equal to 51 Search successful 51 is located at index 8 A total of 8 comparisons were made

我有一个包含单词所有后缀的三元搜索树。在这个结构中构造和搜索单词的时间复杂度是多少？

例子：

一个单词banana$，有后缀banana$,anana$,nana$,ana$,na$,a$,$ 并且按照词典顺序$,a$,ana$,anana$,banana$,na$,nana$ .

以平衡形式在三元搜索树中插入所有后缀为：anana$,a$,$,ana$,na$,banana$,nana$。

我编写了一个程序来在三元搜索树中查找所有可能的单词以及给定字母的列表。输出是所有单词的排序集。以下是查找单词的python代码：

树包含以下单词：cat、acts、act、actor、at、bug、cats、up、actors、upper

我得到以下字母“abugpscort”的输出：

['acts', 'cats', 'cat', 'act', 'bug', 'ors', 'up', 'or', 't']

而输出应该是：

['actors', 'actor', 'acts', 'cats', 'cat', 'act', 'bug', 'up', 'at']

我怎样才能解决这个问题？

我正在尝试创建一个平衡的三元树。为此，我想以确保构建树的顺序插入键，以便每个节点均匀地划分其下方的字符范围。所以理想情况下，第一个节点是“M”，两边都是“F”和“T”，依此类推，每个键都是每个分区的中点。

我有下面的代码来完成这一点，我显然可以预先计算所有可能字符的索引并保存它，但是我想知道是否有人有更好的算术或位旋转方法来计算排序而不是查找数组。它不需要精确地在“M”上进行平衡，任何首先对中点进行排序的公平、二元递归分割都可以。

编辑：是的，如果我可以均匀地划分键而不是字母表会更好，但我在运行时添加到这棵树。

据我了解（也来自这里）这些 DS 的内存复杂性可以像 Trie > Radix > Patricia 一样排序。但是时间复杂度呢？我认为它们几乎相同。

如果要提到我的问题，我想从预先构建的字典中做很多前缀搜索查询。记忆对我来说不是一个大问题。我想用最快的DS。

HAT-trie 最适合我，但实现起来太复杂了。我应该使用三元搜索树而不是上面提到的任何 DS 吗？

非常感谢！

我正在尝试在R.

这是我试图实现的逻辑：

3^somepower通过将树的每一层指定为现有层之后的下一个单元，向量将被“分层” 。因此，第 1 层将是第一个单元，第 2 层将是第 2-4 个单元，第 3 层将是第 5-13 个单元，第 4 层将是第 14-40 个单元，第 5 层将是第 41-122 个单元，依此类推。

我希望我的代码执行以下操作：

1）取一个向量和一个obj要插入到树中的对象。在实践obj中将是一个数字。

2）如果我尝试进入的插槽已满，请根据规则跳到下一层：

2a) 如果obj不是<占用的单元格，则向下到下一层的左侧单元格，即“正下方”的三个单元格块的左侧单元格。

2b) 如果obj是==被占用的小区，则下到“正下方”的三小区块的中心小区。

2c) 如果 'obj' 是>被占用的单元格，则向下到“正下方”的三单元格块的最右边的单元格。

如果我输入数字，我画了一张我希望输出的图表34,42,15,24,16, 34,52,32,42,19,21,16,54,60,55。我包含了做某事的代码，但我不明白它在做什么。我只知道它没有做我想做的事。

谢谢你的帮助。

期望的输出：

我的代码：

这是一个面试问题：编写一个程序来为给定的一组 N 个字符串和正权重实现自动完成。也就是说，给定一个前缀和一个整数 k，在以该前缀开头的字符串中找出集合中的前 k 个字符串。

我在这里找到了一个带有三元搜索树和最大堆的建议算法：http ://www.cs.princeton.edu/courses/archive/fall13/cos226/checklist/autocomplete.html

我有点明白算法，但我不知道如何打印出前 K 个单词。我最大的困惑是：我们可以遍历树并获得所有具有最大权重的节点，但是我们如何返回并将单词放在一起？

任何帮助表示赞赏。