Копирование пути: новая версия дерева из log n узлов

Если ты знаешь копирование пути, сколько оно стоит в сбалансированном и вырожденном дереве и как на нём сделать персистентный массив, листай до «Теперь сам».

Как думаешь, сколько узлов

Дерево поиска на миллион ключей, сбалансированное, высота около 20. Нужно вставить ключ и сохранить обе версии - до и после. Сколько новых узлов понадобится, если старые узлы трогать нельзя? Миллион? Половина?

Ответь себе до чтения. Двадцать один: по узлу на каждом уровне пути и новый лист. Все остальные 999 980 узлов обе версии делят.

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

Оглавление книги с главами, разделами и параграфами. Ты переписал один параграф. Чтобы получить новое издание, не перепечатывая всё, достаточно новой страницы параграфа, новой страницы раздела, где теперь ссылка на новый параграф, новой страницы главы и новой обложки-оглавления. Остальные главы новое издание просто берёт из старого - они не изменились, и ссылки на них прежние.

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

Вставка ключа k в персистентное дерево поиска с корнем v:

вставить(v, k):
    если v пусто: вернуть новый лист k
    если k < ключ(v):
        вернуть НОВЫЙ узел(ключ(v), вставить(левый(v), k), правый(v))
    иначе:
        вернуть НОВЫЙ узел(ключ(v), левый(v), вставить(правый(v), k))

Каждый вызов создаёт копию узла, в которой одна ссылка новая, а вторая указывает на старое поддерево. Старый корень v по-прежнему описывает старое дерево целиком: ни один его узел не изменился. Новый корень - новое дерево. Узлов создано столько, какова длина пути.

Балансировка (красно-чёрная, АВЛ) поворачивает узлы только возле пути вставки: поворот меняет ссылки у двух-трёх соседних узлов, и именно их копируют вместе с путём. Поэтому балансировку тоже можно делать копированием: O(log n) новых узлов на операцию. Есть и более тонкие схемы - «толстые узлы» и копирование узлов Дрисколла и соавторов, с O(1) амортизированной памяти на правку при частичной персистентности.

Правило

Копирование пути: изменение создаёт новые копии всех узлов на пути от корня до места правки, боковые поддеревья делятся со старой версией. Цена - длина пути: O(log n) в сбалансированном дереве, O(n) в вырожденном. Корень - это и есть версия.

Разбор: 300 версий дерева поиска

Узлы хранятся в трёх общих списках - ключ, левый, правый; номер узла - позиция. Вставляем 300 случайных разных ключей (равный ключ эта вставка отправила бы направо), сохраняя корень каждой версии, и проверяем, что старая версия не пострадала.

import random

klyuch = []
levyj = []
pravyj = []

def uzel(k, l, r):
    klyuch.append(k)
    levyj.append(l)
    pravyj.append(r)
    return len(klyuch) - 1

def vstavit(v, k):
    # копирование пути: новый узел на каждом шаге от корня до места
    if v == -1:
        return uzel(k, -1, -1)
    if k < klyuch[v]:
        return uzel(klyuch[v], vstavit(levyj[v], k), pravyj[v])
    return uzel(klyuch[v], levyj[v], vstavit(pravyj[v], k))

def po_poryadku(v, out):
    if v != -1:
        po_poryadku(levyj[v], out)
        out.append(klyuch[v])
        po_poryadku(pravyj[v], out)

random.seed(12)
klyuchi = list(range(1000))
random.shuffle(klyuchi)
klyuchi = klyuchi[:300]
versii = [-1]
for k in klyuchi:
    versii.append(vstavit(versii[-1], k))
kopiya = 0
for i in range(1, len(versii)):
    kopiya = kopiya + i              # копия дерева из i узлов
print("версий:", len(versii) - 1,
      "узлов с копированием пути:", len(klyuch))
print("при копировании целиком:", kopiya)
v50 = []
po_poryadku(versii[50], v50)
print("версия 50: ключей", len(v50),
      "совпадает:", v50 == sorted(klyuchi[:50]))

версий: 300 узлов с копированием пути: 2832
при копировании целиком: 45150
версия 50: ключей 50 совпадает: True

2832 узла на 300 версий - в среднем 9,4 на вставку: столько в случайном дереве поиска длина пути. Копия целиком - 1 + 2 + … + 300 = 45 150. Версия 50 через 250 вставок содержит ровно первые 50 ключей.

Граница правила - баланс. Те же вставки, но ключи по возрастанию: дерево вырождается в цепочку, путь к новому ключу проходит через все старые.

klyuch = []
levyj = []
pravyj = []

