243
правки
Изменения
→Асимптотика
<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>
root = insertNode(root, w, node)
prefixes.addAll(allPrefixes(x))
'''insertNodeN'''insertNode(vertex: '''N''', depth: '''unsigned int''', node: '''N'''):
'''if''' vertex == <tex> \varnothing </tex>
vertex = Node(left = <tex>\varnothing</tex>, right = <tex>\varnothing</tex>, terminal = depth == 0)
'''if''' depth == 0
'''return''' vertex
'''if''' bit(node.value, depth) == 0 <font color="green"> // depth-й бит, т. е. соответствующий текущей глубине</font>
vertex.left = insertNode(vertex.left, depth - 1, node)
'''else'''
Плохие операции {{---}} которые модифицируют верхний бор. Но они не происходят слишком часто.
Применим амортизационный анализ, используя метод предоплаты. Копим деньги на дешевых операциях. Слияние массивов осуществляется за <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> от границ. Следовательно, если мы будем класть определённое константное число монет, то скопим их достаточно, чтобы расплатиться за дорогие операции слияния и разделения деревьев.
Получаем амортизированную оценку <tex>O(\log w)</tex> и истинную {{---}} <tex>O(w)</tex>.
