286
правок
Изменения
→Split
Псевдокод:
'''<tex>\langle</tex>Treap, Treap<tex>\rangle</tex>''' split('''Treap''' t, '''int''' k) '''if''' t == <tex> \varnothing </tex> '''return''' <tex>\langle</tex><tex> \varnothing </tex>, <tex> \varnothing </tex><tex>\rangle</tex>
'''int''' l = t.left.size
'''if''' l >= k
t.left = t2
update(t)
'''return''' <tex>\langle</tex>t1, t<tex>\rangle</tex>
'''else'''
<t1, t2> = split(t.right, k - l - 1)
t.right = t1
update(t)
'''return''' <tex>\langle</tex>t, t2<tex>\rangle</tex>
===Merge===
