Изменения
→Быстрый цифровой бор (x-fast-trie)
==Быстрый цифровой бор (x-fast-trie)==
Он по-прежнему будет занимать <tex>O(n * w) </tex> памяти, но немодифицирующие операции (read-only) будут выполняться за <tex>O(\log w)</tex>. [[File:Tsifrovoybor.jpg|thumb|500px|x-fast-trie]]
Улучшим структуру: было два слабых места — подниматься вверх и искать минимум.
Вторая модификация - добавим ссылки.
Операции поиска минимума и максимума дорогие, выполним их за О<tex>O(1)</tex>. Теперь становится понятно, что необязательно спускаться до минимума или максимума в дереве. Если у вершину нет левого сына (отметим одним битом) вместо ссылки на левого сына сделаем ссылку на минимум в правом поддереве, что удобно для нашей реализации succOrPred. Если нет правого сына, то храним ссылку на максимум в левом поддереве. [[File:Min amp amp max.jpg|thumb|right|500px|Ссылки на минимум и максимум]]
===insert===
При вставке с помощью succOrPred и двусвязного списка находим следующий и предыдущий элементы и вставляем нужный элемент между ними. А также при создании новой вершины(у которой будет только один ребенок) на обратном пути рекурсии заменяем ссылки.
Удаление происходит аналогично.
Вставка и удаление выполняются за <tex>O(w)</tex>.
===binarySearch===
Пока что мы не добились асимптотического выигрыша - все операции по-прежнему выполняются за О<tex>O(w)</tex>. Теперь слабое место - это поиск наибольшего общего префикса. Будем искать его двоичным поиском. Для этого занесём префиксы всех чисел в HashMap - ассоциативный массив, который по префиксу возвращает вершину в боре (чтобы избежать проблемы с ведущими нулями, используем при поиске маску вида <tex>0...01...1</tex>). Запустим двоичный поиск по длине наибольшего общего префикса. Как только он вернет максимальный префикс, переходим в вершину(у этой вершины не может быть два сына, так как тогда поиск бы не завершился) и там за О<tex>O(1) </tex> находим минимум или масимум, и за О<tex>O(1) </tex> переходим по списку, если нужно.
Итого операции <tex>find, succ </tex> и <tex>pred </tex> будут выполняться за <tex>O(\log w)</tex>.
==Сверхбыстрый цифровой бор (y-fast-trie)==
