Preorder tree traversal copy folder. [CLOSED]

Question

Hi,

We have a database that contains several Trees. These trees are build using the "Preorder tree traversal" principle. This is a very powerful way of creating trees but it has one big disadvantage, adding multiple nodes at once.

We have to create a copy function in our tree, copying a single (lowest level) node is very easy, you can do this in one call. But now we want to copy a whole folder at once. We were wondering if we should do this in .net of with a stored procedure. We have to make sure that the transaction works, if anything goes wrong all has to be rollbacked because otherweise the tree will get corrupted.

Anyone who can help me with this? Any info about PTT you can find it here: http://en.wikipedia.org/wiki/Tree_traversal

Edit:

some more information is clearly needed. I have a 2 trees:

Root
Folder 1
 Item 
 Item
 Item
Folder 2
 Item
 Item
Folder 3
 Folder 4
  Item
  Item
 Folder 5
  Item

Root 2
    Folder 6

I want to be able to copy folder 3 underneith folder 6. soo the children need to be copied together with all items. And all the left and rights need to be adjusted properly. If something fails a complete rollback is needed. Hope this is much clearer now.

EDIT2 :

I've written a stored procedure for this. If anyone wants it just ask i'll get back to this question later this day. I'll post it if you want.

Regards, Sem

Answer 1

Could you not traverse the entire tree and insert it into a new binary tree? If you have multiple data sets that need to be combined you can just traverse each one in any order and have the tree rebuild itself.

Could you give more information on what you mean with folder?

I think this question needs more information before it can be fully answered.

As for making sure the transaction works, test it on a database that is not in production!

Answer 2

I'm guessing from your reference to 'left and rights' that you're talking about a nested set representation of a tree. In that case replicating an entire branch is not all that different to adding one node, the process is basically:

• Open a space in the left and right sequences for the new nodes
• Insert the new nodes with the correct sequences

So, if your trees are numbered as follows:

Root (1, 27)
Folder 1 (2, 8)
        Item (3, 4)
        Item (5, 6)
        Item (6, 7)
Folder 2 (9, 14)
        Item (10, 11)
        Item (12, 13)
Folder 3 (15, 26)
        Folder 4 (16, 21)
                Item (17, 18)
                Item (19, 20)
        Folder 5 (22, 25)
                Item (23, 24)

Root 2 (1, 4)
    Folder 6 (2, 3)

And the trees are in different tables, the code for replicating folder 3 below folder 6 is in the block below. Some of the SQL constructs like UPDATE ... FROM ... may be syntactically a little different in your environment, those below are as used in PostgreSQL. I believe that MSSQL requires that the table being updated is included in the FROM clause.

-- Push the items below this point down the sequence by as much as is required to accomadate the new branch (Not required in this case, but here for completeness)
UPDATE tree2 SET leftsequence = leftsequence + (tree.rightsequence - tree.leftsequence), rightsequence = rightsequence + (tree.rightsequence - tree.leftsequence)
 FROM tree
 WHERE tree2.leftsequence > 2 AND tree2.rightsequence = 3
  AND tree.leftsequence = 15;

-- Copy the nodes
INSERT INTO tree2 (label, leftsequence, rightsequence)
 SELECT label, leftsequence - (15 - 2) + 1, rightsequence - (15 - 2) + 1
  FROM tree
  WHERE leftsequence BETWEEN 15 AND 26;