166
правок
Изменения
→Высота в декартовом дереве
== Высота в декартовом дереве ==
{{Теорема
|statement = Декартово дерево из <tex>n</tex> узлов, ключи <tex>y</tex> которых являются независимыми [[Дискретная случайная величина|случайными величинами]] одного и того же распределения, имеет высоту <tex>O(\log n)</tex>.
|proof=
Для начала введем несколько обозначений:
* <tex>x_k</tex> {{---}} вершина с <tex>k</tex>-ым по величине ключом;
* индикаторная величина <tex>A_{i, j} = \left\{\begin{array}{lllc} 1 &&, x_i\ -\ \text{is ancestorof} \ x_j\\
0 &&, \text{otherwise}\\
\end{array}\right.
:<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>XX_{k, i}</tex> обозначают одно и тоже, их мощность равна <tex>|k - i| + 1</tex>.
{{Лемма
