Изменения

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

'''Цифровой бор ''' {{---}} [[Бор | бор]], в котором в качестве строк используются двоичные записи чисел, включая ведущие нули.

Цифровой бор поддерживает операции <tex>\mathrm{insert}, ~\ \mathrm{remove}, ~\ \mathrm{find}, ~\ \mathrm{succ}, ~\ \mathrm{pred}</tex>.

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

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

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

<font color="green">// prefixes {{---}} HashMap всех префиксов бора</font> <font color="green">// узлы списка и дерева будем хранить одним типом: узлом с ссылками на правый и левый элементы, а содержимым {{---}} целым числом</font> <font color="green">// только в списке будет храниться само число, а боре 1, если вершина {{---}} лист, и 0 в остальных случаях</font> '''function''' insert(x: '''N'''): '''if''' x '''in''' prefixes.contains(x): <font color="green">// ''x'' содержится в боре</font> '''return''' <font color="green">// тогда не добавляем его</font> '''Node '''left'' = precpred(x), ''right'' = succ(x), ''nodex'' node = new Node(x) <font color="green">// insert ''nodex'' node между ''left'' и ''right'' в двусвязном списке листьев</font> <font color="green">// передаём ссылку на элемент в списке, чтобы сделать на него быструю ссылку в случае отсутствия одного из сыновей</font> root = insertNode(root, w, ''nodexnode)

'''N''' insertNode(vertex: '''N''', depth: '''unsigned int''', xnode: '''N'''): '''if''' ''vertex'' == <tex> \varnothing </tex>: ''vertex'' = new Node(left = <tex>\varnothing</tex>, right = <tex>\varnothing</tex>, terminal = depth == 0) '''if''' ''depth'' == 0: '''return''' ''vertex'' '''if''' depthBitbit(xnode.value, depth) == 0: <font color="green"> // depth-й бит, т. е. соответствующий текущей глубине</font> vertex.left = insertNode(vertex.left, depth - 1, xnode) '''else''': vertex.right = insertNode(vertex.right, depth - 1, xnode) '''if''' vertex.left == <tex> \varnothing </tex>:

vertex.left = ''x''node '''else if''' vertex.right == <tex> \varnothing </tex>:

vertex.right = node ''x'else''' vertex.mark = ''HASALLSONS''

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

Выберем какое-то <tex>k</tex> (что за <tex>k</tex> {{---}} будет видно дальше). Разобьём их на <tex>s</tex> блоков <tex> B </tex> размером от <tex dpi=150>\frac{k}{2}</tex> до <tex>2k</tex>, а точнее  <tex>B_\overbrace {11a_1 < a_2 < a_3} < B_^{12B_1} ~\overbrace {a_4 < ... < B_}^{1n_{1B_2}} < B_~\overbrace {21} < ... < B_~a_{2n_{2}n-1} < ... < B_{s1a_n} < ... < B_{sn_^{s}B_s}</tex>

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

Находим <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>. Представителем дерева является необязательно минимальный или максимальный элемент, поэтому нужно запустить в двух деревьях. Заметим, что мы ищем элемент только в двух деревьях, так как искомый элемент точно находится между своими следующим и предыдущим элементами.

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

Применим амортизационный анализ, используя метод предоплаты. Копим деньги на дешевых операциях. Слияние массивов осуществляется за <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> от границ. Следовательно, если мы будем класть определённое константное число монет, то скопим их достаточно, чтобы расплатиться за дорогие операции слияния и разделения деревьев.

==СсылкиСм. также== ==Источники информации==

*[http://compscicenter.ru/programcourses/lectureadvanced-algo/2013-spring/725/6902 Лекция А. С. Станкевичав Computer Science Center]