станд :: Карта Известна-Position Erase Амортизационная Сложность и количество красно-черного дерева Recolorings

Question

Сложность std::map::erase(iterator) амортизируется O (1) (см here, например). Хотя стандартная библиотека не диктует реализацию, это де-факто означает, что количество операций по перебалансировке, необходимых для красно-черного дерева, амортизируется O (1). На самом деле, запись на Википедии красно-черных деревьев seems to confirm this:

Восстановление красно-черные свойства требуется небольшое количество (O (Log N) или амортизируется O (1)) изменений цвета (которые очень быстро на практике) и не более трех поворотов деревьев (два для вставки).

но, казалось бы, без ссылки (и я не мог найти его в других местах).

Поскольку число оборотов постоянное, амортизация зависит от количества перекрасок, необходимых для пути к узлу-корню. Хотя большинство узлов в сбалансированном дереве находятся в нижней части дерева (и, следовательно, средний путь является логарифмическим), он, по-видимому, амортизируется O (1), что является удивительным и интересным. Как можно обосновать постоянные издержки?

Answer 1

В этом ответе я предполагаю, что вы знакомы с амортизированным анализом и устраиваете метод банкира. Я также предполагаю, что вы знаете инварианты красно-черного дерева.

Короткий ответ для некоторой небольшой константы k, положить k монет на каждый черный узел, который не имеет ровно одного красного ребенка.

Обратите внимание, что существует несколько различных алгоритмов для удаления в красно-черном дереве. Для стирания с помощью итератора, очевидно, требуется один из алгоритмов снизу вверх. При анализе здесь предполагается, что алгоритм выполняется примерно следующим образом:

1. Пройдите вверх, пока не будет найден черный узел. Это всегда возможно, так как корень черный, и он никогда не занимает больше двух прыжков, так как красные узлы не могут иметь красных детей.

2. Выполнение операции «исправления» в O (1) времени на поддереве, установленном на этом черном узле. Если исправление уменьшает высоту поддерева или меняет цвет корня с черного на красный, перейдите еще один шаг к корню и вернитесь к # 1.

Необходимо выполнить следующие меры: 2. На самом деле, сложность этого является одной из мотивов для ледяных красно-черных деревьев Седжуика. В основном речь идет о перечислении всех случаев, выполнении одиночного или двойного вращения, а затем тщательно проверяя, что вы не нарушали никаких инвариантов.

Один из вариантов операции FixUp (что не трудно найти, если у вас уже есть действующий вариант) сохраняет две дополнительные инварианты в процессе обхода вверх по дереву:

1. Когда высота поддерева уменьшается на 1, корень поддерева (a) изначально имел двух черных детей (b) теперь имеет ровно один красный ребенок.

2. Поддерево никогда не меняет цвет с черного на красный.

Таким образом, для каждого шага обхода, либо

1. Корень поддерева имеет один или два красных детей. Мы выполняем O (1) работу, добавляем не более O (1) монеты и останавливаем

2. Выполняем 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) в каждом из:

1. красно-черных деревьев, в которых черные узлы могут иметь только один красный ребенок

2. AA-деревья

3. 2-3 деревья

4. (а, 2а-1) деревья, для любого а> 1.

В то время как вставка и удаление являются O (1) амортизируется в красно-черных деревьев, (2,4) деревьев, и (а, 2а) деревьев для любого а> 1.