# Возвращаемое значение функции <tex>Merge</tex> ставим на место удаляемого элемента.
== Высота декартового дерева Случайные ключи ==
Мы уже выяснили, что сложность операций с декартовым деревом линейно зависит от его высоты. В действительности высота декартова дерева может быть линейной относительно его размеров. Например, высота декартова дерева, построенного по набору ключей <tex>(1, 1), \ldots, (n, n)</tex>, будет равна <tex>n</tex>. Во избежание таких случаев, полезным оказывается выбирать приоритеты в ключах случайно.
== Высота в декартовом дереве ==
{{Теорема
|statement = Декартово дерево из <tex>n</tex> узлов, ключи <tex>y</tex> которых являются незавимыми непрерывными случайными величинами с одинаковым вероятностным распределением, имеет высоту <tex>O(\log n)</tex>.
|proof=
Замечание: В следующих утверждениях мы будем считать, что <tex>x_1 < x_2 < \ldots x_n</tex>, а каждое <tex>y_i</tex> выбрано случайно и независимо с одинаковым распределением, а также будем называть <tex>i</tex>-м узлом узел с ключом <tex>x_i</tex>.
{{Лемма
|statement = <tex>i</tex>-й узел является прародителем <tex>k</tex>-го узла тогда и только, когда <tex>y_i < y_j</tex> для любого <tex>j</tex> такого, что <tex>i < j \leqslant k</tex> или <tex>k \leqslant j < i</tex>.
|proof=
Рассмотрим случай <tex>i < k</tex>, в случае <tex>i > k</tex> доказательство аналогично.
Необходимость. Допустим, что <tex>y_i < y_j</tex> для всех <tex>i < j \leqslant k</tex>. Тогда по свойствам кучи <tex>i</tex>-й узел не может лежать в поддереве с корнем в <tex>k</tex>-м узле. Более того, не может существовать индекс <tex>j</tex> такой, что <tex>j</tex>-й узел общий прародитель <tex>i</tex>-го и <tex>k</tex>-го узлов, но эти узлы лежат в его разных поддеревьях. Если он существует, то <tex>x_i < x_j < x_k</tex>, следовательно, <tex>i < j < k</tex>. Но тогда <tex>j</tex>-й не мог быть прародителем <tex>i</tex>-го узла (опять же по свойствам кучи). Остался последний вариант взаимного расположения <tex>i</tex>-го и <tex>k</tex>-го узлов: <tex>i</tex>-й является прародителем <tex>k</tex>-го узла.
Достаточность. Пусть <tex>i</tex>-й узел является предком <tex>k</tex>-го узла. Докажем от противного. Предположим, что существует <tex>j</tex> такое, что <tex>i < j \leqslant k</tex> и <tex>y_j < y_i</tex>. По свойствам кучи <tex>i</tex>-й узел не может быть прародителем <tex>j</tex>-го узла. Если <tex>j</tex>-й узел является прародителем <tex>i</tex>-го узла, то из неравенства <tex>x_i < x_j < x_k</tex> следует, что <tex>i</tex>-й узел содержится в левом поддереве <tex>j</tex>-го узла, а <tex>k</tex>-й в правом. Это противоречит тому, что <tex>i</tex>-й узел прародитель <tex>k</tex>-го узла. Остается последний вариант взаимного расположения <tex>i</tex>-го и <tex>j</tex>-го узла: некоторый <tex>l</tex>-й узел является их общим прародителям, но они содержатся в его разных поддеревьях. Тогда получаем неравенство <tex>x_i < x_l < x_j \leqslant x_k</tex>, из которого следует, что <tex>k</tex>-й узел содержится в правом поддереве <tex>l</tex>-го узла. Снова противоречие. Значит, наше предположение не верно.
}}
{{Лемма
|about=о математическом ожидании глубины узла
|statement=Математическое ожидание глубины <tex>k</tex>-го узла равно <tex>H_k + H_{n-k+1} - 1</tex>, где <tex>H_j = \sum\limits_{i=1}^j\frac{1}{i} \approx \ln j</tex>.
|proof=Глубина <tex>k</tex>-го узла - это количество узлов, которые являются прародителями этого узла. Введем случайную величину <tex>A_i</tex>, равную единице, если <tex>i</tex>-й узел является прародителем <tex>k</tex>-го узла, и нулю в противном случае. Легко проверить, что <tex>A_i</tex> и <tex>A_j</tex> независимы при <tex>i \ne j</tex>. Из того, что <tex>y_i</tex> выбраны случайно и независимо с одинаковым распределением и предыдущей леммы следует, что <tex>M(A_i) = \frac{1}{|i - k| + 1}</tex> при <tex>i \ne k</tex>.
:<tex>M(depth_k)=M(\sum\limits_{i=1}^nA_i)=\sum\limits_{i=1}^nM(A_i)=\sum\limits_{i=1}^n\frac{1}{|i-k|+1}=</tex>
:<tex>=\sum\limits_{i=1}^k\frac{1}{k-i+1}+\sum\limits_{i=k}^n\frac{1}{i-k+1}-1=H_k+H_{n-k+1}-1</tex>.}}
Таким образом, мы доказали, что матожидание глубины конкретного узла <tex>O(\log n)</tex>.
Для начала введем несколько обозначений:
* <tex>x_k</tex> - вершина с <tex>k</tex>-ым по величине ключом;
}}
