Деревья поиска

Этот раздел обобщает материалы практических заданий (а именно, «домашнего задания №3»). Структура данных, в нём рассмотренная, является, по-видимому, самой распространённой иерархической структурой данных: различные её вариации встречаются повсеместно и используются для решения самых разных практических задач.

Геометрические запросы и алгебра регионов

Представим себе типичный запрос к базе данных: найти количество всех людей мужского пола старше 17 лет. Этот запрос можно охарактеризовать прямоугольником \([1,1]\times[18,+\infty]\) в двухмерном целочисленном пространстве.

Подобные запросы почти всегда имеют некую геометрическую интерпретацию, которую можно продуктивно эксплуатировать для эффективной реализации ответа на такой запрос. Соответственно, возникает естественный вопрос о том, как математически моделировать геометрический аспект таких запросов.

Ключевым «геометрическим» инструментом является отношение «фигура \(A\) является частью фигуры \(B\)». Мы будем это кратко записывать как \(A\subset B\). От такого отношения мы ожидаем как минимум следующих свойств:

каждая фигура является своей частью: \(A\subset A\)
часть части — часть: из \(A\subset B\subset C\) следует \(A\subset C\)
часть своей части — эта самая часть: из \(A\subset B\subset A\) следует \(A=B\)

Такие отношения называются отношениями (частичного) порядка. Числовые нестрогие неравенства, делимость, теоретико-множественное вложение, логическое следование — четыре самых распространённых примера частичных порядков. Из них наиболее соответствует геометрической интуиции теоретико-множественное вложение, но на практике оно довольно бесполезно: его трудно эффективно моделировать. Тем не менее, всю последующую терминологию мы позаимствуем именно у него.

Договоримся те объекты, на множестве которых мы будем рассматривать отношение «быть частью» называть регионами. Будем говорить, что регион \(A\) является объединением регионов \(A_i\), если:

для всех \(i\) выполнено \(A_i\subset A\)
если для всех \(i\) выполнено \(A_i\subset B\), то \(A\subset B\)

Проще говоря: объединение — наименьший регион, содержащий объединяемые регионы. Это же понятие можно встретить под названиями: максимум и точная верхняя грань (для числовых неравенств), наименьшее общее кратное (для делимости), дизъюнкция и квантор существования (в логике). Обозначается объединение так: \(A=\cup_i A_i\).

Аналогично определяется пересечение:

для всех \(i\) выполнено \(A_i\supset A\)
если для всех \(i\) выполнено \(A_i\supset B\), то \(A\supset B\)

Нетрудно угадать, что это понятие также носит названия: минимум, точная нижняя грань, наибольший общий делитель, конъюнкция, квантор общности. Обозначается пересечение знаком \(\cap\).

Объединение пустого набора регионов (регион, являющийся частью любого региона) будем называть пустым. Часто также можно встретить термин низ (bottom) и обозначение \(\bot\). Пересечение пустого набора регионов традиционно называется верх (top) и обозначается \(\top\), но нам оно не понадобится.

Интересен тот факт, что отношение «быть частью» выражается в терминах операций, им порождённых. А именно, высказывание \(A\subset B\) эквивалентно любому из следующих:

\(A\cap B = A\)
\(A\cup B = B\)

Хотя мы и определили пересечение регионов, оно нам дальше не понадобится. А понадобится следующее:

операция объединения набора регионов
отношение равенства регионов или же отношение «быть частью»
подмножество (его элементы будем называть точками) множества всех регионов
отношение раздельности регионов

Будем требовать, чтобы каждая точка была непуста и не содержала ничего, кроме себя и пустого региона (аналог точек в порядке делимости — простые числа).

Отношение раздельности определим так: регионы раздельны, если их пересечение не содержит ни одной точки (это отличается от непересекающихся регионов: мы не обязаны объявлять любой «простой» регион точкой).

Указанные четыре вещи мы будем моделировать функциями:

join(regions)  ## на вход -- список регионов
contains(a,b)  ## a содержит b
point(p)       ## на вход -- "метка" точки
disjoint(a,b)  ## a и b раздельны

Функция point разделяет типы данных «точка как регион» и «точка как вещь-в-себе». А именно, она преобразует второе в первое. Справедливости ради, более идиоматическим для динамически типизированных языков (каковым является Python) была бы функция is_point(region), проверяющая, является ли входной регион точкой. Но для рассматриваемой нами задачи point гораздо полезнее: например, преобразование \((x\mapsto [x,x])\), сопоставляющее точке числовой прямой отрезок, состоящий только из этой точки, — типичный пример функции point. Такие преобразования нам придётся делать. А вот проверять, является ли результат такого преобразования точкой-как-регионом, уже не понадобится, так как ответ заранее известен.

Дерево регионов

Дерево регионов — дерево, у которого в каждом узле (будь то лист или ветка) хранится регион (вместе с какой-либо дополнительной информацией), причём регион ветки является объединением регионов поддеревьев.

Как было сказано ранее, основное назначение дерева регионов — эффективно выполнять геометрические запросы. Заметим, что пока мы так и не формализовали понятие геометрического запроса. Исправляемся:

## на вход -- список пар (точка,значение)
def query_list(region, pv):
    good = [v for (p,v) in pv 
              if contains(region,point(p))]
    return combine(good)

Это определение зависит от функции combine. Будем считать, что она нам также дана. От неё мы будем требовать лишь ассоциативности. Это означает, что если разбить входной список на несколько (с сохранением относительного порядка элементов), применить к каждому combine, а затем применить combine к списку результатов, получится то же самое, как если бы combine была применена к исходному списку. Формально это означает, что равны результаты следующих двух формул:

