172
правки
Изменения
→Высота в декартовом дереве с случайными приоритетами
{{Лемма
|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> имеет минимальный максимальный приоритет в декартовом дереве; следовательно, <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> лежат в одном поддереве, то доказательство применяется по индукции: пустое декартово дерево есть тривиальная база, а рассматриваемое поддерево является меньшим декартовым деревом.
}}
Так как распределение приоритетов равномерное, каждая вершина среди <tex>X_{i, k}</tex> может иметь минимальный максимальный приоритет, мы немедленно приходим к следующему равенству:
: <tex>Pr[A_{i, j} = 1] = \left\{\begin{array}{lllc} \frac{1}{k - i + 1} &&, k \ > \ i\\
0 &&, k\ =\ i\\
