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