166
правок
Изменения
→Высота в декартовом дереве с случайными приоритетами
== Высота в декартовом дереве с случайными приоритетами ==
{{Теорема
|statement = Декартово дерево В декартовом дереве из <tex>n</tex> узлов, приоритеты <tex>y</tex> которого являются [[Дискретная случайная величина|случайными величинами]] c равномерным распределением, имеет высоту средняя глубина вершины <tex>O(\log n)</tex>.
|proof=
В итоге мы получили что <tex>E(d(x_k)) = O(\log(n))</tex>.
}}
Таким образом, среднее время работы операций <tex>Split</tex> и <tex>Merge</tex> будет <tex>O(\log(n))</tex>.
== См. также ==
