Изменения

Перейти к: навигация, поиск

Декартово дерево

49 байт добавлено, 09:03, 17 апреля 2012
Высота в декартовом дереве
Мы уже выяснили, что сложность операций с декартовым деревом линейно зависит от его высоты. В действительности высота декартова дерева может быть линейной относительно его размеров. Например, высота декартова дерева, построенного по набору ключей <tex>(1, 1), \ldots, (n, n)</tex>, будет равна <tex>n</tex>. Во избежание таких случаев, полезным оказывается выбирать приоритеты в ключах случайно.
== Высота в декартовом дереве с случайными приоритетами ==
{{Теорема
|statement = Декартово дерево из <tex>n</tex> узлов, ключи <tex>y</tex> которых являются независимыми [[Дискретная случайная величина|случайными величинами]] одного и того же распределения, имеет высоту <tex>O(\log n)</tex>.

Навигация