166
правок
Изменения
→Высота в декартовом дереве с случайными приоритетами
|statement = Декартово дерево из <tex>n</tex> узлов, приоритеты <tex>y</tex> которого выбраны случайно и независимо, имеет высоту <tex>O(\log n)</tex>.
|proof=
Будем считать, что все выбранные приоритеты попарно различны.
Для начала введем несколько обозначений:
