166
правок
Изменения
→Merge
<tex>T</tex> совпадёт с левым поддеревом <tex>T_1</tex>. Справа же нужно подвесить объединение правого поддерева
<tex>T_1</tex> и дерева <tex>T_2</tex>.
Псевдокод:
<pre>
Treap T // результат процедуры Merge
Treap T1, T2 // сливаемые деревья
Merge (Treap T, Treap T1, Treap T2) {
if (T1 == NULL || T2 == NULL) {
if (T1 != NULL) {
T = T1
}
else {
T = T2
}
}
else if (T1.y > T2.y) {
Merge (T1.right, T1.right, T2)
T = T1
}
else {
Merge (T2.left, T1, T2.left)
T = T2
}
}
</pre>
Рассуждая аналогично операции <tex>\mathrm{Split}</tex> приходим к выводу, что трудоёмкость операции <tex>\mathrm{Merge}</tex>
