172
правки
Изменения
→Merge
[[file:merge.png|thumb|400px|Операция merge]]
Рассмотрим вторую операцию с декартовыми деревьями {{---}} <tex>\mathrm{Mergemerge}</tex> (''слить'').
С помощью этой операции можно слить два декартовых дерева в одно.
ключи во втором(''правом''). В результате получается дерево, в котором есть все ключи из первого и второго деревьев.
<tex>\mathrm{Mergemerge}(T_1, T_2) \to \{T\}</tex>
Рассмотрим принцип работы этой операции. Пусть нужно слить деревья <tex>T_1</tex> и <tex>T_2</tex>.
Псевдокод:
'''func''' Mergemerge(t : '''Treap''', t1 : '''Treap''', t2 : '''Treap'''):
'''if''' t1 == ''null'' '''or''' t2 == ''null''
'''if''' t1 != ''null''
t = t2
'''else if''' t1.y > t2.y
t = t1
'''else'''
t = t2
