std :: map Известная позиция Стереть Амортизируемую сложность и количество красно-черных перекрашиваний деревьев
Сложность std::map::erase(iterator) амортизируется O (1) (увидеть Вот, например). Хотя стандартная библиотека не диктует реализации, это фактически означает, что количество операций перебалансировки, необходимых для красно-черного дерева, амортизируется. O (1). На самом деле, запись в Википедии о красно-черных деревьях кажется, подтверждает это:
Для восстановления красно-черных свойств требуется небольшое количество (O (log n) или амортизированный O (1)) изменений цвета (которые очень быстро применяются на практике) и не более трех поворотов дерева (два для вставки).
но, казалось бы, без ссылки (и я не мог найти ее в других местах).
Поскольку число вращений является постоянным, амортизация относится к числу перекрашиваний, необходимых на пути корня узла. Хотя большинство узлов в сбалансированном дереве расположены к нижней части дерева (и, следовательно, средний путь является логарифмическим), он, по-видимому, амортизируется. O (1), что удивительно и интересно. Как можно доказать амортизированные постоянные затраты?
Решение
В этом ответе я предполагаю, что вы знакомы с амортизированным анализом и знакомы с методом банкира. Я также предполагаю, что вы знаете красно-черные инварианты деревьев.
Краткий ответ: для некоторой небольшой константы k положите k монет на каждый черный узел, у которого нет ровно одного красного ребенка.
Обратите внимание, что существует множество различных алгоритмов удаления в красно-черном дереве. Стирание с помощью итератора, очевидно, требует одного из восходящих алгоритмов. Анализ здесь предполагает, что алгоритм работает примерно следующим образом:
-
Пройдите вверх, пока не будет найден черный узел. Это всегда возможно, поскольку корень черный, и он никогда не занимает более двух прыжков, поскольку красные узлы не могут иметь красных дочерних элементов.
-
Выполните операцию «fixup» за O (1) время на поддереве с корнем в этом черном узле. Если исправление уменьшает высоту поддерева или меняет цвет корня с черного на красный, пройдите еще один шаг к корню и вернитесь к # 1.
Требуется некоторая работа, чтобы увидеть, что # 2 возможно. На самом деле, сложность этого является одной из мотиваций для лево-наклонных красно-черных деревьев Седжвика. В основном это вопрос перечисления всех случаев, выполнения одинарного или двойного поворота, а затем тщательной проверки того, что вы не нарушили никаких инвариантов.
Один вариант операции исправления (его нетрудно найти, если у вас уже есть другой допустимый вариант) сохраняет два дополнительных инварианта в ходе обхода дерева:
-
Когда высота поддерева уменьшается на 1, у корня поддерева (а) изначально было два черных потомка (б), теперь ровно один красный потомок.
-
Поддерево никогда не меняет цвет с черного на красный.
Таким образом, для каждого шага обхода, либо
-
Корень поддерева имеет одного или двух красных детей. Мы выполняем O (1) работу, добавляем не более O (1) монет и останавливаем
-
Мы выполняем O (1) работу, вернуть O (1) монеты, превратив узел с двумя черными детьми в узел с одним красным ребенком, и продолжить
Дело № 2 амортизируется бесплатно, до тех пор, пока количество монет достаточно велико, чтобы покрыть расходы на реструктуризацию и перекрашивание в случае № 2. Таким образом, общая амортизированная стоимость удаления — это количество раз, которое мы встречаем в случае № 1 за одну операцию удаления, что не более одного, так как после того, как мы ее выполняем, мы останавливаемся.
Хотя это охватывает механику арифметики объяснения, на самом деле это не объясняет Зачем Удалить амортизируется O (1).
Один из случаев, когда учащимся иногда преподают амортизированную стоимость, — это приращение двоичных чисел. Стоимость составляет Ω (lg n) в худшем случае, но O (1) в амортизированном смысле, помещая постоянное количество монет в каждую цифру «1».
Точно так же уменьшение уменьшается на O (1) путем помещения постоянного числа монет в каждую цифру «0». Однако смешивание этих двух значений приводит к стоимости Ω (lg n) даже в амортизированной настройке, поскольку амортизированный анализ зависит от всех шагов обхода, кроме последнего, возвращая постоянное количество монет.
Эта тема прохождения без освобождения похожа на анализ красно-черного дерева выше. Цифры, на которые должны быть нанесены монеты, представляют собой цифры, которые представляют собой структурные изменения, которые должны быть сделаны. Используя метод физика, потенциальная энергия добавляется к структуре для каждой цифры, как это.
Рассмотрим другое представление двоичных чисел, в которых цифры могут быть 0, 1, или 2 (но цифра d_i по-прежнему представляет d_i * 2 ^ i). Это называется избыточным двоичным кодом. Теперь вы можете поместить постоянное количество монет на все 0 или 2 цифры и получить амортизированный прирост и уменьшение постоянного времени. Причина в том, что каскадный прирост или декремент изменяется от 0 с или 2 с до 1 с, и поэтому всегда возвращает монеты.
Таким образом, с двумя цифрами, приращение или уменьшение равно O (1), амортизируется, но не оба, и с тремя, оба могут быть амортизированы O (1).
Аналогично, либо вставка, либо удаление (но не оба) амортизируется O (1) во всех:
-
Красно-черные деревья, в которых черные узлы могут иметь только одного красного ребенка
-
AA-деревья
-
2-3 дерева
-
(a, 2a-1) деревьев для любого a> 1.
В то время как как вставка, так и удаление O (1) амортизируются в красно-черных деревьях, (2,4) деревья и (a, 2a) деревья для любого a> 1.
Другие решения
Других решений пока нет …