3

I've got a tree structure that I need to rearrange (drag and drop) and then submit the changes.

What's going to be the best way to capture the changes? As I see it there are two ways:

  1. Store every change command, submit the list of changes then execute each one
  2. Serialize the tree and then diff the new tree with the old tree to work out what's changed, then execute the changes

1 seems easiest to implement, although it could be very wasteful if many repetitive actions have occurred (i.e. dragging nodes around many times, but putting them back where they started)

2 avoids the above problem, but how can I "diff" the trees to work out what parental change commands to execute? Presumably there are algorithms for this?

Edit To clarify, every node has an "id" and a "parentId". I need to allow users to rearrange the tree (thereby changing the parentId of some nodes).

For option 2, should it be straightforward enough to simply serialize the changed tree, then to work out the differences iterate over the the original tree in preorder, find the same node in the new tree and record a change if the parents are different? is that a robust approach that won't get stuck in a cycle?

Edit actually no, that won't work. I need to iterate over the NEW tree in preorder and find the corresponding node in the old tree, then diff parent ids etc..

halfer
  • 19,824
  • 17
  • 99
  • 186
Andrew Bullock
  • 36,616
  • 34
  • 155
  • 231
  • by rearrange, do you mean to change the structure of tree keeping the nodes same? – Srikanth Dec 01 '10 at 18:01
  • Since you want your diff to give you the operations necessary to convert one tree to the other, we'll need to know what operations are supported. – Niki Yoshiuchi Dec 01 '10 at 18:39
  • Can you explain why 'delete old tree', 'write new tree' isn't a viable option? Is the tree huge? What's the payload on each node? – Ian Mercer Dec 02 '10 at 08:40
  • @Hightechrider, that is an option, hadn't considered that... hmmm. that would also solve a separate problem. post a proper answer and ill +1 and probably accept – Andrew Bullock Dec 04 '10 at 16:28

2 Answers2

1

Unless the trees are huge it might be easiest simply to delete the old tree and then add the new tree.

Differencing two trees when the allowed operations include moves, deletes, adds is going to be much more complex so unless there is a significant benefit to be gained it's probably best to avoid that complexity and use a simple remove-then-add option.

Ian Mercer
  • 38,490
  • 8
  • 97
  • 133
0

I would say, I follow the below algorithm to a forest changes changes why I am referring to forst because in normal gui based scenarios there can be number to trees. i don't know whether this is applicable to your scenario or not but for mine it is valid.

There can be scenarios

1- Child Added to Parent ( By Drag & Drop)

2- Parent added to child (By Drag & Drop)

3- one tree moved to another tree. (By merging root nodes) (this may not be applicable in your scenario)

for implementational point of view, I were using C# as my language.

My Approach to the problem

1- Create a in memory structure which represents tree
2- When user moves the node change the parent id ( Check has to be made that it is not results in a cycle)

3- Re-Create the tree so that in memory representation will always be updated.

4- take in memory representation and save.

so in my implementation point no 3 is crucial as I always hold the latest tree in my memory.

BenMorel
  • 34,448
  • 50
  • 182
  • 322
TalentTuner
  • 17,262
  • 5
  • 38
  • 63