= Декартово дерево#footnote[a.k.a ДД, Treap, Дерамида, Пиво, Курево]
Хотим реализовать set.

Каждая вершина дерева хранит пару $(x, y)$ -- (ключ, приоритет).

Приоритет --- внутренняя информация для балансировки.

Предполагаем, что $x$-ы и $y$-и уникальны.

- По ключам ($x$) --- двоичное дерево поиска
- По приоритетам ($y$) --- куча (с максимумом вверху)

== Версия 1980 (offline)

В этой версии приоритетов нет

Вставка (как в простом бинарном дереве) в порядке случайной перестановки

== Версия 1996

Вставка в произвольном порядке, но с приоритетами

Берем $y$ из равномерного распределения: $y in U[0, 1]$ --- получаем нулевую
вероятность совпадения приоритетов

Характеристики:
- Глубина вершины: $E("dep"[v]) = O(log n)$
- Высота вершины: $E(h[v]) = O(1)$
- Размер поддерева вершины: $E("sz"[v]) = O(log n)$

Есть два способа реализации:
- с поворотами
- через split-merge

== Split-Merge

=== Split

"Режем" дерево вертикальной прямой: `pair<T, T> split(T tree, int line_x)`.

Все ключи левого дерева меньше прямой, все ключи правого --- больше

=== Merge

Есть два дерева такие, что у левого все ключи меньше, чем у правого.

Merge объединяет их в одно дерево: `T split(T left, T right)`.

=== Insert

```python
tl, tr = split(t, x)
merge(tl, merge(T({x, y}), tr))
```

=== Delete

- Двумя `split`-ами отрезаем все элементы меньше $x$ и все элементы больше $x$.
- `merge`-им два эти дерева

== Повороты

#grid(
    columns: (1fr, auto, 1fr),
    align: center + horizon,
    [
        - y
            - x
                - A
                - B
            - C
    ],
    $arrow("right(x)")\ arrow.l("left(y)")$,
    [
        - x
            - A
            - y
                - B
                - C
   ]
)

=== Insert

- Вставка до листа
- Подъем поворотами

=== Delete

- Поворотами опускаем в лист
- Удаляем лист

=== Split

Делаем `split(a)`

- `insert({a, +inf})` --- новый элемент окажется в корне
- Левое и правое поддерево корня --- нужные деревья

=== Merge (Join)

- Подвесим деревья к `{a, +inf}`
- Сделаем `delete(a)`

== Теоремы

=== Теорема 1

Пусть ключи отсортированы: $x_1 < ... < x_n$

Хотим узнать $"dep"[x_l] = sum_(i = 1)^n A_(i, l)$ --- где
$A_(i, l) = "int"(x_i "- предок" x_l)$

$"sz"[x_l] = sum_(j = 1)^n A_(l, j)$

==== Следствие

$a_(i, l) = P(x_i "- предок" x_j)$

$E("dep"[x_l]) = sum_(i = 1)^n a_(i, l) = E("sz"[x_l]) = sum_(i = 1)^n a_(l, i)$

==== Лемма

Пусть все приоритеты разные (это происходит с вероятностью $= 1$)

$ x_i "- предок" x_j
    <=> "prior"(x_i) = max_(min(i, j) <= k <= max(i, j)) "prior"(x_k) $

$ a_(i, j) = 1/(abs(i - j) + 1) $

==== Теорема

$ ln n := log_e n $
$ lg n := log_2 n $

$ E("dep"[x_l])
    = 1/(abs(l - 1) + 1) + 1/(abs(l - 2) + 1) + ...
        + 1/(1 + 1) + 1/1 + 1/(1 + 1) + ...
        + 1/(abs(n - l) + 1) = \
    = {H_l "- сумма гармонического ряда до " l} =\
    = H_l + H_(n - l + 1) - 1
    < {ln(n) < H_n < ln(n) + 1} < 1 + 2 ln n $

$ E("sz"[x_l]) < 1 + 2 ln n $

