Изменения
→Операция split
Как же устроена сея замечательная операция?
Рассмотрим случай, в котором требуется распилить разрезать дерево по ключу, большему ключа корня.
Посмотрим, как будут устроены результирующие деревья <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>x</tex> и взять <tex>T^R_1</tex>.
* <tex>T_2</tex> совпадёт с <tex>T^R_2</tex>.
Случай, в котором требуется распилить разрезать дерево по ключу, меньше либо равному ключа в корне, рассматривается симметрично.
Оценим время работы операции <tex>\mathrm{split}</tex>. Во время выполнения вызывается одна операция <tex>\mathrm{split}</tex> для
