Изменения

Пусть процедура <tex>\mathrm{split}</tex> запущена в корне дерева с требованием отрезать от дерева <tex>tk</tex> вершин. Также известно, что в левом поддереве вершины находится <tex>l</tex> вершин, а в правом <tex>r</tex>. Рассмотрим все возможные случаи: * <tex>l >= tk</tex>. В этом случае процедура нужно рекурсивно запустить процедуру <tex>\mathrm{split}</tex> должна просто пометить, что у корня больше нет от левого сына, и вернуть его бывшего левого сына в качестве левой части ответа, а сам корень {{---}} в качестве правой. * Случай (с тем же параметром <tex>t = l + 1k</tex>) рассматривается аналогично предыдущему. При этом новым левым сыном корня станет правая часть ответа рекурсивной процедуры, а правой частью ответа станет корень. * <tex>t l < lk</tex>Случай симметричен предыдущему. В этом случае нужно рекурсивно запустить Рекурсивно запустим процедуру <tex>\mathrm{split}</tex> от левого правого сына с тем же параметром <tex>tk - l - 1</tex>, и . При этом новым правым сыном корня станет левая часть сына станет левой частью ответа нашей рекурсивной процедуры, а правая часть сына левой частью ответа станет левым сыном корня, после чего корень станет правой частью ответа. * Случай Псевдокод:<texpre>Split(Treap t, int k, Treap &t1, Treap &t2) int l = t > .left.size; if l + 1</tex> рассматривается аналогично предыдущему= k split(t.left, k, с той лишь разницейt1, что от правого сына отрезается <tex>t .left) update(v) r = v; else split(t.right, k - l - 1, t.right, t2) update(v) l = v</texpre> вершин.