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
<references />
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>.
==См. также==*[[Поисковые структуры данных2-3 дерево]]* [[B-дерево]]*[[Дерево поиска, наивная реализацияSplay-дерево]]*[[Декартово АВЛ-дерево]]*[[Декартово Красно-черное дерево по неявному ключу]]
==Примечания==
<references />
== Источники информации ==
* [http://en.wikipedia.org/wiki/Random_binary_tree Wikipedia {{---}} Random binary tree]
