Приоритетное дерево поиска: три стороны запроса

Если механизм уже знаком - листай до «Теперь сам».

Как думаешь: что нужно сохранить

Нужно выбрать заказы с ценой не выше порога и временем в заданном интервале. Обычное дерево по времени найдёт много подходящих дат, но затем придётся отдельно отфильтровать цену. Можно ли хранить две координаты так, чтобы дешёвые точки сами открывали путь обходу? Сравни запрос с прямоугольником, где ограничены обе стороны цены: дополнительная нижняя граница меняет возможность отсечения.

На что это похоже

Представь архив: ящики разделены по датам, а на каждом лежит карточка самого дешёвого заказа из содержимого ящика. Если даже эта карточка дороже бюджета, ящик можно не открывать. Если карточка подходит, один найденный заказ уже оплачивает открытие, а даты определяют, в какие вложенные ящики вообще стоит смотреть. Карточку хранят в узле отдельно от остальных заказов, поэтому одна запись не появляется в ответе несколько раз.

Механизм: от определения к алгоритму

Построй узел по набору точек: выбери точку с минимальным x, сохрани её в узле и удали из набора. Оставшиеся раздели по медиане y на две почти равные части. Рекурсивно построй детей. Это сочетает свойство кучи x(parent)≤x(descendant) и разбиение диапазонов y. Равные y разрешай по уникальному идентификатору: дерево балансируется по полному ключу, а геометрический запрос всё равно включает все точки на граничной прямой.

Память линейна: каждая точка хранится ровно в одном узле, число указателей постоянно. Высота логарифмическая: после удаления корневой точки оставшиеся делятся примерно пополам. Простая сортировка на каждом уровне требует O(n log² n) подготовки; при предварительном упорядочении и линейном разбиении на уровнях получают O(n log n). Это разные способы построения одной структуры, не разные оценки запроса.

Для ответа ищи границы y₁ и y₂. Два граничных пути стоят O(log n). У поддеревьев, целиком попавших в диапазон y, остаётся только условие x≤limit. Если минимальный x корня больше порога, поддерево отбрасывается. Иначе выдай корневую точку и проверь детей. Каждый посещённый подходящий узел выдаёт одну точку, а каждое неподходящее поддерево останавливается на корне. Поэтому обход таких поддеревьев стоит O(1+k) суммарно, а весь запрос - O(log n+k).

Название «приоритетное» не означает порядок вывода по приоритету. Результат может идти в любом порядке. Чтобы получить точки отсортированными, понадобится дополнительная работа. Свойство минимального x используется для отсечения, а не как обещание сортировки ответа.

Правило

Храни минимум x в узле и сбалансированное разбиение по y; сначала отдели два граничных пути, затем обходи целиком подходящие поддеревья с отсечением по минимуму x.

Разбор: проследим вычисление

Ниже дерево дополнительно хранит точные нижнюю и верхнюю границы y своего поддерева. Это делает три случая видимыми: диапазон не пересекается, попал целиком, пересекается частично. Сортировка заново в каждом вызове упрощает учебную реализацию и ухудшает только построение. Сравним ответ с прямым перебором, включая две точки с одинаковым временем.

def build(points):
    if not points:
        return None
    p = min(points)
    rest = points.copy()
    rest.remove(p)
    rest.sort(key=lambda q: (q[1], q[0]))
    middle = len(rest) // 2
    left, right = build(rest[:middle]), build(rest[middle:])
    lo = min(q[1] for q in points)
    hi = max(q[1] for q in points)
    return p, lo, hi, left, right

def query(node, limit, lo, hi):
    if node is None:
        return []
    p, ymin, ymax, left, right = node
    if p[0] > limit or ymax < lo or ymin > hi:
        return []
    answer = [p] if lo <= p[1] <= hi else []
    return (answer + query(left, limit, lo, hi)
            + query(right, limit, lo, hi))

points = [(7, 1), (2, 4), (4, 4), (1, 8), (6, 6), (3, 9)]
tree = build(points)
for limit, low, high in [(4, 4, 8), (0, 0, 10), (9, 4, 4)]:
    got = sorted(query(tree, limit, low, high))
    want = sorted(p for p in points
                  if p[0] <= limit and low <= p[1] <= high)
    assert got == want
    print((limit, low, high), got)

(4, 4, 8) [(1, 8), (2, 4), (4, 4)]
(0, 0, 10) []
(9, 4, 4) [(2, 4), (4, 4)]

Разбор: где проходит граница

Пусть запрос ограничивает x ещё и снизу: L≤x≤R. Корень имеет минимальный x. Если x(root)<L, выбросить всё поддерево нельзя: ниже могут лежать значения между L и R. Теперь посещённый узел способен не выдать результат и всё же потребовать спуска к обоим детям. Прежняя оплата «один посещённый подходящий узел - одна точка ответа» перестаёт работать. Поэтому оценку трёхстороннего запроса нельзя механически переносить на четырёхсторонний.

Что ломается без этого

Если хранить одну точку одновременно в корне и дочернем наборе, ответ содержит дубликаты. Если разбивать по координате x, исчезает независимый поиск границ y. Равные координаты без правила распределения способны создать длинную цепочку вместо дерева. А если обещать линейное время выдачи без стоимости двух граничных путей, пустой ответ ошибочно выглядит бесплатным: чтобы доказать его пустоту, ещё нужно найти нужный диапазон.

Зачем это в работе

Структура подходит для запросов «дедлайн между двумя датами, цена не выше бюджета» или «событие в интервале времени, нагрузка не выше порога». Если API принимает обычные прямоугольники с четырьмя конечными границами, сначала уточни задачу: возможно, нужно дерево диапазонов или другой индекс. Особая форма запроса здесь и даёт выигрыш памяти; это полезнее запомнить, чем одно название структуры.

Теперь сам

Точки (1,2), (5,3), (2,7), (4,8). Запрос x≤4, 3≤y≤8. Какие точки выдаются и какая точка могла бы отсечь поддерево по x?