Хочу понять алгоритм перемещания узла в дереве nested set

Мне смысл перемещений узлов помог понять вот этот рисунок (на нем графически изображены пункты и подпункты условного меню с их правыми и левыми ключами):

И вот этот (иллюстрирует вставку нового узла):

С помощью схемы такого типа можно визуально понять, как изменяются ключи узлов при том или ином действии.

Нарисуйте небольшое дерево и вручную переместите узел, и посчитайте, что поменялось.

А теперь мысленно перенесите ноду в дереве из одной ветки в другую и посмотрите как пересчитать значения.

По сути если вы заменяете местами две ноды в дереве, то у них должны просто индексы инвертироваться между собой. А если вы добавляете ноду или убираете ее из ветки — то вам придется пересчитать все индексы справа и все слева от того места где была/будет нода. Как-то так.

Вводим колонку fix (tinyint 1). Далее так:

— помечаем переносимый узел и детей fix = 1
— нормализуем ключи для узлов, которые находятся после удаляемого (как при удалении)
— изменяем ключи для переносимого узла и детей
— нормализуем ключи после переносимого узла (как при добавлении)
— снимаем пометку fix = 0 для всех

Введение дополнительной колонки облегчает понимание задачи. Флаг по сути помечает временно удалённые узлы.

возьмите готовый класс и посмотрите как происходит перемещение, код же открытый…

Сделал себе скрипт, чтобы понять что там вообще происходит. Результат выглядит так:
http://jsfiddle.net/h4R43/3/

По мне вот более лучшее описание: "Управление деревьями Nested Set".

А что бы лучше понять всю кухню просто брал листок и карандашом рисовал подобную схему, а потом вручную пересчитывал ключи.

Перемещение по сути два действия: удалили ноду со старого места, вставили в новое. В таким виде и предлагаю вручную дерево пересчитать два раза.