166
правок
Изменения
Нет описания правки
Так как каждая вершина среди <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\\
\frac{1}{i - k + 1} &&, k \ < \ i\\
\end{array}\right.
</tex>
Подставив последнее в нашу формулу с математическим ожиданием получим:
: <tex>E(d(x_k)) = \sum\limits_{i = 1}^{n} Pr[A_{i,k} = 1] = \sum\limits_{i = 1}^{k - 1} \frac{1}{k - i + 1} + \sum\limits_{i = k + 1}^{n} \frac{1}{i - k + 1} \le ln(k) + ln(n-k)</tex>
В итоге мы получили что <tex>E(d(x_k)) = O(ln(n))</tex>.
}}
== Ссылки ==
*[http://ru.wikipedia.org/wiki/Декартово_дерево Декартово дерево — Википедия]
*[http://rain.ifmo.ru/cat/data/theory/trees/treaps-2006/article.pdf]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]