combine([combine(x) for x in xs])
combine([y for x in xs for y in x])

Также встречается свойство combine([x]) == x, которое часто включают в понятие ассоциативности. Нам же будет удобно не требовать его выполнения. Например, операция «сложить все входные числа по модулю 42» с нашей точки зрения является ассоциативной.

Задача эффективного выполнения геометрического запроса состоит в реализации пары таких функций

preprocess(pv)
query(region,data)

что выполнено

query_list(region,pv) == query(region,preprocess(pv))

Будем считать, что мы достигли цели, если

data = preprocess(pv)
for i in range(N): query(r[i],data)

начиная с некоторого N выполняется быстрее, чем

for i in range(N): query_list(r[i],pv)

В идеале сделать так, чтобы первый пример тратил в среднем (на одну итерацию цикла) время, пропорциональное логарифму количества данных.

Построение дерева сверху и снизу

Зададимся некоторой моделью дерева с функцией extract, которая по своему результату эквивалентна следующему определению:

def extract(t):
    return reduce(t, lambda x: x, lambda x,y: x)
## _именно такое_ определение неэффективно из-за того, 
## что reduce проходится по поддеревьям, хотя они вообще 
## не влияют на результат

Дерево регионов строится очень просто. Либо рекурсией (это называется «сверху вниз»):

def combine_trees(trees):
    region = join([extract(t)[0] for t in trees])
    val = combine([extract(t)[1] for t in trees])
    
    return branch( (region,val), trees )
    

def topdown_tree(b,l,pv):
    if len(pv) <= l:
        trees = [leaf( (point(p),v) ) for (p,v) in pv]
    else:
        d = (len(pv)+b-1) // b
        trees = [topdown_tree(b,l,pv[i:i+d]) for i in range(0,len(pv),d)]
    
    return combine_trees(trees)

Либо же циклом («снизу вверх»):

def bottomup_tree(b,l,pv):
    if len(pv) == 0: return combine_trees([])

    leaves = [leaf( (point(p),v) ) for (p,v) in pv]

    trees = [combine_trees(leaves[i:i+l]) for i in range(0,len(pv),l)]
    
    while len(trees) > 1:
        trees = [combine_trees(trees[i:i+b]) for i in range(0,len(trees),b)]

    return trees[0]

На практике чаще встречается первый способ: если операция combine коммутативна (то есть её результат не зависит от порядка элементов в списке), то засчёт правильного распределения точек по регионам можно добиться маленького размера их пересечений (что, как мы увидим ниже, сильно убыстряет запросы). Управлять же распределением, строя дерево снизу вверх, сильно труднее, чем при построении сверху вниз (особенно легко это увидеть в многомерных пространствах: такие структуры как квадродерево или же бинарное разбиение пространства тривиально строятся сверху вниз, но совершенно непонятно на первый взгляд, как их строить снизу вверх).

Геометрический запрос к дереву

Нам понадобится функция subtrees, возвращающая список поддеревьев входного дерева (у листа он пустой). Формальное определение для абстрактных деревьев приводить не будем, поскольку одним катаморфизмом здесь не обойтись (нужно катаморфно преобразовать дерево к удобной модели, в ней взять поддеревья, каждое из которых катаморфизмом этой самой удобной модели преобразовать обратно к абстрактной).

В свете всего предыдущего геометрический запрос к дереву регионов совершенно тривиален:

def query_tree(region, tree):
    r,v = extract(tree)

    if contains(region,r): return v
    if disjoint(region,r): return combine([])

    return combine([query_tree(region, t) for t in subtrees(tree)])

Дерево отрезков

Дерево отрезков является модификацией дерева минимумов из предыдущего раздела. Оно является деревом регионов для следующего набора операций:

def join(segments):
    nonempty = [s for s in segments if s != None]
    if len(nonempty) == 0: return None

    a = min([x for (x,y) in nonempty])
    b = max([y for (x,y) in nonempty])

    return (a,b)

def contains(a,b): return join([a,b]) == a

def point(x): return (x,x)

def disjoint(a,b): 
    if a == None or b == None: return True
    
    a1,a2 = a
    b1,b2 = b
    return b2 < a1 or a2 < b1

Идеальная для дерева отрезков ситуация: когда входные данные упорядочены по своим точкам. В такой ситуации любой запрос потенциально может спуститься до низа дерева не более двух раз: это свойство как раз обеспечивает логарифмическую по количеству входных данных сложность геометрического запроса.

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

Обобщённые запросы и динамизация

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

def remove_from_tree(region, tree):
    r,v = extract(tree)

    if contains(region,r): return None
    if disjoint(region,r): return tree

    trees = [remove_from_tree(region, t) for t in subtrees(tree)]
    return combine_trees([t for t in trees if t != None])

Как нетрудно заметить, что эта функция, что функция query являются частными случаями более общей схемы:

def gquery_tree(f,g,c,region,tree):
    r,v = extract(tree)
    
    if contains(region,r): return f(tree)
    if disjoint(region,r): return g(tree)

    return c([gquery(f,g,c,region, t) for t in subtrees(tree)])

А именно, можно использовать следующие альтернативные определения:

def query_tree(region, tree):
    return gquery_tree(lambda t: extract(t)[1], lambda t: combine([]), combine)

def remove_from_tree(region, tree):
    def combine_nonempty(ts):
        return combine_trees([t for t in ts if t != None])

    return gquery_tree(lambda t: None, lambda t: t, combine_nonempty)

Но мы отвлеклись: изначально мы обсуждали проблему динамизации статического дерева. Удалять данные мы научились. Ну а добавлять, на самом деле, уже умели.