$ h_n / ln_n -> gamma, n -> +oo, "где" gamma approx 4.311 $

= Zip-дерево

Цель создания --- чтобы ранг (приоритет) занимал меньше бит. В zip-дереве он
имеет значение от $1$ до $lg n$ (т.е. столько же, сколько и слоев) и занимает
$lg lg n$ бит.

Берем не равномерное распределение, а геометрическое. Это логично т.к.
количество вершин на соседних уровнях различается примерно в два раза.

$ P("rank" = 0) = 1/2, P("rank" = 1) = 1/4, ..., P("rank" = k) = 1/(2^(k + 1)) $

Теперь многие приоритеты совпадают.

Пусть у $v$ есть два сына $l$ и $r$:
- $"rank"(l) < "rank"(v)$
- $"rank"(r) >= "rank"(v)$

Дерево будет перекошено влево.

$ E("rank") = 0 dot 1/2 + 1 dot 1/4 + ... => 2 E = E + 1 => E = 1 $

Операции `unzip` и `zip` --- аналоги `split` и `merge`

#figure(
    caption: [Вставка и удаление в `zip`-дереве],
    image("zip-tree-insert-delete.jpg", height: 5cm)
)

`zip-tree` имеет естественный изоморфизм со `skip-list`: Вершина, которая лежит
в $k$-ом уровне, но не лежит в $(k + 1)$-ом в `skip-list`-е имеет `rank = k`.

#figure(
    caption: [Изоморфизм `zip-tree` и `skip-list`],
    image("zip-tree-skip-list.jpg", height: 5cm)
)

`zip-tree` c данными ключами и приоритетам единственно.

== Теоремы

=== Формулки

$ r_i := "rank"(i) $
$ "rr" := "rank"("root") $

$ P(r_i = k) = 1/(2^(k + 1)) => P(r_i < k) = 1/2 + ... + 1/(2^(k)) = 1 - 1/(2^k) $

$ P(r_i > k) = 1/(2^k) => P(max_i r_i < k) = (1 - 1/(2^k))^n
    underbrace(>=, "по н-ву Бернули") 1 - n/(2^k) $

$ P(max r_i >= k) <= n/(2^k) $

$ P("rr" >= ln n +C) <= n/(2^(ln n + C)) = 1/(2^C) $

$ P("rr" >= (c + 1) ln n) <= 1/(n^C) $

=== Теорема

$ E("rr") = 0 dot P("rr" = 0) + 1 dot P("rr" = 1) + ... =\
    = 0 dot P_0 + 1 dot P_1 + ... + ceil(lg n) P_ceil(lg n)
        + (ceil(lg n) + 1) P_(ceil(lg n) + 1) + ... <=\
    <= ceil(lg n) dot sum_(i = 1)^oo P_i + 1 dot 1/2 + 2 dot 1/4 + 3 dot 1/8 + ...
    = ceil(lg n) + 2 < lg n + 3 $

=== Лемма

- `low` --- предки $x$-а с ключом, *меньше* чем у $x$-а
- `high` --- предки $x$-а с ключом, *больше* чем у $x$-а

$y_l$ --- самый высокий из `low`
$y_h$ --- самый высокий из `high`

$ E("# low") = 1 + ("rank"(y_e) - "rank"(x)) <= 1 + "rank"(y_l) <= lg n + 4$

$ E("# high") <= (1 + "rank"(y_h)) / 2 $

=== Теорема

Из прошлых лемм:
$ E("dep"[v]) = 3/2 lg n + O(1) $

=== Теорема (без доказательства)

$ E("sz"[v], "rank"(v) == k) <= 3 dot 2^k - 1 $
$ E("sz"[v]) <= 3 / 2 lg n + 2 $

== Сравнение с ДД

#figure(table(
        columns: 3,
        align: center,
        table.header[][*ДД*][*Zip*],
        [глубина], $2 ln n = 1.3863 lg n$, $1.5 ln n$
))
