Скошенный двоичный список: перенос за один шаг

Если механизм уже знаком - листай до «Теперь сам».

Как думаешь: что нужно сохранить

Бинарный список деревьев размеров 1,2,4,… при добавлении головы может объединить цепочку равных деревьев. В среднем это дёшево, но отдельная операция стоит логарифм. Можно ли выбрать другие размеры и разрешить ограниченную избыточность, чтобы один перенос никогда не запускал второй? Подумай о двух одинаковых младших деревьях и новой вершине над ними: какого размера получится дерево?

На что это похоже

Представь стопку коробок размеров 1,3,7,15. Когда первые две коробки одинаковы, новая единица становится крышкой большой коробки, внутри которой помещаются обе старые. Размер новой коробки - не просто сумма, а сумма плюс крышка. Избыточная пара разрешена только в начале стопки, поэтому перенос никогда не догоняет ещё одну пару того же размера дальше по списку.

Механизм: от определения к алгоритму

Скошенные двоичные веса определим как w₀=1, wᵢ₊₁=2wᵢ+1, то есть wᵢ=2^(i+1)-1. Цифры могут быть 0,1,2, но двойка допустима только у самого младшего ненулевого разряда. В разреженном представлении хранят возрастающий список ненулевых весов, первые два могут совпадать. Например, число 6 - [3,3], число 7 - [7].

При увеличении на один посмотри на два первых веса. Если равны w, замени их на 1+2w. Если нет - добавь 1 в начало. Новый результат снова канонический. Равная пара была младшей, значит дальше не было ещё одной двойки, которая потребовала бы каскада переносов. Для уменьшения удали первый вес 1 либо разбей вес w>1 на два веса (w-1)/2. Это постоянное число операций со связным списком весов.

Для списка с произвольным доступом каждому весу соответствует полное двоичное дерево, значения лежат в вершинах. Порядок элементов внутри дерева - корень, левое поддерево, правое поддерево. При cons(x) два первых дерева одинакового размера становятся детьми нового корня x; иначе создаётся одноэлементное дерево. При удалении головы большого дерева его дети возвращаются в начало леса. Старые вершины неизменяемы и разделяются между версиями.

Размеры леса растут геометрически, поэтому деревьев O(log n). Для доступа по индексу вычитай размеры деревьев, пока не найдёшь нужное, затем спускайся по размерам детей. Высота дерева логарифмическая. Суммарный путь поиска O(log n); изменение элемента копированием пути имеет ту же оценку. Добавление и удаление головы затрагивают лишь постоянное число вершин и звеньев леса.

Python-список как контейнер леса исказил бы эту стоимость: вставка в начало сдвигает элементы, а срез копирует хвост. Ниже лес и деревья представлены неизменяемыми кортежами-связками. Размер известен в корне дерева, копировать поддеревья при объединении не нужно.

Правило

Разрешай равную пару только у младшего ненулевого веса; тогда новая голова объединяет максимум два дерева и не вызывает каскада.

Разбор: проследим вычисление

Построим список добавлениями от 0 до 9. Логический порядок будет обратным: 9,8,…,0. Выведем веса деревьев и проверим все индексы. Сохранённый пустой лес и старые версии остаются пригодными к чтению, поскольку ни одна существующая вершина не изменяется. tail большого дерева лишь раскрывает двух детей, а не обходит всё дерево.

def leaf(x):
    return (1, x, None, None)

def cons(x, forest):
    if forest and forest[1]:
        a, rest = forest
        b, tail = rest
        if a[0] == b[0]:
            return ((1+a[0]+b[0], x, a, b), tail)
    return leaf(x), forest

def uncons(forest):
    tree, rest = forest
    size, x, left, right = tree
    if size == 1:
        return x, rest
    return x, (left, (right, rest))

def at(forest, index):
    if index < 0:
        raise IndexError(index)
    while forest:
        tree, forest = forest
        if index < tree[0]:
            while index:
                index -= 1
                left, right = tree[2], tree[3]
                if index < left[0]:
                    tree = left
                else:
                    index -= left[0]
                    tree = right
            return tree[1]
        index -= tree[0]
    raise IndexError(index)

forest = None
versions = []
for x in range(10):
    forest = cons(x, forest)
    versions.append(forest)
weights, cursor = [], forest
while cursor:
    tree, cursor = cursor
    weights.append(tree[0])
print('веса', weights)
print('значения', [at(forest, i) for i in range(10)])
head, after = uncons(forest)
assert head == 9 and at(after, 0) == 8
assert at(versions[3], 0) == 3
print('старая версия', at(versions[3], 0))

веса [3, 7]
значения [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
старая версия 3

Разбор: где проходит граница

Обычная двоичная запись числа 7 - три единицы. Добавление единицы вызывает перенос через три позиции. Скошенная запись 6 - [3,3], увеличение даёт [7] одним объединением. У 7 следующая операция просто добавляет 1: [1,7]. Здесь нет цепочки скрытых слияний. Однако если разрешить одинаковые пары где угодно, например [1,1,3,3], правило каноничности нарушено и одно локальное действие больше не доказывает ограниченность переносов.

Что ломается без этого

Копирование целого леса при cons возвращает логарифмическую стоимость. Неверный порядок обхода дерева меняет смысл индекса: корень должен идти раньше обоих детей. После удаления корня нельзя менять местами левое и правое поддеревья. Если хранить только суммарный размер списка и забыть размеры деревьев, поиск индекса потребует обходить поддеревья для вычисления их длины, разрушая логарифмическую оценку.

Зачем это в работе

Структура нужна, когда сохраняются версии последовательности, часто добавляется голова и иногда нужен индексный доступ. Обычный связный список даёт быструю голову, но медленный индекс; массив хорош для индекса, но дорог для персистентной вставки спереди. Скошенный лес занимает промежуточное место с простыми локальными операциями. Если основной сценарий - добавление в конец и проход по памяти, другую структуру можно выбрать и по асимптотике, и по кеш-локальности.

Теперь сам

Канонический лес имеет веса [1,3,3]. Допустим ли он? А [3,3,7]? Как изменится второй после добавления головы?