std::map Known-Position Erase Амортизированная сложность и количество красно-черных перекрасок дерева

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

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

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

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

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

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

Один вариант операции исправления (его нетрудно найти, если у вас уже есть другой допустимый вариант) сохраняет два дополнительных инварианта в ходе обхода дерева:

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

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. (a,2a-1) деревьев для любого a > 1.

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