166
правок
Изменения
→Split
Случай, в котором требуется разрезать дерево по ключу, меньше либо равному ключа в корне, рассматривается симметрично.
Псевдокод:
<pre>
Treap T // декартово дерево
Node x // ключ по которому нужно разрезать декартово дерево
Split (Treap T, Node x, Treap T1, Treap T2) { // T1, T2 - результат процедуры Split
if (T == NULL) {
T1 = T2 = NULL
}
else if (x.key > T.key) {
Split (T.right, x, T.right, T2)
T1 = T
}
else {
Split (T.left, x, T1, T.left)
T2 = T
}
}
</pre>
Оценим время работы операции <tex>\mathrm{Split}</tex>. Во время выполнения вызывается одна операция <tex>\mathrm{Split}</tex> для
