1632
правки
Изменения
м
'''if''' r < m r.left = merge(l, r.left) <font color="green">// с вероятностью m n / (m + n)</font> r.size = 1 + r.left.size + r.right.size '''return''' r
==См. также==
*[[Поисковые структуры данных]]
*[[Дерево поиска, наивная реализация]]
*[[Декартово дерево]]
*[[Декартово дерево по неявному ключу]]
rollbackEdits.php mass rollback
l.size = 1 + l.left.size + l.right.size
'''return''' l
Докажем, что данный алгоритм оставляет рандомизированное дерево рандомизированным.
Очевидно, что время работы приведённых алгоритмов пропорционально глубине дерева. Но т.к. математическое ожидание глубины рандомизированного бинарного дерева поиска есть <tex>O (\log n)</tex>, где <tex>n</tex> {{---}} число вершин в дереве<ref>Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stei, "Introduction to Algorithms", Second Edition {{---}} Chapter 12.4</ref>, то математическое ожидание времени работы поиска, вставки и удаления {{---}} также <tex>O (\log n)</tex>.
== См. также ==
