Изменения

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

Рандомизированное бинарное дерево поиска

28 байт убрано, 20:50, 17 декабря 2018
Нет описания правки
l.size = 1 + l.left.size + l.right.size
'''return''' l
'''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
Докажем, что данный алгоритм оставляет рандомизированное дерево рандомизированным.
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/67959»

Навигация