2

我正在寻找一个合适的结构来处理以下问题：

  • 应用程序正在接收（例如从 Web 服务器）可变大小数据的页面 Pi，例如页面 P1 可以包含 20 个元素，P2 3、P3 20、P4 20 等...
  • 每个页面包含具有全局唯一递减 Id j 的元素 Tj，例如 P2=[T150, T149, T120]。在此示例中，P1 Tj 元素 ID 将严格低于 120，P3 元素将严格大于 150。
  • 这意味着 Pi 中的 i 不代表网络接收顺序，而是最终的页面顺序，当我们接收到页面时它是未知的，并且在插入新页面时会发生变化。

这些页面可以按任何顺序接收。一组页面 P1..P10 的示例：

  1. 先 P3 然后 P2 然后 P1
  2. 然后 P6 然后 P5 然后 P4
  3. 然后 P10 然后 P9
  4. 然后是 P8，然后是 P7（注意 P10 和 P9 将是插入这些页面之前的第 8 页和第 9 页）。

我想找到一个允许我执行以下操作的结构：

  • 在页面序列的中间、结尾或开头的任何位置插入新页面（例如在 P9 和 P6 之间插入 P8 和 P7），因此根据内部 Tj 元素。但我正在寻找比 O(n) 更好的复杂性。
  • 删除页面也很好。
  • 有趣的部分是查询：我希望能够根据间隔进行查询：例如从第 15 个元素到第 25 个元素。在首先呈现的示例中，我将检索 P1 的最后 5 个元素 + P2 的 3 + P3 的两个第一个元素。当然，在这里，我也期待比 O(n) 更好的复杂性......

基本上，我想要实现的是在收到推文时有效地将它们存储在内存页面中（推特时间线）。我当然可以使用数组或链接列表，但这意味着 O(n) 插入和查询时间......当然我需要能够根据它们在列表中的“位置”来查询项目以显示它们在列表视图中。

我想了一些解决方案，但没有一个是合适的：

  • 首先，区间树，但它们允许插入和查询“相同范围”的元素，即插入“j”但查询“j”而不是“i”。不确定我是否可以根据“i”向它附加一种前缀总和。
  • 我想的是使用 Fenwick 树来存储项目页数的累积总和，Pi 中的 i 是树中的“位置”，它表示与值 Tj 关联的键。但是 Fenwwick 树不适合插入新元素......我想知道是否可以用红黑树实现 Fenwick 树，但我不确定......
  • 另一种解决方案可能是摆脱页面并在我猜的一种 B-tree 中直接插入元素。但是如果我想一次插入一个包含许多元素的页面，我有点担心速度。

我希望我的问题得到明确说明。关于可扩展的可能有效解决方案的任何想法？

编辑：我想查询的页面不是内部项目 ID（例如 T140、T150 或其他任何东西），而是元素（即 Tweet）索引。例如，在我的第一个示例中，T120 将是​​第 21 个项目（因为页面 P1 有 20 个元素）。所以我希望能够查询一个区间 [20-29]，它应该返回元素 [T120, ...]。我不想直接搜索120。

4

1 回答 1

2

您可以使用线程平衡二叉搜索树。但是，在搜索中，您不是根据xnode 中的单个数字检查数字，而是根据npage 来检查px页面pn。由于您的页面不重叠，这很简单。取一个您选择的 id px( ) 并对照( , )x的最小值和最大值检查它。然后：pnpn_minpn_max

if pn_min <= x <= pn_max
    the page you are looking for
if x < pn_min
    go left
if x > pn_max
    go right

为了能够检索某个范围内的 id，您首先要在树 ( x) 中找到该范围的最小值（使用普通搜索）。如果它不存在，则意味着您已经搜索到了一片叶子。调用它pn：

if x < pn_min
    start from pn
if x > pn_max
    start from pn->next

pn->next线程树中的下一个节点在哪里。现在你有了一个起始页面。只需浏览页面并检索 ID，直到达到范围的最大值。如果页面结束，请转到next线程树中的页面并继续如上。

由于树是平衡的，这应该为您O(logn)提供搜索/插入/删除操作，并且由于它是线程的，它应该在间隔查询中为您提供O(logn + k)（k给定范围内的 id 数在哪里）。

注意：您的树不需要在两个方向都有线程。GNU 的 libavl似乎有您需要的工具，但如果它更简单，或者您必须自己编写，您可以只考虑右线程树。

编辑：查询基于rth 到sth id 的范围。

稍作修改，您也可以实现这一点。该算法与查找一系列实际 id 相同，只是查找第一个元素不同。

让我们在每个节点上附加一个数字，表示该节点左侧插入了多少个 id。打电话给这个pn_before。另外，pn_size调用pn. 现在搜索rthid（这是 id 范围内的第一个[rth, sth]）如下：

passed = 0
pn = root
while pn not leaf
    if passed + pn_before < rth <= passed + pn_before + pn_size
        the node you are looking for
    if rth <= passed + pn_before
        go left
    if rth > passed + pn_before + pn_size
        passed += pn_before + pn_size
        go right

为了解释什么是passed，想象下面的树

          __________ p3 {5, 6} before: 4___________
         /                                         \
  ______p2 {2, 3, 4} before: 1              _______p5 {9}: before 2_____
 /                                         /                            \
p1 {1} before: 0                          p4 {7, 8}: before 0           p6 ...

现在假设您正在寻找第 7 个元素（在此示例中也具有 id 7）。如果您查看根 ( p3)，您会看到它前面有 4 个 id，里面有 2 个 id。因此，第 3 个如果适用，你就走对了。现在在这个新树中，您知道您已经传递了 4+2 个 id，因此您必须寻找第 1 个元素，而不是寻找第 7 个元素。该变量passed有助于跟踪当您向右时跳过了哪些 id。

或者，您可以减少pn_beforeand pn_sizefrom rth，因此rth实际上每次都会变小。它是一样的（但记得备份，rth因为你以后需要它）

一旦你找到了rth元素的位置，你就继续之前的区间查询算法。

现在唯一剩下的问题就是更新了pn_before。这很简单。由于每个子树的每个根只跟踪它的左子树，因此在插入/删除时，您需要向上到树的根并pn_before通过刚刚插入/删除的 id 数量添加/删除该节点. 记住只在你从左孩子开始的地方改变父母。如果你去找父母并且你在正确的孩子身上，父母不需要跟踪你。请注意，在这种情况下，您不应停止，因为父母可能是其父母的左孩子。

在纸上做，你会明白的；）

另一个注意事项：pn_before当你重新平衡树时要注意。

搜索再次O(logn + k)是k您查询的时间间隔内的 id 数 ( s - r)。在插入/删除中向后退到根的额外步骤不会改变这些算法的顺序，因为向后的步骤也是O(logn).

于 2013-09-17T08:30:31.717 回答