主页 / 问题 / 1166525
Accepted
John
Asked:2020-08-16 06:05:10 +0000 UTC2020-08-16 06:05:10 +0000 UTC

如何在一棵二叉搜索树中找到两个相邻的数值？

  • 772

我想了解解决问题的最简单方法。数轴上有值，需要根据请求为传入的数值找到一对现有的相邻值。在结构和输入中都不能有重复的点。

示例：在树 1、5、6、7.56、100 和输入 8 中，结果为 (7.56, 100)

还是另一种数据结构更适合这里？（要求的最大速度）

UPD：换句话说，我想出了它，但还没有实现。让我们将期望值称为 v。让我们开始寻找 v。如果最后一个值小于 v(node1)，那么您需要找到一个最小值大于 node1 (node2) 的节点。如果最后一个值大于v(node2)，那么你需要找到最大值小于node2 (node1)的节点。如果在树中找到值为 v 的节点，则报告异常。如果该对中没有值，则在响应中将其替换为 null，例如 (null,null) 或 (3,null)。

алгоритм

2 个回答

  1. Best Answer

    也许 B+ 树会比基于 CPU 缓存使用情况的二叉树更好。甚至可能比大型数组中的二进制搜索更好。

    堆位于线性/虚拟地址空间中。物理上，数据可以在处理器缓存（非常快的访问）、RAM（正常）、换出（慢）中。

    访问虚拟地址时，数据以大块（内存页（参见 TLB）和缓存块（缓存线））从慢速子系统传输到快速子系统。

    也就是说，如果你访问的是卸载页面对应的地址，那么这将是一个很长的操作。但是后续访问相邻地址会非常快。

    如果您在一个大数组中按半除法搜索，那么前几个除法可能会访问新的内存位置。对于 B+ 树，其中一个节点适合一个缓存单元，并且一个节点对子节点有很多引用，第一次搜索将在子节点数组内，然后才 - 到一个新节点；

    树的叶子包含排序数组。

    对scala中向量实现的批评，不是关于搜索，而是一般来说：

    ...缓存局部性，32路分支...比使用二叉树更快...

    https://www.lihaoyi.com/post/BenchmarkingScalaCollections.html#vectors-are-ok

    结论：向量比树好，但在很多方面比数组差。也就是说，如果数据不多，那么最好使用数组，即使考虑到粘贴时复制。

    几篇文章的摘要（我没有读过）说：

    节点大小对 Cache-Conscious B+-trees 性能的影响：

    在现代处理器中，索引结构的整体性能取决于缓存未命中的数量、执行的指令、错误预测的条件分支的数量以及 TLB 未命中的数量。

    http://pages.cs.wisc.edu/~jignesh/publ/cci.pdf

    使 B+-Trees 缓存在主内存中是有意识的：

    Cache Sensitive SearchTrees (CSS-Trees) 执行查找比二分查找快得多

    http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.444.6716&rep=rep1&type=pdf

    或者也许有一些非常专业的结构。

    一般来说，你应该试试。

    • 2

  2. 第一种方式

    平衡二叉搜索树。

    假设您知道如何在树中查找具有特定值的元素。

    让 成为X包含找到的“传入数值”的树的节点。

    至于寻找前任，这个任务难度不大：

    • 如果找到的元素有一个左子树，那么前驱是它的最大元素；换句话说，我们取左儿子并在循环中沿着节点层次结构向下，在每个级别选择右儿子，直到我们遇到叶节点：
    t = X->Left_Child;
while ( t->Right_Child != null )
{
    t = t->Right_Child;
}
return t->Value;
    • 否则（即左子树为空），我们爬上层次结构，直到找到一个键小于 X 值的节点：
    t = X->Parent;
while ( t->Value > X->Value )
{
    t = t->Parent;
}
return t->Value;

    算法的渐近线：

    • n从输入元素构建树：O(n*log(n))
    • X 搜索：O(log(n))
    • 搜索前任：O(log(n))

    我们总结，用较大的分数吸收较小的分数，得到最终的分数：

    O(n*log(n))

    第二种方式

    对有序数组进行二分查找。

    让A我们存储输入数据的排序数组。

    让X- 您需要确定前一个值的“传入数值”。

    设 为i二分查找找到的“传入数值”的索引。

    然后(i-1)将是前任的索引，前任的值为A[i-1]。

    算法的渐近线：

    • 基于比较的排序：O(n*log(n))
    • 二分查找：O(log(n))
    • 前身计算：O(1)

    我们总结，用较大的分数吸收较小的分数，得到最终的分数：

    O(n*log(n))

    优化

    是否有可能获得更好的速度？

    是的你可以！只有限制：

    • 输入的值必须在一个相对较窄的范围内，例如从 1 到 10000 的数字
    • 数据应沿最小值和最大值之间的轴相对均匀分布
    • 在第二种方法中，我们将基于比较的排序替换——我们将使用基于键值的排序（例如：计数排序和篮子排序）与线性渐近O(n)

    在这种情况下，算法的渐近线被“挤压”了：

    • 根据值排序：O(n)
    • 二分查找：O(log(n))
    • 前身计算：O(1)

    我们总结，用较大的分数吸收较小的分数，得到最终的分数：

    O(n)

    第三种方式

    是否有可能获得更快的结果？

    是和不是:)

    “不”——因为我们不能低于标准O(n)——因为 您需要读取整个输入数据。

    “是”——因为在评估中O(n)我们可以减少隐藏的常数因子！

    怎么做？好吧，既然我们已经提到了篮子排序，让我们尝试利用它的主要思想来实现我们自己的目的。

    因此，篮子排序将数轴划分为多个区间，并为每个区间创建一个“篮子”，其中添加了所有落在该区间内的值。如果一组篮子被实现为一个列表数组，并且每个篮子的大小设置为一个常量c，那么排序就变得非常简单：

    A = new int[n];  // входные данные
B = new List<int>[max(A)/c];  // набор корзин

// 1-й проход - читаем входные данные
for (i = 0; i < n; i++)
    B[A[i]/c].add(A[i]);
    
// 2-й проход - сортируем внутренности каждой корзины
for (i = 0; i < max(A)/c; i++)
    B[i].sort();

// 3-й проход (необязательный) - переписываем числа из набора корзин обратно в линейный массив A[]

    现在让我们想一想——我们需要一次对所有的篮子进行分类吗？

    正确答案是“当然不是！” :)

    我们拟定了算法的最终方案：

    • 将数字分类到篮子中
    • 我们确定所需数字所在的篮子X；这很简单 -X将值除以值c（篮子大小）；让编号为的篮子的索引X为i
    • 对第-个篮子进行排序i（如果篮子大小不变，则任何算法对其排序都视为O(1)！）
    • 二进制（甚至线性）搜索确定篮子中数字的位置X；让它在篮子内的索引是j（在篮子内搜索无论如何都会比排序这个篮子快，所以我们也把渐近线当作O(1)！）
    • 如果j > 0，那么作为响应，我们返回带有索引的篮子的值(j-1)并完成执行
    • (如果j = 0) 走到i第 - 个篮子的左边，直到我们找到一个非空的；我们在非空篮子中寻找具有最大值的元素并将其作为答案返回（同样，出于同样的原因，这一步的渐近线被视为O(1)！）

    算法的渐近线：

    • 分类成篮子：O(n)
    • 带有 item 的购物车定义X：O(1)
    • 带有元素的分类篮X：O(1)
    • 搜索最近的左侧非空篮子：（O(n) 在最坏的情况下，检查 [empty / non-empty]所有篮子，其数量是线性的）
    • 计算篮子的最大元素：O(1)

    我们总结，用较大的分数吸收较小的分数，得到最终的分数：

    O(n)

    PS：

    实际上，计数和篮子排序算法的渐近复杂度估计并不完全是O(n)，而是，输入数据值的范围O(r)在哪里，即 . 但在许多情况下（取决于输入数据），估计值可以被认为是等价的。rr = max(A) - min(A)O(n)O(r)

    此外，O(n)对于平均情况，“优化的”第二种方法（以及第三种方法）的估计是乐观的。然而，输入数据的最坏情况也是可能的，此时算法将在比线性算法更差的时间内运行。

    然而，这也发生在一些众所周知的算法中——例如，一个实施不佳的快速排序可能会因O(n*log(n))特殊O(n^2)输入数据而降级。

    • 0

相关问题