Нахождение ближайших интервалов в дереве интервалов, которые не содержат запрос

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

Поскольку интервалы упорядочены по нижней конечной точке, выше это просто - начиная с дыры, где будет интервал [запрос, запрос], подниматься по дереву, пока вы не достигнете родителя от его левого потомка; этот родитель является желаемым узлом.

Ниже, казалось бы, требуется проверка максимальных полей. Учитывая поддерево, содержащее только интервалы ниже запроса (т. Е. Те, чья нижняя конечная точка ниже, чем запрос), мы можем извлечь одного кандидата для ближайшего ниже, спустившись по пути, узлы которого имеют наибольшее значение max. Имеется O(log n) максимальных таких поддеревьев, по одному на каждый раз в алгоритме поиска, который мы рассматривали, идя налево, но не сделали этого. Нам также нужно проверить узлы O(log n) в исходном пути поиска. Наивно, эта идея приводит к алгоритму времени O (log² n), но если мы будем поддерживать в каждом узле указатель на один интервал, максимум которого равен максимальному для этого узла, то мы получим алгоритм времени O(log n),

Answer 2

Ява TreeMap, который реализует красно-черное дерево, реализует методы headMap и tailMap, которые возвращают части карты меньше, чем точка запроса (для headMap) или больше точки запроса (для tailMap). Если вы реализуете что-то похожее на эти методы для своего дерева, то это должно позволить вам выполнить линейный обход от точки запроса, чтобы найти N ближайших интервалов, а не обходить все дерево.