Изменения

При вставке с помощью <tex>succOrPred </tex> и двусвязного списка находим следующий и предыдущий элементы и вставляем нужный элемент между ними. А также при создании новой вершины(у которой будет только один ребенок) на обратном пути рекурсии заменяем ссылки.<code style = "display: inline-block;"> // prefixes {{---}} HashMap всех префиксов бора insert(x) if prefixes.contains(x): // ''x'' содержится в боре return root = insertNode(root, w, x) Node ''left'' = prec(x), ''right'' = succ(x) insert ''x'' между ''left'' и ''right'' в двусвязном списке листьев prefixes.addAll(allPrefixes(x))  insertNode(vertex, depth, value) 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 hiBit(x) == 0: vertex.left = insertNode(vertex.left, depth - 1, x[1:]) else: vertex.right = insertNode(vertex.right, depth - 1, x[1:]) // ещё вставка min & max</code> ===delete===Удаление происходит аналогичнодобавлению.Модифицируем бор, чтобы в вершине был счётчик, сколько у неё вершин в поддереве. Если 0, то удаляем её совсем. Иначе же, если удалился какой-то из сыновей, то надо обновить ссылки min и max. Это сделать просто {{---}} ссылкой на минимум (максимум) в правом (левом) поддереве становится <tex> successor ~(predecessor)</tex> удалённой вершины. 

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

Пусть <tex>a_1 < a_2 < a_3 < ... < a_n</tex> {{-- -}} числа, которые нужно хранить в боре.Выберем какое-то <tex>k</tex> (что за <tex>k</tex> {{--- }} будет видно дальше). Разобьём их на <tex>s</tex> блоков размером от <texdpi=150>\frac{k}{2}</tex> до <tex>2k</tex>, а точнее <tex>B_{11} < B_{12} < ... < B_{1n11n_{1}} < B_{21} < B_{22} < ... < B_{2n22n_{2}} < ... < B_{s1} < B_{s2} < ... < B_{snssn_{s}}</tex>

Выберем в каждом блоке какого-нибудь представителя. И поместим этих представителей в <tex>x{-}fast{-}trie</tex>. Всего в <tex>x{-}fast{-}trie</tex> будет <texdpi=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> является представителем блока, а все остальные элементы блока (в т. ч. и представителя) подвесим к листу как сбалансированное двоичное дерево поиска. В дереве может храниться от <texdpi=150>\frac{w}{2}</tex> до <tex>2w</tex> элементов, поэтому его высота {{--- }} <tex>O(\log w)</tex>.

Все деревья поиска занимают <tex>O(n)</tex> памяти, и <tex>x{-}fast{-}trie – {{---}} 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(\log w)</tex> на поиск в <tex>x{-}fast{-}trie</tex> и <tex>O(\log w)</tex> на поиск в деревьях поиска, поэтому итогая асимптотика {{- --}} <tex>O(\log w)</tex>.

Вставка элемента <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> их оба. [[АВЛ-дерево |АВЛ-деревья]] или [[Красно-черное дерево |красно-чёрные]] позволяют выполнять слияние за линейное время, поэтому операция вставки выполняется за <tex>O(w)</tex>.

Удаление происходит аналогично, только если размер дерева станет <texdpi=150>\frac{w}{2} - 1</tex>, то надо его слить с любым соседним деревом. А если после слияния размер получившегося дерева станет больше <tex>2 \cdot w</tex>, то надо его разделить аналогично предыдущему случаю. [[АВЛ-дерево |АВЛ-деревья]] или [[Красно-черное дерево |красно-чёрные]] позволяют выполнять слияние и разделение за линейное время, поэтому операции вставки и удаления выполняются за <tex>O(w)</tex>.

Плохие операции — {{---}} которые модифицируют верхний бор. Но они не происходят слишком часто.

Применим амортизационный анализ, используя метод предоплаты. Копим деньги на дешевых операциях. Слиянием Слияние массивов осуществляется за <tex>O(w)</tex>, как и разделение. Поэтому, если мы накопим <tex>\Omega(w)</tex> дополнительных денег на дешёвых операциях, то сумеем расплатиться за все остальные, просто положив константное число дополнительных монет во время каждой операции. Худший для разделения случай произойдет, если мы дальше будем только добавлять элементы {{-- -}} было <texdpi=150>\frac{w}{2} - 1</tex> и <tex>2 \cdot w</tex>, слили, стало больше <tex>2 \cdot w</tex>, разделелиразделили, таким образом получили два дерева с <texdpi=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> памяти.

*[http[wikipedia://en.wikipedia.org/wiki/Y-fast_trie | Y-fast trie — {{---}} Wikipedia]]*[http[wikipedia://en.wikipedia.org/wiki/X-fast_trie | X-fast trie — {{---}} Wikipedia]]