Re: [boost] [intrusive] Looking for a non-recursive structural tree cloning algorithm

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-09-09 05:43:12

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