Re: [boost] [intrusive] Looking for a non-recursive structural tree cloning algorithm
AMDG Ion Gazta?aga <igaztanaga@gmail.com> wrote:
So if you are a tree expert, I need your help to get a tree cloning function, that:
* Does not use the comparison predicate or calls any function that uses it (e.g.: insert())
* Can destroy all constructed nodes in a non-recursive form if node-copying throws an exception.
* It's pretty efficient ;-)
Willing to help?
Ion
warning untested: node* current = root; node* new_root = 0; node* insertion_point = 0; insertion_point = new_root = copy_node(*current); // sets the links to zero try { while(true) { if(current->left != 0 && insertion_point->left == 0) { current = current->left; node* temp = insertion_point; insertion_point = copy_node(*current); insert_at_left(temp, insertion_point); } else if(current->right != 0 && insertion_point->right == 0) { current = current->right; node* temp = insertion_point; insertion_point = copy_node(*current); insert_at_right(temp, insertion_point); } else { if(current == root) break; current = current->parent; insertion_point = insertion_point->parent; } } } catch(...) { destroy_tree(new_root); throw; } In Christ, Steven Watanabe
Steven Watanabe wrote:
warning untested:
[snip]
Thanks Steven. If an exception is thrown, new_root is the root of a BST tree so a non-recursive destruction algorithm is possible. I'll test your code ASAP. Regards, Ion
Ion Gaztañaga wrote:
Steven Watanabe wrote:
warning untested:
[snip]
Thanks Steven. If an exception is thrown, new_root is the root of a BST tree so a non-recursive destruction algorithm is possible. I'll test your code ASAP.
I've implemented your algorithm and all Intrusive and Interprocess tree tests run ok. Since the STL-like tree's header node maintains links to the leftmost and rightmost nodes of the tree, I've also added the incremental computation of the rightmost and leftmost nodes of the newly created subtree to your function. The non-recursive tree destruction is based on the following algorithm found on http://eternallyconfuzzled.com: 1 void jsw_destroy ( struct jsw_tree *tree ) 2 { 3 struct jsw_node *it = tree->root; 4 struct jsw_node *save; 5 6 while ( it != NULL ) { 7 if ( it->link[0] != NULL ) { 8 /* Right rotation */ 9 save = it->link[0]; 10 it->link[0] = save->link[1]; 11 save->link[1] = it; 12 } 13 else { 14 save = it->link[1]; 15 free ( it ); 16 } 17 18 it = save; 19 } 20 } which incrementally linearizes the tree using right rotations (forming a singly linked list using the right children pointer) and destroys nodes with no left children. Thanks a lot again! Ion
participants (2)
-
Ion Gaztañaga -
Steven Watanabe