Сверхбыстрый цифровой бор — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 60 промежуточных версий 7 участников)
Строка 1: Строка 1:
 
==Цифровой бор==
 
==Цифровой бор==
Работаем с целыми числами, которые представляются с помощью w битов, аналогично дереву Ван Эмде Боаса. Мы можем их складывать, вычитать, умножать, сдвигать, производить с ними логические операции, адресоваться ими. В модели памяти unit cost RAM, которая сейчас применима к большинству процессоров, эти операции могут быть выполнены за О(1).
+
Работаем с целыми числами, которые представляются с помощью <tex>w</tex> битов, аналогично [[Дерево ван Эмде Боаса | дереву Ван Эмде Боаса]]. Мы можем их складывать, вычитать, умножать, сдвигать, производить с ними логические операции, адресоваться ими. В модели памяти <tex>\mathrm{unit~cost~RAM}</tex>, которая сейчас применима к большинству процессоров, эти операции могут быть выполнены за <tex>O(1)</tex>.
  
Цифровой бор [[Бор | бор]], в котором в качестве строк используются двоичные записи чисел, включая ведущие нули.
+
'''Цифровой бор''' {{---}} [[Бор | бор]], в котором в качестве строк используются двоичные записи чисел, включая ведущие нули.
Таким образом он имеет глубину w.
+
Таким образом он имеет глубину <tex>w</tex>.
  
Цифровой бор поддерживает операции insert, remove, find, succ, pred.  
+
Цифровой бор поддерживает операции <tex>\mathrm{insert},\ \mathrm{remove},\ \mathrm{find},\ \mathrm{succ},\ \mathrm{pred}</tex>.  
  
 
Добавление вершины происходит так же, как и в обычном боре.
 
Добавление вершины происходит так же, как и в обычном боре.
Удаление можно выполнять лениво - просто убирая пометку с листа. А можно хранить число пометок в поддереве и удалять вершину, если это число стало равным нулю.
+
Удаление можно выполнять лениво {{---}} просто убирая пометку с листа. А можно хранить число пометок в поддереве и удалять вершину, если это число стало равным нулю.
  
 
===succ===
 
===succ===
Поиск следующего элемента осуществляется проходом от корня до вершины, из которой не можем пойти в нужную сторону. Если не смогли пойти влево (по ребру 0), то ответ - минимум в правом поддереве. Если не смогли пойти вправо, поднимаемся наверх, пока являемся правым ребенком, если стали левым, то поднимаемся, пока у вершины нет правого ребенка (если такой ситуации нет, то запрос больше всех элементов). Тогда ответ - минимум в правом поддереве.
+
Поиск следующего элемента осуществляется проходом от корня до вершины, из которой не можем пойти в нужную сторону. Если не смогли пойти влево <tex>(</tex>по ребру <tex>0)</tex>, то ответ {{---}} минимум в правом поддереве. Если не смогли пойти вправо, поднимаемся наверх, пока являемся правым ребенком; если стали левым, то поднимаемся, пока у вершины нет правого ребенка (если такой ситуации нет, то запрос больше всех элементов). Тогда ответ {{---}} минимум в правом поддереве.
 +
 
 +
Преимущества: простая реализация, занимает <tex>O(n \cdot w)</tex> памяти, все операции выполняются за <tex>O(w)</tex>.
  
Преимущества: простая реализация, занимает O(n * w) памяти, все операции выполняются за O(w).
 
 
Хуже дерева Ван Эмде Боаса по скорости, но памяти занимает меньше.
 
Хуже дерева Ван Эмде Боаса по скорости, но памяти занимает меньше.
  
 
==Быстрый цифровой бор (x-fast-trie)==
 
==Быстрый цифровой бор (x-fast-trie)==
Он по-прежнему будет занимать O(n * w) памяти, но немодифицирующие операции (read-only) будут выполняться за O(log w).
+
[[File:Tsifrovoybor.jpg|thumb|500px|x-fast-trie]]
 +
[[File:Min amp amp max.jpg|thumb|right|500px|Ссылки на минимум и максимум]]
 +
Он по-прежнему будет занимать <tex>O(n \cdot w)</tex> памяти, но немодифицирующие операции <tex>(read{-}only)</tex> будут выполняться за <tex>O(\log w)</tex>.  
  
Улучшим структуру: было два слабых места подниматься вверх и искать минимум.
+
Улучшим структуру: было два слабых места {{---}} подниматься вверх и искать минимум.
  
 
===succOrPred===
 
===succOrPred===
Первая модификация - занесем все элементы  в двусвязный список в порядке, в котором они лежат в боре. Добавим операцию succOrPred, которая возвращает следующий или предыдущий в зависимости от того, что проще. Спускается вниз до наибольшего общего префикса, а потом до минимума в правом дереве или же до максимума в левом. Тогда мы получим какой-то элемент списка и не более чем за два шага сможем получить ответ на запрос.
+
Первая модификация {{---}} занесем все элементы  в двусвязный список в порядке, в котором они лежат в боре. Добавим операцию <tex>\mathrm{succOrPred}</tex>, которая возвращает следующий или предыдущий в зависимости от того, что проще. Работает она так: спускается вниз до наибольшего общего префикса, а потом до минимума в правом дереве или же до максимума в левом. Тогда мы получим какой-то элемент списка и не более чем за два шага в списке сможем получить ответ на запрос.
  
Вторая модификация - добавим ссылки.
+
Вторая модификация {{---}} добавим ссылки.
Операции поиска минимума и максимума дорогие, выполним их за О(1). Теперь становится понятно, что необязательно спускаться до минимума или максимума в дереве. Если у вершину нет левого сына (отметим одним битом) вместо ссылки на левого сына сделаем ссылку на минимум в правом поддереве, что удобно для нашей реализации succOrPred. Если нет правого сына, то храним ссылку на максимум в левом поддереве.
+
Операции поиска минимума и максимума дорогие, выполним их за <tex>O(1)</tex>. Теперь становится понятно, что необязательно спускаться до минимума или максимума в дереве. Если у вершины нет левого сына, отметим это одним битом, а вместо ссылки на левого сына сделаем ссылку на минимум в правом поддереве, что удобно для нашей реализации <tex>\mathrm{succOrPred}</tex>. Если нет правого сына, то храним ссылку на максимум в левом поддереве.  
  
 
===insert===
 
===insert===
При вставке с помощью succOrPred и двусвязного списка находим следующий и предыдущий элементы и вставляем нужный элемент между ними. А также при создании новой вершины(у которой будет только один ребенок) на обратном пути рекурсии заменяем ссылки.
+
При вставке с помощью <tex>\mathrm{succOrPred}</tex> и двусвязного списка находим следующий и предыдущий элементы и вставляем нужный элемент между ними. А также при создании новой вершины (у которой будет только один ребенок) на обратном пути рекурсии заменяем ссылки.
Удаление происходит аналогично.
+
<code style = "display: inline-block;">
Вставка и удаление выполняются за O(w).
+
  <font color="green">// prefixes {{---}} HashMap всех префиксов бора</font>
 +
  <font color="green">// узлы списка и дерева будем хранить одним типом: узлом с ссылками на правый и левый элементы, а содержимым {{---}} целым числом</font>
 +
  <font color="green">// только в списке будет храниться само число, а боре 1, если вершина {{---}} лист, и 0 в остальных случаях</font>
 +
  '''function''' insert(x: '''N'''):
 +
    '''if''' x '''in''' prefixes                                                <font color="green">// ''x'' содержится в боре</font>
 +
      '''return'''                                                        <font color="green">// тогда не добавляем его</font>
 +
    '''Node''' left = pred(x), right = succ(x), node = Node(x)
 +
    <font color="green">// insert node между left и right в двусвязном списке листьев</font>
 +
    <font color="green">// передаём ссылку на элемент в списке, чтобы сделать на него быструю ссылку в случае отсутствия одного из сыновей</font>
 +
    root = insertNode(root, w, node)
 +
    prefixes.addAll(allPrefixes(x))
 +
 
 +
  '''N''' insertNode(vertex: '''N''', depth: '''unsigned int''', node: '''N'''):
 +
    '''if''' vertex == <tex> \varnothing </tex>
 +
      vertex = Node(left = <tex>\varnothing</tex>, right = <tex>\varnothing</tex>, terminal = depth == 0)
 +
    '''if''' depth == 0
 +
      '''return''' vertex
 +
    '''if''' bit(node.value, depth) == 0 <font color="green">                                // depth-й бит, т. е. соответствующий текущей глубине</font>
 +
      vertex.left = insertNode(vertex.left, depth - 1, node)
 +
    '''else'''
 +
      vertex.right = insertNode(vertex.right, depth - 1, node)
 +
    '''if''' vertex.left == <tex> \varnothing </tex>
 +
      vertex.mark = ''HASNOLEFTSON''
 +
      vertex.left = node
 +
    '''else if''' vertex.right == <tex> \varnothing </tex>
 +
      vertex.mark = ''HASNORIGHTSON''
 +
      vertex.right = node
 +
    '''else'''
 +
      vertex.mark = ''HASALLSONS''
 +
</code>
 +
 
 +
===delete===
 +
Удаление происходит аналогично добавлению. Модифицируем бор, чтобы в вершине был счётчик, сколько у неё вершин в поддереве. Если 0, то удаляем её совсем. Иначе же, если удалился какой-то из сыновей, то надо обновить ссылки min и max. Это сделать просто {{---}} ссылкой на минимум (максимум) в правом (левом) поддереве становится <tex> successor ~(predecessor)</tex> удалённой вершины.
 +
 
 +
Вставка и удаление выполняются за <tex>O(w)</tex>.
  
 
===binarySearch===
 
===binarySearch===
Пока что мы не добились асимптотического выигрыша - все операции по-прежнему выполняются за О(w). Теперь слабое место - это поиск наибольшего общего префикса. Будем искать его двоичным поиском. Для этого занесём префиксы всех чисел в HashMap - ассоциативный массив, который по префиксу возвращает вершину в боре (чтобы избежать проблемы с ведущими нулями, используем при поиске маску вида 0..01..1). Запустим двоичный поиск по длине наибольшего общего префикса. Как только он вернет максимальный префикс, переходим в вершину(у этой вершины не может быть два сына, так как тогда поиск бы не завершился) и там за О(1) находим минимум или масимум, и за О(1) переходим по списку, если нужно. Итого операции find, succ и pred будут выполняться за O(log w).
+
Пока что мы не добились асимптотического выигрыша {{---}} все операции по-прежнему выполняются за <tex>O(w)</tex>. Теперь слабое место {{---}} это поиск наибольшего общего префикса. Будем искать его двоичным поиском. Для этого занесём префиксы всех чисел в <tex> HashMap </tex> {{---}} [[Хеш-таблица |ассоциативный массив]], который по префиксу возвращает вершину в боре <tex>(</tex>чтобы избежать проблемы с ведущими нулями, используем при поиске маску вида <tex>0\ldots01\ldots1)</tex>. Запустим двоичный поиск по длине наибольшего общего префикса. Как только он вернет максимальный префикс, переходим в вершину (у этой вершины не может быть два сына, так как тогда поиск бы не завершился) и там за <tex>O(1)</tex> находим минимум или максимум, и за <tex>O(1)</tex> переходим по списку, если нужно.
 +
 
 +
Итого операции <tex>find, succ</tex> и <tex>pred</tex> будут выполняться за <tex>O(\log w)</tex>.
  
 
==Сверхбыстрый цифровой бор (y-fast-trie)==
 
==Сверхбыстрый цифровой бор (y-fast-trie)==
Теперь усовершенствуем x-fast-trie до y-fast-trie, который занимает O(n) памяти, а все операции выполняются за O(log w), правда, для модифицирующих операций эта оценка будет амортизированной.
+
[[File:Sverkhbystrybor.jpg|thumb|400px|y-fast-trie]]
 +
 
 +
Теперь усовершенствуем <tex>x{-}fast{-}trie</tex> до <tex>y{-}fast{-}trie</tex>, который занимает <tex>O(n)</tex> памяти, а все операции выполняются за <tex>O(\log w)</tex>, правда, для модифицирующих операций эта оценка будет амортизированной.
  
 
Уменьшим количество занимаемой памяти.
 
Уменьшим количество занимаемой памяти.
Пусть a_1 < a_2 < a_3 < ... < a_n - числа, которые нужно хранить в боре.
+
Пусть <tex>a_1 < a_2 < a_3 < ... < a_n</tex> {{---}} числа, которые нужно хранить в боре.
Выберем какое-то k (что за k - будет видно дальше). Разобьём их на s блоков размером от k/2 до 2k, а точнее
+
Выберем какое-то <tex>k</tex> (что за <tex>k</tex> {{---}} будет видно дальше). Разобьём их на <tex>s</tex> блоков <tex> B </tex> размером от <tex dpi=150>\frac{k}{2}</tex> до <tex>2k</tex>, а точнее
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).
+
<tex>
 +
\overbrace {a_1 < a_2 < a_3}^{B_1} ~\overbrace {a_4 < ... }^{B_2} ~\overbrace {... <~a_{n-1} < a_n}^{B_s}
 +
</tex>
  
Все деревья поиска занимают O(n) памяти, и x-fast-trie O(n) памяти. Поэтому y-fast-trie тоже занимает O(n) памяти.
+
Выберем в каждом блоке какого-нибудь представителя. И поместим этих представителей в <tex>x{-}fast{-}trie</tex>. Всего в <tex>x{-}fast{-}trie</tex> будет <tex dpi=150>O(\frac{2 \cdot n \cdot w} {k})</tex> элементов. Поэтому если выбрать <tex>k = \Omega(w)</tex>, то <tex>x{-}fast{-}trie</tex> будет занимать <tex>O(n)</tex> памяти.
 +
 
 +
Каждый лист <tex>x{-}fast{-}trie</tex> является представителем блока, а все остальные элементы блока (в т. ч. и представителя) подвесим к листу как сбалансированное двоичное дерево поиска. В дереве может храниться от <tex dpi=150>\frac{w}{2}</tex> до <tex>2w</tex> элементов, поэтому его высота {{---}} <tex>O(\log w)</tex>.
 +
 
 +
Все деревья поиска занимают <tex>O(n)</tex> памяти, и <tex>x{-}fast{-}trie</tex> {{---}} <tex>O(n)</tex> памяти. Поэтому <tex>y{-}fast{-}trie</tex> тоже занимает <tex>O(n)</tex> памяти.
  
 
===find===
 
===find===
Находим succ = x среди представителей в x-fast-trie, а потом запускаем поиск succ(x) в дереве, подвешенном к листу x, а также в дереве, подвешенном к листу pred(x) среди представителей в x-fast-trie. Представителем дерева является необязательно минимальный или максимальный элемент, поэтому нужно запустить в двух деревьях. Заметим, что мы ищем элемент только в двух деревьях, так как искомый элемент точно находится между своим сакцессором и прецессором.  
+
Находим <tex>succ(x)</tex> среди представителей в <tex>x{-}fast{-}trie</tex>, а потом запускаем поиск <tex>succ(x)</tex> в дереве, подвешенном к листу <tex>x</tex>, а также в дереве, подвешенном к листу <tex>pred(x)</tex> среди представителей в <tex>x{-}fast{-}trie</tex>. Представителем дерева является необязательно минимальный или максимальный элемент, поэтому нужно запустить в двух деревьях. Заметим, что мы ищем элемент только в двух деревьях, так как искомый элемент точно находится между своими следующим и предыдущим элементами.  
O(log w) на поиск в x-fast-trie и O(log w) на поиск в деревьях поиска, поэтому итогая асимптотика - O(log w).
+
<tex>O(\log w)</tex> на поиск в <tex>x{-}fast{-}trie</tex> и <tex>O(\log w)</tex> на поиск в деревьях поиска, поэтому итогая асимптотика {{---}} <tex>O(\log w)</tex>.
  
succ & pred выполняются аналогично.
+
<tex>succ</tex> и <tex>pred</tex> выполняются аналогично.
  
 
===insert===
 
===insert===
Вставка элемента x происходит следующим образом: найдём succ(x) и вставим его в подвешенное к листу дерево. Но может возникнуть плохая ситуация: размер дерева станет 2 * w + 1. Тогда поступим следующим образом - удалим наше дерево из x-fast-trie, разделим его на элементы, из которых построим два дерева размером w и w + 1, и вставим в x-fast-trie их оба. АВЛ-деревья или красно-чёрные позволяют выполнять слияние за линейное время, поэтому операция вставки выполняется за O(w).
+
Вставка элемента <tex>x</tex> происходит следующим образом: найдём <tex>succ(x)</tex> и вставим его в подвешенное к листу дерево. Но может возникнуть плохая ситуация: размер дерева станет <tex>2 \cdot w + 1</tex>. Тогда поступим следующим образом: удалим наше дерево из <tex>x{-}fast{-}trie</tex>, разделим его на элементы, из которых построим два дерева размером <tex>w</tex> и <tex>w + 1</tex>, и вставим в <tex>x{-}fast{-}trie</tex> их оба.  
  
 
===delete===
 
===delete===
Удаление происходит аналогично, только если размер дерева станет w/2 - 1, то надо его слить с любым соседним деревом. А если после слияния размер получившегося дерева станет больше 2 * w, то надо его разделить аналогично предыдущему случаю.
+
Удаление происходит аналогично, только если размер дерева станет <tex dpi=150>\frac{w}{2} - 1</tex>, то надо его слить с любым соседним деревом. А если после слияния размер получившегося дерева станет больше <tex>2 \cdot w</tex>, то надо его разделить аналогично предыдущему случаю.
 +
 
 +
[[АВЛ-дерево |АВЛ-деревья]] или [[Красно-черное дерево |красно-чёрные]] позволяют выполнять слияние и разделение за линейное время, поэтому операции вставки и удаления выполняются за <tex>O(w)</tex>.
 +
 
 +
===Асимптотика===
 +
Заметим, что вставка, которая не модифицирует верхний бор, выполняется за истинный <tex>\log w</tex>, также и <tex>succ, pred</tex>.
 +
Плохие операции {{---}} которые модифицируют верхний бор. Но они не происходят слишком часто.
 +
 
 +
Применим амортизационный анализ, используя метод предоплаты. Копим деньги на дешевых операциях. Слияние массивов осуществляется за <tex>O(w)</tex>, как и разделение. Поэтому если мы накопим <tex>\Omega(w)</tex> дополнительных денег на дешёвых операциях, то сумеем расплатиться за все остальные, просто положив константное число дополнительных монет во время каждой операции. Худший для разделения случай произойдет, если мы дальше будем только добавлять элементы {{---}} было <tex dpi=150>\frac{w}{2} - 1</tex> и <tex>2 \cdot w</tex>, слили, стало больше <tex>2 \cdot w</tex>, разделили, таким образом получили два дерева с <tex dpi=150>\frac{5\cdot w}{4}</tex> элементами. Худший случай для слияния, когда у нас <tex>w</tex> элементов (происходит после разделения <tex>2 \cdot w + 1</tex> дерева). Заметим, что в каждом случае дерево находится на расстоянии <tex>\Theta(w)</tex> от границ. Следовательно, если мы будем класть определённое константное число монет, то скопим их достаточно, чтобы расплатиться за дорогие операции слияния и разделения деревьев.
 +
 
 +
