Сверхбыстрый цифровой бор

Цифровой бор

Работаем с целыми числами, которые представляются с помощью w битов, аналогично дереву Ван Эмде Боаса. Мы можем их складывать, вычитать, умножать, сдвигать, производить с ними логические операции, адресоваться ими. В модели памяти unit cost RAM, которая сейчас применима к большинству процессоров, эти операции могут быть выполнены за О(1).

Цифровой бор — бор, в котором в качестве строк используются двоичные записи чисел, включая ведущие нули. Таким образом он имеет глубину w.

Цифровой бор поддерживает операции insert, remove, find, succ, pred.

Добавление вершины происходит так же, как и в обычном боре. Удаление можно выполнять лениво - просто убирая пометку с листа. А можно хранить число пометок в поддереве и удалять вершину, если это число стало равным нулю. Поиск следующего элемента осуществляется проходом от корня до вершины, из которой не можем пойти в нужную сторону. Если не смогли пойти влево (по ребру 0), то ответ - минимум в правом поддереве. Если не смогли пойти вправо, поднимаемся наверх, пока являемся правым ребенком, если стали левым, то поднимаемся, пока у вершины нет правого ребенка (если такой ситуации нет, то запрос больше всех элементов). Тогда ответ - минимум в правом поддереве.

Простая реализация, занимает O(n * w) памяти (например, когда в боре хранятся два числа — w нулей и w единиц, получаем O(2*w)), все операции выполняются за O(w). Хуже дерева Ван Эмде Боаса по скорости, но памяти занимает меньше.

Быстрый цифровой бор (x-fast-trie)

Он по-прежнему будет занимать O(n * w) памяти, но немодифицирующие операции (read-only) будут выполняться за O(log w).

Улучшим структуру: было два слабых места — подниматься вверх и искать минимум.

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

Вторая модификация - добавим ссылки. Операции поиска минимума и максимума дорогие, выполним их за О(1). Теперь становится понятно, что необязательно спускаться до минимума или максимума в дереве. Если у вершину нет левого сына (отметим одним битом) вместо ссылки на левого сына сделаем ссылку на минимум в правом поддереве, что удобно для нашей реализации succOrPred. Если нет правого сына, то храним ссылку на максимум в левом поддереве.

При вставке с помощью succOrPred и двусвязного списка находим следующий и предыдущий элементы и вставляем нужный элемент между ними. А также при создании новой вершины(у которой будет только один ребенок) на обратном пути рекурсии заменяем ссылки. Удаление происходит аналогично. Вставка и удаление выполняются за O(w).

Пока что мы не добились асимптотического выигрыша - все операции по-прежнему выполняются за О(w). Теперь слабое место - это поиск наибольшего общего префикса. Будем искать его двоичным поиском. Для этого занесём префиксы всех чисел в HashMap - ассоциативный массив, который по префиксу возвращает вершину в боре (чтобы избежать проблемы с ведущими нулями, используем при поиске маску вида 0..01..1). Запустим двоичный поиск по длине наибольшего общего префикса. Как только он вернет максимальный префикс, переходим в вершину(у этой вершины не может быть два сына, так как тогда поиск бы не завершился) и там за О(1) находим минимум или масимум, и за О(1) переходим по списку, если нужно. Итого операции find, succ и pred будут выполняться за O(log w).

Сверхбыстрый цифровой бор (y-fast-trie)

Теперь усовершенствуем x-fast-trie до y-fast-trie, который занимает O(n) памяти, а все операции выполняются за O(log w), правда, для модифицирующих операций эта оценка будет амортизированной.

Уменьшим количество занимаемой памяти. Пусть a_1 < a_2 < a_3 < ... < a_n - числа, которые нужно хранить в боре. Выберем какое-то k (что за k - будет видно дальше). Разобьём их на s блоков размером от k/2 до 2k, а точнее B_{11} < B_{12} < ... < B_{1n1} < B_{21} < B_{22} < ... < B_{2n2} < ... < B_{s1} < B_{s2} < ... < B_{sns} Выберем в каждом блоке какого-нибудь представителя. И поместим этих представителей в x-fast-trie. Всего в x-fast-trie будет O(2 * n * w / k) элементов. Поэтому если выбрать k = \theta(w), то x-fast-trie будет занимать O(n) памяти.

Каждый лист x-fast-trie является представителем блока, а все остальные элементы блока (в т. ч. и представителя) подвесим к листу как сбалансированное двоичное дерево поиска. В дереве может храниться от w/2 До 2 * w элементов, поэтому его высота - O(log w).

Все деревья поиска занимают O(n) памяти, и x-fast-trie – O(n) памяти. Поэтому y-fast-trie тоже занимает O(n) памяти.

find

Находим succ = x среди представителей в x-fast-trie, а потом запускаем поиск succ(x) в дереве, подвешенном к листу x, а также в дереве, подвешенном к листу pred(x) среди представителей в x-fast-trie. Представителем дерева является необязательно минимальный или максимальный элемент, поэтому нужно запустить в двух деревьях. Заметим, что мы ищем элемент только в двух деревьях, так как искомый элемент точно находится между своим сакцессором и прецессором.

O(log w) на поиск в x-fast-trie и O(log w) на поиск в деревьях поиска, поэтому итогая асимптотика - O(log w).

succ & pred выполняются аналогично.

insert

Вставка элемента x происходит следующим образом: найдём succ(x) и вставим его в подвешенное к листу дерево. Но может возникнуть плохая ситуация: размер дерева станет 2 * w + 1. Тогда поступим следующим образом - удалим наше дерево из x-fast-trie, разделим его на элементы, из которых построим два дерева размером w и w + 1, и вставим в x-fast-trie их оба. АВЛ-деревья или красно-чёрные позволяют выполнять слияние за линейное время, поэтому операция вставки выполняется за O(w).

delete

Удаление происходит аналогично, только если размер дерева станет w/2 - 1, то надо его слить с любым соседним деревом. А если после слияния размер получившегося дерева станет больше 2 * w, то надо его разделить аналогично предыдущему случаю.

Ассимптотика

Заметим, что вставка, которая не модифицирует верхний бор, выполняется за истинный log(w), также и succ, pred. Плохие операции — которые модифицируют верхний бор. Но они не происходят слишком часто, так как после каждой операции слияния/разделения деревья оказываются на расстоянии Theta(w) от границ. Худший случай — было: w/2 и 2*w, - стало: 5w/4 и 5w/4. В нижнее дерево должно произойти порядка w вставок и удалений, чтобы оно с чем-то слилось или разделилось. Применим амортизационный анализ. Копим деньги на дешевых операциях — берем столько монет, какое расстояние до края. Скопим их достаточно, чтобы расплатиться за преобразование верхнего дерева. Получаем амортизированную оценку O(log(w)) и истинную - O(w).

Здесь не имеет смысла использовать сливаемые деревья поиска, так как после слияния/разделения все равно нужно можифицировать верхний бор. Получилась та же оценка на операции, что и у Ван Эмде Боаса, но структура данных занимает O(n) памяти.