algorithm - 在不包含查询的区间树中查找最接近的区间

Question

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

在我的例子中，如果被查询的数字不属于任何区间，我想知道“最近”的节点是什么，即那些区间在查询之前和之后的节点。我使用以下功能完成了此操作。每个节点包含区间(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() 在尝试查找查询失败后被调用。因此，事先知道查询不会落入任何给定的区间内。

Answer 1

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

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