Плохие операции — которые модифицируют верхний бор. Но они не происходят слишком часто.
// O - сверху, Omega - снизу, Theta - и сверху и снизу - памятка для тебя, чтобы не запутаться Применим амортизационный анализ, используя метод предоплаты. Копим деньги на дешевых операциях. Слиянием массивов осуществляется за O(w), как и разделение. Поэтому, если мы накопим Omega(w) дополнительных денег на дешёвых операциях, то сумеем расплатиться за все остальные, просто кладя константное число дополнительных монет во время каждой операции. Худший случай для разделения, если мы дальше будем только добавлять элементы - было w/2 - 1 и 2 * w, слили, стало больше 2 * w, разделели, таким образом получили два дерева с 5/4 * w элементами. Худший случай для слияния, когда у нас w элементов (просиходит после разделения 2 * w + 1 дерева). ЗаметилЗаметим, что в каждом случае дерево находится на расстоянии Theta(w) от границ. Следовательно, если мы будем класть определённое константное число монет, то скопим их достаточно, чтобы расплатиться за преобразование верхнего дерева.
Получаем амортизированную оценку O(log(w)) и истинную - O(w).
