Изменения

* <tex>x_k</tex> {{- --}} вершина с <tex>k</tex>-ым по величине ключом;* индикаторная величина <tex>A_{i, j} = \left\{\begin{array}{lllc} 1 &&, x_i\ -\ \text{ancestor} \ x_j\\ 0 &&, \text{otherwise}\\\end{array}\right.</tex>* <tex>d(v)</tex> - глубина вершины <tex>v</tex>; В силу обозначений глубину вершины можно записать как количество предков::<tex>d(x_k) = \sum\limits_{i = 1}^{n} A_{i,k} </tex>. Теперь можно выразить математическое ожидание глубины конкретной вершины::<tex>E(d(x_k)) = \sum\limits_{i = 1}^{n} Pr[A_{i,k} = 1] </tex> {{---}} здесь мы использовали линейность математического ожидания <tex>E</tex>, и то что <tex>E(X) = Pr[X = 1]</tex> для индикаторной величины <tex>X</tex> (<tex>Pr[A]</tex> {{---}} вероятность события <tex>A</tex>).Для подсчёта средней глубины вершин нам нужно сосчитать вероятность того, что вершина <tex>x_i</tex> является предком вершины <tex>x_k</tex>, то есть <tex>Pr[A_{i,k} = 1]</tex>. Введем новое обозначение:* <tex>X_{i, k}</tex> {{---}} множество ключей <tex>\{x_i, \ldots, x_k\}</tex> или <tex>\{x_k, \ldots, x_i\}</tex>, в зависимости от <tex>i < k</tex> или <tex>i > k</tex>. <tex>X_{i, k}</tex> и <tex>X{k, i}</tex> обозначают одно и тоже, их мощность равна <tex>|k - i| + 1</tex>.  {{Лемма|statement=Для любых <tex>i \ne k</tex> , <tex>x_i</tex> является предком <tex>x_k</tex> тогда и только тогда, когда <tex>x_i</tex> имеет наименьший приоритет среди <tex>X_{i, k}</tex>.|proof=Если <tex>x_i</tex> является корнем, то оно является предком <tex>x_k</tex> и по определению имеет минимальный приоритет среди всех вершин, следовательно, и среди <tex>X_{i, k}</tex>. С другой стороны, если <tex>x_k</tex> {{---}} корень, то <tex>x_i</tex> {{---}} не предок <tex>x_k</tex>, и <tex>x_k</tex> имеет минимальный приоритет в treap’е; следовательно, <tex>x_i</tex> не имеет наименьший приоритет среди <tex>X_{i, k}</tex>. Теперь предположим, что какая-то другая вершина <tex>x_m</tex> – корень. Тогда, если <tex>x_i</tex> и <tex>x_k</tex> лежат в разных поддеревьях, то <tex>i < m < k</tex> или <tex>i > m > k</tex>, следовательно, <tex>x_m</tex> содержится в <tex>X_{i , k}</tex>. В этом случае <tex>x_i</tex> – не предок <tex>x_k</tex>, и наименьший приоритет среди <tex>X_{i, k}</tex> имеет вершина с номером <tex>m</tex>. Наконец, если <tex>x_i</tex> и <tex>x_k</tex> лежат в одном поддереве, то доказательство применяется по индукции, так как это поддерево является меньшим treap’ом. Пустой treap есть тривиальная база. }} Так как каждая вершина среди <tex>X_{i, k}</tex> может иметь минимальный приоритет, мы немедленно приходим к следующему равенству: