Изменения

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

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

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

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

Поиск следующего элемента осуществляется проходом от корня до вершины, из которой не можем пойти в нужную сторону. Если не смогли пойти влево <tex>(</tex>по ребру <tex>0)</tex>), то ответ {{-- -}} минимум в правом поддереве. Если не смогли пойти вправо, поднимаемся наверх, пока являемся правым ребенком, ; если стали левым, то поднимаемся, пока у вершины нет правого ребенка (если такой ситуации нет, то запрос больше всех элементов). Тогда ответ {{--- }} минимум в правом поддереве.

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

[[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>. [[File:Tsifrovoybor.jpg|thumb|500px|x-fast-trie]]

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

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

Вторая модификация {{- --}} добавим ссылки.Операции поиска минимума и максимума дорогие, выполним их за <tex>O(1)</tex>. Теперь становится понятно, что необязательно спускаться до минимума или максимума в дереве. Если у вершину нет левого сына (, отметим это одним битом) , а вместо ссылки на левого сына сделаем ссылку на минимум в правом поддереве, что удобно для нашей реализации <tex>succOrPred</tex>. Если нет правого сына, то храним ссылку на максимум в левом поддереве. [[File:Min amp amp max.jpg|thumb|right|500px|Ссылки на минимум и максимум]]