166
правок
Изменения
→Split
Операция <tex>\mathrm{Split}</tex> (''разрезать'') позволяет сделать следующее: разрезать декартово дерево <tex>T</tex> по ключу
<tex>xk</tex> и получить два других декартовых дерева: <tex>T_1</tex> и <tex>T_2</tex>, причем в <tex>T_1</tex>находятся все ключи дерева <tex>T</tex>, не большие <tex>xk</tex>, а в <tex>T_2</tex> {{---}} большие <tex>xk</tex>.
<tex>\mathrm{Split}(T, xk) \to \{T_1, T_2\}</tex>.
Эта операция устроена следующим образом.
Рассмотрим случай, в котором требуется разрезать дерево по ключу, большему ключа корня.
Посмотрим, как будут устроены результирующие деревья <tex>T_1</tex> и <tex>T_2</tex>:
* <tex>T_1</tex>: левое поддерево <tex>T_1</tex> совпадёт с левым поддеревом <tex>T</tex>. Для нахождения правого поддерева <tex>T_1</tex>, нужно разрезать правое поддерево <tex>T</tex> на <tex>T^R_1</tex> и <tex>T^R_2</tex> по ключу <tex>xk</tex> и взять <tex>T^R_1</tex>.
* <tex>T_2</tex> совпадёт с <tex>T^R_2</tex>.
<pre>
Treap T // декартово дерево
Node x k // ключ по которому нужно разрезать декартово дерево
Split (Treap T, Node xk, Treap T1, Treap T2) { // T1, T2 - результат процедуры Split
if (T == NULL) {
T1 = T2 = NULL
}
else if (k.x.key > T.keyx) { Split (T.right, xk, T.right, T2)
T1 = T
}
else {
Split (T.left, xk, T1, T.left)
T2 = T
}
