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