1632
правки
Изменения
м
rollbackEdits.php mass rollback
При вставке с помощью <tex>\mathrm{succOrPred}</tex> и двусвязного списка находим следующий и предыдущий элементы и вставляем нужный элемент между ними. А также при создании новой вершины (у которой будет только один ребенок) на обратном пути рекурсии заменяем ссылки.
<code style = "display: inline-block;">
<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>
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>.
