I want to understand the algorithm for moving a node in a nested set tree

Question

PHP

In the open spaces, the same article forum.vingrad.ru/faq/topic-158343.html
is replicated everywhere I can’t master it.
Can someone explain on the fingers how to move a node through the tree?

Answer 1

This figure helped me understand the meaning of moving nodes (it graphically depicts the items and sub-items of the conditional menu with their right and left keys )

:

with one action or another.

Answer 2

Draw a small tree and manually move the node and count what has changed.

Answer 3

And now mentally transfer the node in the tree from one branch to another and see how to recalculate the values.

Answer 4

In fact, if you swap two nodes in a tree, then their indices should simply be inverted with each other. And if you add a node or remove it from a branch, then you will have to recalculate all indices to the right and all to the left of the place where the node was / will be. Something like this.

Answer 5

Enter the fix column (tinyint 1). Further, as follows:
- mark the portable node and children fix = 1
- normalize the keys for the nodes that are after the deleted one (as when deleting)
- change the keys for the portable node and children
- normalize the keys after the portable node (as when adding)
- remove the mark fix = 0 for all
The introduction of an additional column makes it easier to understand the problem. The flag essentially marks temporarily removed nodes.

Answer 6

take a ready-made class and see how the movement happens, the code is open ...

Answer 7

I made myself a script to understand what is happening there. The result looks like this:
http://jsfiddle.net/h4R43/3/

Answer 8

For me, here's a better description: " Managing Nested Set Trees ".
And in order to better understand the whole kitchen, he simply took a piece of paper and drew a similar diagram with a pencil, and then manually counted the keys.
Moving is essentially two actions: the node was removed from the old place, inserted into the new one. In this form, I propose to manually count the tree twice.