1

我已经按照 CLRS 算法书中的概述在 Java 中实现了一个区间树（它使用红黑树作为底层结构）。在书中（据我在网上看到的），它讨论了如何找到其区间包含被查询数字的节点。

在我的情况下，如果被查询的数字不属于任何区间，我想知道“最近”节点是什么，即那些区间位于查询之前和之后的节点。我已经使用以下函数完成了这项工作。每个节点都包含区间（int low, int high），以及它们自己及其子树的最小值和最大值。

public Node[] findPrevNext(int query) {
    if (tree.root.isNull())
        return null;
    else {
        Node prev = findPrev(query, tree.root, new Node());
        Node next = findNext(query, tree.root, new Node());
        Node[] result = {prev, next};
        return result;
    }
}

private Node findPrev(int query, Node x, Node prev) {
    if (x.interval.high < query && x.interval.high > prev.interval.high)
        prev = x;
    if (!x.left.isNull())
        prev = findPrev(query, x.left, prev);
    if (!x.right.isNull())
        prev = findPrev(query, x.right, prev);
    return prev;
}

private Node findNext(int query, Node x, Node next) {
    if (x.interval.low > query && x.interval.low < next.interval.low)
        next = x;
    if (!x.left.isNull())
        next = findNext(query, x.left, next);
    if (!x.right.isNull())
        next = findNext(query, x.right, next);
    return next;
}

当然，问题在于函数 findPrev() 和 findNext() 都遍历整个树并且没有利用树的结构。有没有办法在 O(lgn) 时间内执行此查询？

我还考虑了创建第二个包含所有间隔间隙的间隔树的可能性，并在那里简单地进行查询。然后，节点将包含有关哪些元素在该间隙之前和之后的信息（我已经尝试过，但到目前为止还没有成功实现这一点）。

编辑：请注意，函数 findPrevNext() 在尝试查找查询失败后被调用。因此，已知查询不会事先落在任何给定的时间间隔内。

4

2 回答 2

1

由于区间是按低端点排序的，所以上面很简单——从区间 [query, query] 所在的洞开始，向上爬树，直到从左子节点到达父节点；该父节点是所需的节点。

下面似乎需要检查最大字段。给定一棵只包含查询下方区间的子树（即下端点低于查询的那些），我们可以通过在其节点具有最大值 max 的路径上递减来提取一个最近的候选。这样的子树最多有 O(log n) 个，在我们考虑向左但没有向左的搜索算法中，每次都有一个。我们还需要检查原始搜索路径上的 O(log n) 个节点。天真地，这个想法导致了一个 O(log 2 n) 时间的算法，但是如果我们在每个节点上维护一个指向一个区间的指针，该区间的高等于该节点的最大值，那么我们得到一个 O(log n) 时间的算法.

于 2013-05-15T04:10:02.567 回答
0

JavaTreeMap实现了红黑树，实现了headMap和tailMap方法，它们返回小于查询点 (for headMap) 或大于查询点 (for tailMap) 的地图部分。如果您为您的树实现与这些方法类似的东西，那么这应该允许您从查询点进行线性遍历以找到 N 个最接近的间隔，而不必遍历整个树。

于 2013-05-14T20:46:36.780 回答