Изменения

Пусть процедура <tex>split</tex> запущена в корне дерева с требованием отрезать от дерева <tex>t</tex> вершин. Также известно, что в левом поддереве вершины находится <tex>l</tex> вершин, а в правом <tex>r</tex>. Рассмотрим сначала два тривиальных случая. Первыйвсе возможные случаи: * <tex>l = t</tex>. В этом случае процедура <tex>split</tex> должна просто пометить, что у корня больше нет левого сына, и вернуть его бывшего левого сына в качестве левой части ответа, а сам корень {{---}} в качестве правой. Второй случай * Случай (<tex>t = l + 1</tex>) рассматривается аналогично. Следующий случай не так тривиален: * <tex>t < l</tex>. В этом случае нужно рекурсивно запустить процедуру <tex>split</tex> от левого сына с тем же параметром <tex>t</tex>, и левая часть сына станет левой частью ответа нашей процедуры, а правая часть сына станет левым сыном корня, после чего корень станет правой частью ответа. * Случай <tex>t > l + 1</tex> рассматривается аналогично, с той лишь разницей, что от правого сына отрезается <tex>t - l - 1</tex> вершин.