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

Question

[Дмитрий Сергеев]

На просторах везде растиражирована одна и таже статья forum.vingrad.ru/faq/topic-158343.html
Я не могу её осилить.
Может кто-нибудь объяснить на пальцах как перемещать узел по дереву?

Answer 1

[Placido]

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

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

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

Answer 2

[egorinsk]

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

Answer 3

[Сергей Протько]

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

Comments

[Сергей Протько]

Answer 4

[Сергей Протько]

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

Answer 5

[sdevalex]

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

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

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

Comments

[egorinsk]

Неправильный и плохой алгоритм. Посчитать диапазоны изменяемых значений можно и без этого. Область, где меняются ключи, разбивается точкой вставки и точкой удаления на 3 части, и в этих 3 частях ключи увеличиваются/уменьшаются на одинаковую величину, если я ничего не путаю.

Answer 6

[nifus]

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

Answer 7

[Сергей Береснев]

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

Answer 8

[Алексей Сундуков]

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

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

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