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