def uzel(k, l, r):
    klyuch.append(k)
    levyj.append(l)
    pravyj.append(r)
    return len(klyuch) - 1

def vstavit(v, k):
    if v == -1:
        return uzel(k, -1, -1)
    if k < klyuch[v]:
        return uzel(klyuch[v], vstavit(levyj[v], k), pravyj[v])
    return uzel(klyuch[v], levyj[v], vstavit(pravyj[v], k))

v = -1
for k in range(150):                 # ключи по возрастанию
    v = vstavit(v, k)
print("узлов:", len(klyuch))

узлов: 11325

1 + 2 + … + 150 = 11 325 - ровно столько же, сколько копирование целиком: в цепочке «путь» и есть всё дерево. Персистентность без баланса ничего не экономит.

Разбор: персистентный массив

Массив из 2ᵏ ячеек - полное двоичное дерево глубины k: путь к ячейке i задают биты i от старшего к младшему, ноль - налево, единица - направо. Запись - копирование пути: k внутренних узлов и лист.

# персистентный массив из 2^k ячеек: полное двоичное дерево, путь к
# ячейке i - биты i от старшего к младшему; узел - [левый, правый],
# лист - [значение]; индексы 0 .. 2^k - 1, границы не проверяем
uzly = []

def novyj(x):
    uzly.append(x)
    return len(uzly) - 1

def postroit(k, znach):
    # одинаковые половины - один и тот же узел: общие части с рождения
    if k == 0:
        return novyj([znach])
    polovina = postroit(k - 1, znach)
    return novyj([polovina, polovina])

def prochitat(v, k, i):
    for b in range(k - 1, -1, -1):
        # i >> b ставит бит номер b в младший разряд, & 1 оставляет
        # только его: 0 - налево, 1 - направо
        v = uzly[v][(i >> b) & 1]
    return uzly[v][0]

def zapisat(v, k, i, x):
    # копируем путь: k внутренних узлов и лист
    if k == 0:
        return novyj([x])
    bit = (i >> (k - 1)) & 1
    l = uzly[v][0]
    r = uzly[v][1]
    if bit == 0:
        l = zapisat(l, k - 1, i, x)
    else:
        r = zapisat(r, k - 1, i, x)
    return novyj([l, r])

k = 10                               # 1024 ячейки
v0 = postroit(k, 0)
nachalo = len(uzly)
v1 = zapisat(v0, k, 700, 5)
v2 = zapisat(v1, k, 3, 9)
v3 = zapisat(v1, k, 700, 8)          # ветка от v1
print("узлов в исходном массиве:", nachalo)
print("новых узлов на три записи:", len(uzly) - nachalo)
for imya, v in [["v0", v0], ["v1", v1], ["v2", v2], ["v3", v3]]:
    print(imya, "[3] =", prochitat(v, k, 3),
          "[700] =", prochitat(v, k, 700))

узлов в исходном массиве: 11
новых узлов на три записи: 33
v0 [3] = 0 [700] = 0
v1 [3] = 0 [700] = 5
v2 [3] = 9 [700] = 5
v3 [3] = 0 [700] = 8

Массив из 1024 нулей уместился в 11 узлах: одинаковые половины - один и тот же узел, общие части работают даже внутри одной версии. Каждая запись - 11 новых узлов (log₂ 1024 + 1), три записи - 33. Версия v3 отпочкована от v1 и не видит записи в v2: полная персистентность.

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

Персистентное дерево без баланса. Отсортированный поток ключей - и каждая версия стоит O(n), память растёт квадратом.

Правка узла «на месте» в одной ветке. Узел общий для многих версий; изменишь его - изменятся все они. Правило железное: в персистентной структуре после создания узел только читают.

Ожидание скорости обычного массива. Чтение персистентного массива - O(log n) переходов по узлам, разбросанным по памяти, а не одно обращение по адресу. Поэтому ветвление делают широким.

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

Векторы Clojure и Scala - деревья с ветвлением 32: на миллион элементов глубина 4, запись копирует четыре узла по 32 ссылки. Git хранит каталог деревом объектов: изменил один файл - новые объекты для файла и для каждого каталога на пути к корню, остальное берётся по хешу из прошлого коммита. LMDB и btrfs устроены как B-деревья с копированием при записи: читатель держит старый корень и видит непротиворечивый снимок, пока писатель строит новый.

Теперь сам

1. Персистентный массив на 2²⁰ ячеек (около миллиона). Сколько новых узлов создаст одна запись?
2. Сколько узлов займёт персистентный массив из 2²⁰ нулей, если одинаковые половины - один узел?
3. Почему вектор Clojure ветвится на 32, а не на 2?