Изменения

<font color="green">// prefixes {{---}} HashMap всех префиксов бора</font> <font color="green">// узлы списка и дерева будем хранить одним типом: узлом с ссылками на правый и левый элементы, а содержимым {{---}} целым числом</font> <font color="green">// только в списке будет храниться само число, а боре 1, если вершина {{---}} лист, и 0 в остальных случаях</font> '''insertfunction'''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>

'''insertNodeN'''insertNode(vertex: '''N''', depth: '''unsigned int''', node: '''N'''):

'''if''' bit(node.value, depth) == 0 <font color="green"> // depth-й бит, т. е. соответствующий текущей глубине</font>

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