рекурсивный метод -- самый простой способ решить эту задачу. не всегда правда оптимальный.
Теперь давай смотреть на структуру дерева.
При добавлении N узлов нужно увеличить left и right всех узлов "правее" нового на 2*N. При удалении этих же N узлов -- на 2*N.
Теперь дальше. При изменении родителя узла нужно изменить left, right и level. С последним все ясно. с left и right дело обстоит так:
новый left (и right) узлов, который перенесли и всех узлов "правее" нужно увеличить на разность right родителя и left исходного.
Я не слишком сильно оптимизировал это место, поскольку обновление происходит по индексу да и операция переноса выполняется крайне редко (в моем случае).
Выглядит это так
1. Сдвигаю дерево для новых узлов
2. Меняю left и right указанного узла и его детей так, чтобы они заполнили пустое место.
3. Ещё раз сдвигаю дерево.
Если оптимизировать до одного запроса, то нужно ставить в запрос условия на left и right.
выделять нужно три варианта:
1. узел между тем, в который вставляют и тем который вставляют.
2. узел внутри того, который вставляют.
3. узел после того, который вставляют.
Первую группу сдвигаем "вправо" на количество вставляемых узлов.
Для второй группы изменяем родителя.
Третью сдвигаем "влево" на количество вставляемых узлов + изменяем level этих узлов.
Направления "вправо" и "влево" чисто условные. Определить их можно так:
Если вставляемый узел выше (в таблице отсортированной по left) того, в который вставляют, то "вправо" - это увеличение индексов, "влево" - уменьшение. В противном случае -- наоборот
Кажется так. И относится это только к переносу. Для копирования я так и не придумал ничего лучше рекурсивного перебора всех узлов, которые нужно скопировать.