Изменения
→Ассимптотика
Заметим, что вставка, которая не модифицирует верхний бор, выполняется за истинный log(w), также и succ, pred.
Плохие операции — которые модифицируют верхний бор. Но они не происходят слишком часто, так как после каждой операции слияния/разделения деревья оказываются на расстоянии Theta(w) от границ. Худший случай — было: w/2 и 2*w, - стало: 5w/4 и 5w/4. В нижнее дерево должно произойти порядка w вставок и удалений, чтобы оно с чем-то слилось или разделилось.
Применим амортизационный анализ. Копим деньги на дешевых операциях — берем столько монет: когда добавляем вершину, какое расстояние до краято кладём 4/3 монетки. Скопим Таким образом мы успеем накопить на разделение при превышении размера в 2 * w. При удалении кладём ещё 2 монетки. И таким образом мы скопим их достаточно, чтобы расплатиться за преобразование верхнего дерева. Получаем амортизированную оценку O(log(w)) и истинную - O(w).
Здесь не имеет смысла использовать сливаемые деревья поиска, так как после слияния/разделения все равно нужно модифицировать верхний бор.
Получилась та же оценка на операции, что и у Ван Эмде Боаса, но структура данных занимает O(n) памяти.