Получаем амортизированную оценку <tex>O(\log w)</tex> и истинную {{---}} <tex>O(w)</tex>.
 +
 
 +
Получилась та же оценка на операции, что и у дерева Ван Эмде Боаса, но структура данных занимает <tex>O(n)</tex> памяти.
 +
 
 +
==См. также==
  
===Ассимптотика===
+
==Источники информации==
Заметим, что вставка, которая не модифицирует верхний бор, выполняется за истинный log(w), также и succ, pred.
+
*[[wikipedia:Y-fast_trie | Y-fast trie {{---}} Wikipedia]]
Плохие операции — которые модифицируют верхний бор. Но они не происходят слишком часто, так как после каждой операции слияния/разделения деревья оказываются на расстоянии Theta(w) от границ. Худший случай — было: w/2 и 2*w, - стало: 5w/4 и 5w/4. В нижнее дерево должно произойти порядка w вставок и удалений, чтобы оно с чем-то слилось или разделилось.
+
*[[wikipedia:X-fast_trie | X-fast trie {{---}} Wikipedia]]
Применим амортизационный анализ. Копим деньги на дешевых операциях — берем столько монет, какое расстояние до края. Скопим их достаточно, чтобы расплатиться за преобразование верхнего дерева. Получаем амортизированную оценку O(log(w)) и истинную - O(w).
+
*[http://compscicenter.ru/courses/advanced-algo/2013-spring/725/ Лекция А. С. Станкевича в Computer Science Center]
  
Здесь не имеет смысла использовать сливаемые деревья поиска, так как после слияния/разделения все равно нужно модифицировать верхний бор.
+
[[Категория: Дискретная математика и алгоритмы]]
Получилась та же оценка на операции, что и у Ван Эмде Боаса, но структура данных занимает O(n) памяти.
+
[[Категория: Деревья поиска]]
 +
[[Категория: Структуры данных]]

Текущая версия на 19:29, 4 сентября 2022

Цифровой бор

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

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

Цифровой бор поддерживает операции [math]\mathrm{insert},\ \mathrm{remove},\ \mathrm{find},\ \mathrm{succ},\ \mathrm{pred}[/math].

Добавление вершины происходит так же, как и в обычном боре. Удаление можно выполнять лениво — просто убирая пометку с листа. А можно хранить число пометок в поддереве и удалять вершину, если это число стало равным нулю.

succ

Поиск следующего элемента осуществляется проходом от корня до вершины, из которой не можем пойти в нужную сторону. Если не смогли пойти влево [math]([/math]по ребру [math]0)[/math], то ответ — минимум в правом поддереве. Если не смогли пойти вправо, поднимаемся наверх, пока являемся правым ребенком; если стали левым, то поднимаемся, пока у вершины нет правого ребенка (если такой ситуации нет, то запрос больше всех элементов). Тогда ответ — минимум в правом поддереве.

Преимущества: простая реализация, занимает [math]O(n \cdot w)[/math] памяти, все операции выполняются за [math]O(w)[/math].

Хуже дерева Ван Эмде Боаса по скорости, но памяти занимает меньше.

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

x-fast-trie
Ссылки на минимум и максимум

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

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

succOrPred

Первая модификация — занесем все элементы в двусвязный список в порядке, в котором они лежат в боре. Добавим операцию [math]\mathrm{succOrPred}[/math], которая возвращает следующий или предыдущий в зависимости от того, что проще. Работает она так: спускается вниз до наибольшего общего префикса, а потом до минимума в правом дереве или же до максимума в левом. Тогда мы получим какой-то элемент списка и не более чем за два шага в списке сможем получить ответ на запрос.

Вторая модификация — добавим ссылки. Операции поиска минимума и максимума дорогие, выполним их за [math]O(1)[/math]. Теперь становится понятно, что необязательно спускаться до минимума или максимума в дереве. Если у вершины нет левого сына, отметим это одним битом, а вместо ссылки на левого сына сделаем ссылку на минимум в правом поддереве, что удобно для нашей реализации [math]\mathrm{succOrPred}[/math]. Если нет правого сына, то храним ссылку на максимум в левом поддереве.

insert

При вставке с помощью [math]\mathrm{succOrPred}[/math] и двусвязного списка находим следующий и предыдущий элементы и вставляем нужный элемент между ними. А также при создании новой вершины (у которой будет только один ребенок) на обратном пути рекурсии заменяем ссылки.

 // prefixes — HashMap всех префиксов бора
 // узлы списка и дерева будем хранить одним типом: узлом с ссылками на правый и левый элементы, а содержимым — целым числом
 // только в списке будет храниться само число, а боре 1, если вершина — лист, и 0 в остальных случаях
 function insert(x: N):
   if x in prefixes                                                // x содержится в боре
     return                                                        // тогда не добавляем его
   Node left = pred(x), right = succ(x), node = Node(x)
   // insert node между left и right в двусвязном списке листьев
   // передаём ссылку на элемент в списке, чтобы сделать на него быструю ссылку в случае отсутствия одного из сыновей
   root = insertNode(root, w, node) 
   prefixes.addAll(allPrefixes(x))
 N insertNode(vertex: N, depth: unsigned int, node: N):
   if vertex == [math] \varnothing [/math]
     vertex = Node(left = [math]\varnothing[/math], right = [math]\varnothing[/math], terminal = depth == 0)
   if depth == 0
     return vertex
   if bit(node.value, depth) == 0                                  // depth-й бит, т. е. соответствующий текущей глубине
     vertex.left = insertNode(vertex.left, depth - 1, node)
   else
     vertex.right = insertNode(vertex.right, depth - 1, node)
   if vertex.left == [math] \varnothing [/math]
     vertex.mark = HASNOLEFTSON
     vertex.left = node
   else if vertex.right == [math] \varnothing [/math]
     vertex.mark = HASNORIGHTSON
     vertex.right = node
   else
     vertex.mark = HASALLSONS

delete

Удаление происходит аналогично добавлению. Модифицируем бор, чтобы в вершине был счётчик, сколько у неё вершин в поддереве. Если 0, то удаляем её совсем. Иначе же, если удалился какой-то из сыновей, то надо обновить ссылки min и max. Это сделать просто — ссылкой на минимум (максимум) в правом (левом) поддереве становится [math] successor ~(predecessor)[/math] удалённой вершины.

Вставка и удаление выполняются за [math]O(w)[/math].

binarySearch

Пока что мы не добились асимптотического выигрыша — все операции по-прежнему выполняются за [math]O(w)[/math]. Теперь слабое место — это поиск наибольшего общего префикса. Будем искать его двоичным поиском. Для этого занесём префиксы всех чисел в [math] HashMap [/math]ассоциативный массив, который по префиксу возвращает вершину в боре [math]([/math]чтобы избежать проблемы с ведущими нулями, используем при поиске маску вида [math]0\ldots01\ldots1)[/math]. Запустим двоичный поиск по длине наибольшего общего префикса. Как только он вернет максимальный префикс, переходим в вершину (у этой вершины не может быть два сына, так как тогда поиск бы не завершился) и там за [math]O(1)[/math] находим минимум или максимум, и за [math]O(1)[/math] переходим по списку, если нужно.

Итого операции [math]find, succ[/math] и [math]pred[/math] будут выполняться за [math]O(\log w)[/math].

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

y-fast-trie

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

Уменьшим количество занимаемой памяти. Пусть [math]a_1 \lt a_2 \lt a_3 \lt ... \lt a_n[/math] — числа, которые нужно хранить в боре. Выберем какое-то [math]k[/math] (что за [math]k[/math] — будет видно дальше). Разобьём их на [math]s[/math] блоков [math] B [/math] размером от [math]\frac{k}{2}[/math] до [math]2k[/math], а точнее

[math] \overbrace {a_1 \lt a_2 \lt a_3}^{B_1} ~\overbrace {a_4 \lt ... }^{B_2} ~\overbrace {... \lt ~a_{n-1} \lt a_n}^{B_s} [/math]

Выберем в каждом блоке какого-нибудь представителя. И поместим этих представителей в [math]x{-}fast{-}trie[/math]. Всего в [math]x{-}fast{-}trie[/math] будет [math]O(\frac{2 \cdot n \cdot w} {k})[/math] элементов. Поэтому если выбрать [math]k = \Omega(w)[/math], то [math]x{-}fast{-}trie[/math] будет занимать [math]O(n)[/math] памяти.

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

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

find

Находим [math]succ(x)[/math] среди представителей в [math]x{-}fast{-}trie[/math], а потом запускаем поиск [math]succ(x)[/math] в дереве, подвешенном к листу [math]x[/math], а также в дереве, подвешенном к листу [math]pred(x)[/math] среди представителей в [math]x{-}fast{-}trie[/math]. Представителем дерева является необязательно минимальный или максимальный элемент, поэтому нужно запустить в двух деревьях. Заметим, что мы ищем элемент только в двух деревьях, так как искомый элемент точно находится между своими следующим и предыдущим элементами. [math]O(\log w)[/math] на поиск в [math]x{-}fast{-}trie[/math] и [math]O(\log w)[/math] на поиск в деревьях поиска, поэтому итогая асимптотика — [math]O(\log w)[/math].

[math]succ[/math] и [math]pred[/math] выполняются аналогично.

insert

Вставка элемента [math]x[/math] происходит следующим образом: найдём [math]succ(x)[/math] и вставим его в подвешенное к листу дерево. Но может возникнуть плохая ситуация: размер дерева станет [math]2 \cdot w + 1[/math]. Тогда поступим следующим образом: удалим наше дерево из [math]x{-}fast{-}trie[/math], разделим его на элементы, из которых построим два дерева размером [math]w[/math] и [math]w + 1[/math], и вставим в [math]x{-}fast{-}trie[/math] их оба.

delete

Удаление происходит аналогично, только если размер дерева станет [math]\frac{w}{2} - 1[/math], то надо его слить с любым соседним деревом. А если после слияния размер получившегося дерева станет больше [math]2 \cdot w[/math], то надо его разделить аналогично предыдущему случаю.

АВЛ-деревья или красно-чёрные позволяют выполнять слияние и разделение за линейное время, поэтому операции вставки и удаления выполняются за [math]O(w)[/math].

Асимптотика

Заметим, что вставка, которая не модифицирует верхний бор, выполняется за истинный [math]\log w[/math], также и [math]succ, pred[/math]. Плохие операции — которые модифицируют верхний бор. Но они не происходят слишком часто.

Применим амортизационный анализ, используя метод предоплаты. Копим деньги на дешевых операциях. Слияние массивов осуществляется за [math]O(w)[/math], как и разделение. Поэтому если мы накопим [math]\Omega(w)[/math] дополнительных денег на дешёвых операциях, то сумеем расплатиться за все остальные, просто положив константное число дополнительных монет во время каждой операции. Худший для разделения случай произойдет, если мы дальше будем только добавлять элементы — было [math]\frac{w}{2} - 1[/math] и [math]2 \cdot w[/math], слили, стало больше [math]2 \cdot w[/math], разделили, таким образом получили два дерева с [math]\frac{5\cdot w}{4}[/math] элементами. Худший случай для слияния, когда у нас [math]w[/math] элементов (происходит после разделения [math]2 \cdot w + 1[/math] дерева). Заметим, что в каждом случае дерево находится на расстоянии [math]\Theta(w)[/math] от границ. Следовательно, если мы будем класть определённое константное число монет, то скопим их достаточно, чтобы расплатиться за дорогие операции слияния и разделения деревьев.

Получаем амортизированную оценку [math]O(\log w)[/math] и истинную — [math]O(w)[/math].

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

См. также

Источники информации