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

На просторах везде растиражирована одна и таже статья forum.vingrad.ru/faq/topic-158343.html
Я не могу её осилить.
Может кто-нибудь объяснить на пальцах как перемещать узел по дереву?
  • Вопрос задан
  • 5328 просмотров
Пригласить эксперта
Ответы на вопрос 8
@Placido
Мне смысл перемещений узлов помог понять вот этот рисунок (на нем графически изображены пункты и подпункты условного меню с их правыми и левыми ключами):
image
И вот этот (иллюстрирует вставку нового узла):
image
С помощью схемы такого типа можно визуально понять, как изменяются ключи узлов при том или ином действии.
Ответ написан
Комментировать
@egorinsk
Нарисуйте небольшое дерево и вручную переместите узел, и посчитайте, что поменялось.
Ответ написан
Комментировать
Fesor
@Fesor
Full-stack developer (Symfony, Angular)


А теперь мысленно перенесите ноду в дереве из одной ветки в другую и посмотрите как пересчитать значения.
Ответ написан
Fesor
@Fesor
Full-stack developer (Symfony, Angular)
По сути если вы заменяете местами две ноды в дереве, то у них должны просто индексы инвертироваться между собой. А если вы добавляете ноду или убираете ее из ветки — то вам придется пересчитать все индексы справа и все слева от того места где была/будет нода. Как-то так.
Ответ написан
Комментировать
sdevalex
@sdevalex
Вводим колонку fix (tinyint 1). Далее так:

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

Введение дополнительной колонки облегчает понимание задачи. Флаг по сути помечает временно удалённые узлы.
Ответ написан
@nifus
возьмите готовый класс и посмотрите как происходит перемещение, код же открытый…
Ответ написан
Комментировать
Сделал себе скрипт, чтобы понять что там вообще происходит. Результат выглядит так:
http://jsfiddle.net/h4R43/3/
Ответ написан
Комментировать
alekciy
@alekciy
Вёбных дел мастер
По мне вот более лучшее описание: "Управление деревьями Nested Set".

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы