我最近听说过三元搜索，我们将一个数组分成 3 个部分并进行比较。这里将进行两次比较，但它将数组减少到 n/3。为什么人们不使用这么多？
问问题
20482 次
15 回答
44
实际上，人们确实使用 k-ary 树来表示任意 k。
然而，这是一个权衡。
要在 k-ary 树中查找元素，您需要大约 k*ln(N)/ln(k) 操作（请记住基数变化公式）。您的 k 越大，您需要的整体操作就越多。
您所说的逻辑扩展是“为什么人们不对 N 个数据元素使用 N 叉树？”。当然，这将是一个数组。
于 2010-08-17T00:14:20.747 回答
26
三元搜索仍会为您提供相同的渐近复杂度O(log N)搜索时间，并增加实现的复杂性。
可以说相同的论点来解释为什么您不想要四边形搜索或任何其他更高阶。
于 2010-08-17T00:12:48.067 回答
25
搜索 10 亿个（十亿美元 - 1,000,000,000）个已排序的项目，与二分搜索相比平均需要大约 15 次，而与三元搜索相比大约需要 9 次 - 这不是一个巨大的优势。请注意，每个“三元比较”可能涉及 2 个实际比较。
于 2010-08-17T00:19:31.650 回答
10
哇。我认为，投票最多的答案错过了这艘船。
您的 CPU 不支持将三元逻辑作为单个操作；它将三元逻辑分解为二进制逻辑的几个步骤。CPU 的最佳代码是二进制逻辑。如果芯片很常见，支持三元逻辑作为单一操作，那你是对的。
B-Trees 在每个节点上可以有多个分支；3 阶 B 树是三元逻辑。树的每一步都会进行两次比较而不是一次，这可能会导致它在 CPU 时间上变慢。
然而，B-Trees 很常见。如果您假设树中的每个节点都将单独存储在磁盘上的某个位置，那么您将花费大部分时间从磁盘读取...... CPU 不会成为瓶颈，但磁盘会。因此，您采用每个节点有 100,000 个子节点的 B 树，或者任何其他几乎不适合一块内存的东西。具有这种分支因子的 B 树的高度很少会超过三个节点，并且您只有三个磁盘读取（在瓶颈处停止三个站点）来搜索一个巨大的、巨大的数据集。
审查：
- 硬件不支持三叉树，因此它们的运行速度较慢。
- 阶数远高于 3 的 B-tress 常用于大型数据集的磁盘优化；超过 2 后，请高于 3。
于 2010-08-19T19:56:05.760 回答
8
是什么让您认为三元搜索应该更快？
平均比较次数：
in ternary search = ((1/3)*1 + (2/3)*2) * ln(n)/ln(3) ~ 1.517*ln(n)
in binary search = 1 * ln(n)/ln(2) ~ 1.443*ln(n).
最差比较次数：
in ternary search = 2 * ln(n)/ln(3) ~ 1.820*ln(n)
in binary search = 1 * ln(n)/ln(2) ~ 1.443*ln(n).
所以看起来三元搜索更糟糕。
于 2010-08-17T01:03:36.073 回答
8
三元搜索比二分搜索更快的唯一方法是，如果可以以不到大约 1.55 倍的 2 路比较成本来确定 3 路分区确定。如果项目存储在排序数组中，则 3 路确定的平均成本将是 2 路确定的 1.66 倍。但是，如果信息存储在树中，则获取信息的成本相对于实际比较的成本较高，并且缓存局部性意味着随机获取一对相关数据的成本并不比获取单个数据的成本差多少datum，三叉树或n路树可以大大提高效率。
于 2010-08-17T02:09:26.463 回答
5
另外，请注意，如果我们继续，这个序列可以推广到线性搜索
Binary search
Ternary search
...
...
n-ary search ≡ linear search
因此，在 n 元搜索中，我们将有“one only COMPARE”，这可能需要多达 n 次实际比较。
于 2010-08-17T04:48:47.380 回答
2
“三元”（三元？）搜索在最好的情况下更有效，这将涉及搜索第一个元素（或者可能是最后一个元素，具体取决于您首先进行的比较）。对于距离末端较远的元素，您首先要检查，虽然两次比较每次都会将数组缩小 2/3，但与二分搜索相同的两次比较会将搜索空间缩小 3/4。
除此之外，二分查找更简单。你只是比较并得到一半或另一个，而不是比较，如果小于得到第一个三分之一，否则比较，如果小于得到第二个三分之一，否则得到最后三分之一。
于 2010-08-17T00:17:50.337 回答
2
三元搜索可以有效地用于并行架构 - FPGA 和 ASIC。例如，如果搜索所需的内部 FPGA 内存小于 FPGA 资源的一半，您可以制作一个重复的内存块。这将允许同时访问两个不同的内存地址并在单个时钟周期内进行所有比较。这就是为什么 100MHz FPGA 有时可以胜过 4GHz CPU 的原因之一 :)
于 2013-05-29T19:55:48.880 回答
1
这是一些我根本没有审查过的随机实验证据，表明它比二分搜索慢。
于 2010-08-17T00:13:53.367 回答
1
几乎所有关于二叉搜索树的教科书和网站都没有真正谈论二叉树！他们向您展示了三元搜索树！真正的二叉树将数据存储在其叶子而不是内部节点中（导航键除外）。有些人称这些叶子树，并区分教科书中显示的节点树：
J. Nievergelt，C.-K。Wong：二叉树总路径长度的上限，ACM 杂志 20 (1973) 1-6。
以下内容来自 Peter Brass 关于数据结构的书。
2.1 两种搜索树模型
在刚刚给出的大纲中，我们隐藏了一个重要的点，这个点乍一看似乎微不足道，但实际上它导致了两种不同的搜索树模型，其中任何一种都可以与以下大部分材料结合，但其中一种更可取。
如果我们在每个节点中将查询键与节点中包含的键进行比较，如果查询键较小则沿着左分支，如果查询键较大则沿着右分支，那么如果它们相等会发生什么？两种搜索树模型如下：
如果查询键小于节点键，则取左分支；否则取右分支，直到你到达树的叶子。树的内部节点中的键仅用于比较；所有的物体都在叶子里。
如果查询键小于节点键，则取左分支；如果查询键大于节点键，则取右分支；如果它们相等，则取节点中包含的对象。
这个小问题有很多后果：
{ 在模型 1 中，底层树是二叉树，而在模型 2 中，每个树节点实际上是具有特殊中间邻居的三元节点。
{ 在模型 1 中，每个内部节点都有一个左子树和一个右子树（每个都可能是树的一个叶节点），而在模型 2 中，我们必须允许不完整的节点，其中左子树或右子树可能会丢失，并且只有比较对象和键保证存在。
所以模型 1 的搜索树的结构比模型 2 的树结构更规则；至少对于实施而言，这是一个明显的优势。
{ 在模型 1 中，遍历一个内部节点只需要一次比较，而在模型 2 中，我们需要两次比较来检查三种可能性。
实际上，模型 1 和模型 2 中相同高度的树最多包含大约相同数量的对象，但是在模型 2 中需要两倍的比较才能到达树的最深对象。当然，在模型 2 中，也有一些更早到达的对象；仅通过两次比较即可找到根中的对象，但几乎所有对象都在最深层次上或附近。
定理。高度为 h 且模型 1 的树最多包含 2^h 个对象。高度为 h 和模型 2 的树最多包含 2^h+1 - 1 个对象。
这很容易看出，因为高度为 h 的树作为左子树和右子树，每个树的高度最多为 h-1，并且在模型 2 中，它们之间还有一个附加对象。
{ 在模型 1 中，内部节点中的键仅用于比较，并且可能重新出现在叶子中以识别对象。在模型 2 中，每个键及其对象仅出现一次。
在模型 1 中，甚至有可能用于比较的键不属于任何对象，例如，如果对象已被删除。通过在概念上分离这些比较和识别的功能，这并不奇怪，在以后的结构中，我们甚至可能需要定义不对应任何对象的人工测试，只是为了很好地划分搜索空间。用于比较的所有键都必须是不同的，因为在模型 1 树中，每个内部节点都有非空的左子树和右子树。所以每个键最多出现两次，一次作为比较键，一次作为叶子中的标识键。
模型 2 成为首选的教科书版本，因为在大多数教科书中没有区分对象和它的键：键就是对象。然后在树结构中复制键变得不自然。但在所有实际应用中，key 和 object 之间的区别是相当重要的。人们几乎从不希望只跟踪一组数字。这些数字通常与一些进一步的信息相关联，这些信息通常比密钥本身大得多。
于 2014-09-13T16:42:04.907 回答
0
您可能听说过在那些涉及在秤上称重的谜语中使用了三元搜索。那些秤可以返回 3 个答案：左边更轻，两者相同，或者左边更重。所以在三元搜索中，只需要 1 次比较。但是，计算机使用布尔逻辑，它只有 2 个答案。要进行三元搜索，您实际上必须进行 2 次比较而不是 1 次。我想在某些情况下，这仍然比之前的海报提到的更快，但您可以看到三元搜索并不总是更好，而且在计算机上实现更令人困惑且更不自然。
于 2010-08-17T05:22:58.623 回答
0
从理论上讲，在ek/ln(k)处达到最小值，并且由于 3 比 2 更接近e，因此需要较少的比较。您可以检查一下，并且二进制搜索可以更快的原因是它的代码将具有更少的分支并且将在现代 CPU 上运行得更快。3/ln(3) = 2.73..2/ln(2) = 2.88..
于 2010-08-18T20:48:06.707 回答
0
尽管您在两个搜索树中得到相同的大 O 复杂度 (ln n)，但区别在于常量。您必须对每个级别的三元搜索树进行更多比较。因此，对于 k 元搜索树，差异归结为 k/ln(k)。这在 e=2.7 处具有最小值，并且 k=2 提供了最佳结果。
于 2015-10-29T01:22:34.557 回答